1579 . 來自未來的新台幣

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

98.1% (52/53)

Submission's AC Ratio

55.4% (144/260)

Tags

TOI 2015-TOI-2nd

Description

相信大家都知道，現在流通於市面的新台幣面額常見的有1, 5, 10, 50, 100, 500, 1000。（20、200、2000元和五角並不常見）
假設過了幾百年以後，央行發行了「新新台幣」，有N種面額，分別是1, 5, 10, 50, ...如此下去的規律，請計算給定的新台幣們能湊出的不為零的金額數有多少個。

Input Format

第一行有一個正整數$1\leq N\leq 19$，代表使用的新台幣面額個數。
第二行有$N$個正整數$0\leq c_i\leq 10^ 9$，代表現在有$c_i$個第$i$種新台幣。
以下以$S$代表$c_1+\dots+c_N$

子任務（測資） 額外限制 分數
1 (0~4) $c_i < 2$ 7
2 (5~9) $S\leq 20$ 11
3 (10~14) $N\leq 7, S\leq 1000$ 16
4(10~19) $N\leq 8, S\leq 2000$ 17
5 (0~24) 無限制 49

Output Format

輸出一個整數，代表能湊出的不為零的金額個數。請將答案模1000000007後輸出。

Sample Input 1

4
7 0 6 1

Sample Output 1

95

Hints

有7個1塊，6個10塊，1個50塊，能湊出1~7，10~17，20~27，30~37，40~47，50~57，60~67，70~77，80~87，90~97，100~107，110~117共95種非零金額。

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第二次模擬考pA

Subtasks

No. Testdata Range Score
1 0~4 7
2 5~9 11
3 10~14 16
4 10~19 17
5 0~24 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 5
1 1000 65536 262144 1 5
2 1000 65536 262144 1 5
3 1000 65536 262144 1 5
4 1000 65536 262144 1 5
5 1000 65536 262144 2 5
6 1000 65536 262144 2 5
7 1000 65536 262144 2 5
8 1000 65536 262144 2 5
9 1000 65536 262144 2 5
10 1100 65536 262144 3 4 5
11 1000 65536 262144 3 4 5
12 1000 65536 262144 3 4 5
13 1000 65536 262144 3 4 5
14 1000 65536 262144 3 4 5
15 1500 65536 262144 4 5
16 1500 65536 262144 4 5
17 1500 65536 262144 4 5
18 1500 65536 262144 4 5
19 1500 65536 262144 4 5
20 1000 65536 262144 5
21 1000 65536 262144 5
22 1000 65536 262144 5
23 1000 65536 262144 5
24 1000 65536 262144 5
Submit
Back to Top