TopCoder

Caido
Waimai

User's AC Ratio

98.1% (53/54)

Submission's AC Ratio

53.9% (146/271)

Tags

Description

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

Input Format

第一行有一個正整數1N19,代表使用的新台幣面額個數。
第二行有N個正整數0ci109,代表現在有ci個第i種新台幣。
以下以S代表c1++cN

子任務(測資) 額外限制 分數
1 (0~4) ci<2 7
2 (5~9) S20 11
3 (10~14) N7,S1000 16
4(10~19) N8,S2000 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