TopCoder

User's AC Ratio

47.6% (10/21)

Submission's AC Ratio

14.9% (17/114)

Tags

Description

Jolin 是個愛唱歌的小孩,每次總喜歡邊唱邊用電腦把自己的歌聲錄下來,因此長久下來,在她的電腦裡,已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了,為了準備一份特別的耶誕禮物給爸爸,Jolin 準備從電腦中儲存的個人歌唱作品,挑選幾首歌製成一張個人專輯CD。由於每張CD 的容量有限,而Jolin 的個人歌唱作品早已遠遠超過一張CD 可收錄的容量,因此Jolin 希望你可以幫她想辦法,讓她所製作的專輯中,能有數目最多的歌曲(請注意:每一首歌只能被收錄一次),同時必需剛好裝滿整張CD,不留下任何未使用的空間。

Input Format

第一行為一個正整數N,代表Jolin 的個人歌唱作品數目。

第二行則有N個以空白相間隔的正整數Xi,分別代表第i 首個人歌唱作品的大小(單位為MBytes)。

第三行則有一個正整數S,代表CD 的容量(單位為MBytes)。

為簡化計算過程起見,我們假設每一首歌唱作品的大小皆不相同,同時N≦100,Xi≦200,S≦10000。

Output Format

請根據輸入的資料,輸出依序印出兩個正整數L 與K。

其中,L 代表最多可以在CD 中收錄的歌曲數目,K 代表共有幾種方式可以收錄L 首歌曲於CD 中。

注意,若歌曲曲目相同,但排列順序不同,仍視為不同的收錄方式。若沒有任何方法可以錄滿整片CD,則L=K=0。

Sample Input 1

5
10 50 30 70 60
80

Sample Output 1

2 4

Sample Input 2

5
10 50 30 70 60
20

Sample Output 2

0 0

Hints

Problem Source

原TIOJ1475 / 96北市賽
建中校內培訓第五次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7