TopCoder

User's AC Ratio

95.8% (46/48)

Submission's AC Ratio

53.9% (55/102)

Description

  米花市出了一個大案件:重達近千斤的貨櫃一靠港立即不翼而飛,警方急著尋找貨櫃主人,卻發現主人橫死在自己家裡反鎖的浴室!名偵探蚵男再一次得到任務,他必須找出貨櫃裡究竟藏有什麼,並解開密室殺人案。

  所幸當初將東西搬上貨櫃的工人並未受到襲擊,根據他的說法,貨櫃裡有許多不同的貨品,包裝得很隱密,因此只知道貨櫃總重量以及每種貨品多重。至於每種貨品各有多少個,很遺憾地工人並不記得。警方想要分析這個貨櫃可能的組合方式,卻發現問題意外地複雜,舉例來說,貨櫃重10公斤,貨品有4種,分別為1、2、3、5公斤:

  10=5+5=5+3+2=5+3+1+1=5+2+1+1+1=5+1+1+1+1+1=…=1+1+1+…+1
  總計竟有高達20種可能性!

  身為蚵男,你是否能利用程式找出所有可能的組合情形,幫助無力的警方呢?

Input Format

輸入檔包含了多筆的測試資料。每筆資料兩行,第一行為一個正整數N(1≦N≦100)表示貨品種類數以及一個正整數P(1≦P≦10000)表示貨櫃總重;第二行包含N個相異正整數表示N種貨品的重量,同一行內的數字將以一個空白鍵分隔。最後一筆資料結束後會有一行0 0表示結束。

Output Format

針對每筆資料輸出一個整數,即貨櫃可能的組合情形,並以換行分隔。注意答案不一定總是小於232

Sample Input

3 10
11 12 13
4 10
1 2 3 5
0 0

Sample Output

0
20

Hints

※2007/10/07:測資出現問題,已修正。感謝各位因為long long炸掉的同胞們XD
(這年的問題這麼多,到底是怎樣= =+,還是自己出題好了|||)
(我看到232就很高興的用unsigned int...)

Problem Source

原TIOJ1043 / NPSC2003初賽(prob F)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536