提示: 欢迎访问OurACM平台。
Problem 2255 过河

Accept: 20    Submit: 56
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

遥远的YS星球上,生活着两种物种名为Yellow和Star,简称物种Y和物种S。

神奇的是物种Y的体重始终为50kg,物种S的体重始终为100kg。

这天,n只生物结伴出行,在路途中,它们被一条长长的河流挡住了去路。所幸岸边停靠着一条船,船上写着:负重m kg。

YS星球上的物种有很强的时间观念,它们需要找出一种最快的方案过河:

1、要开船每次至少要有一只生物在船上

2、载着的生物总重量不能超过船的负重m

3、无论载多少只生物,船每次从岸边到另一岸边需要的时间相同,并且不考虑中间换乘时间(换句话说,要求的是最少的开船次数)

请你帮助这些Yellow、Star们,找出最少的开船次数,并且求出最少次数下的有多少种不同的方案数。

当存在某轮开船时,两个方案乘客的集合不同,认为这两个方案是不同的。

Input

包含多组测试数据。

第一行为n, m。

接下来n个数字,数字要么是50,要么是100。

1≤n≤50

200≤m≤1000

Output

输出两行,第一行为最少开船次数,第二行为不同方案数,由于方案数可能很大,对1000000007(10^9+7)取模后输出。

Sample Input

3 100 50 50 100

Sample Output

5 2

Hint

最优的两种情况为:

1和2过去,1回来,3过去,2回来,1和2过去。

1和2过去,2回来,3过去,1回来,1和2过去。

Source

福州大学第十四届程序设计竞赛_重现赛

Submit  Back  Status  Discuss