/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder王国では、1 円硬貨、10 円硬貨、100 円硬貨の 3 種類の硬貨と、1000 円紙幣が流通しています。
高橋君は 1000 円紙幣を 10^{100} 枚、硬貨を 0 枚持っている状態から買い物を N 回行いました。
i 回目の買い物では A_i 円の商品を購入しました。
支払いでは、合計金額が A_i 円以上になるような最小枚数の 1000 円紙幣のみを出し、お釣りの硬貨の合計枚数が最小となるようにお釣りを受け取りました。
N 回の買い物が全て終わった時点で高橋君が持っている各硬貨の枚数を求めてください。
制約
- 1\leq N \leq 1000
- 1\leq A_i \leq 10^5
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \dots A_N
出力
N 回の買い物が終わった時点で高橋君が持っている 1 円硬貨、 10 円硬貨、 100 円硬貨の枚数を、この順に空白区切りで出力せよ。
入力例 1
3 1296 110 1
出力例 1
13 18 24
1 回目の買い物で、高橋君は 1296 円の支払いに対し 1000 円紙幣 2 枚を出し、100 円硬貨 7 枚と 1 円硬貨 4 枚をお釣りとして受け取ります。
2 回目の買い物で、高橋君は 110 円の支払いに対し 1000 円紙幣 1 枚を出し、100 円硬貨 8 枚と 10 円硬貨 9 枚をお釣りとして受け取ります。
3 回目の買い物で、高橋君は 1 円の支払いに対し 1000 円紙幣 1 枚を出し、100 円硬貨 9 枚、 10 円硬貨 9 枚、1 円硬貨 9 枚をお釣りとして受け取ります。
3 回の買い物が終わった時点で、高橋君は 1 円硬貨を 13 枚、 10 円硬貨を 18 枚、 100 円硬貨を 24 枚持っています。
入力例 2
12 3141 592 65358 9 79 323 84 6264 3 38327 950 28
出力例 2
52 59 82
Score : 200 points
Problem Statement
In the Kingdom of AtCoder, three kinds of coins — 1-yen coins, 10-yen coins, and 100-yen coins — and 1000-yen bills are in circulation.
Takahashi made N purchases, starting from a state where he had 10^{100} 1000-yen bills and 0 coins.
In the i-th purchase, he bought an item worth A_i yen.
For the payment, he paid using only the minimum number of 1000-yen bills such that the total amount paid was at least A_i yen, and received the change so that the total number of coins received as change was minimized.
Find the number of each type of coin that Takahashi has at the point when all N purchases are finished.
Constraints
- 1\leq N \leq 1000
- 1\leq A_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 \dots A_N
Output
Output the number of 1-yen coins, 10-yen coins, and 100-yen coins that Takahashi has at the point when the N purchases are finished, in this order, separated by spaces.
Sample Input 1
3 1296 110 1
Sample Output 1
13 18 24
In the first purchase, for the payment of 1296 yen, Takahashi pays with two 1000-yen bills, and receives seven 100-yen coins and four 1-yen coins as change.
In the second purchase, for the payment of 110 yen, he pays with one 1000-yen bill, and receives eight 100-yen coins and nine 10-yen coins as change.
In the third purchase, for the payment of 1 yen, he pays with one 1000-yen bill, and receives nine 100-yen coins, nine 10-yen coins, and nine 1-yen coins as change.
At the point when the three purchases are finished, he has 13 1-yen coins, 18 10-yen coins, and 24 100-yen coins.
Sample Input 2
12 3141 592 65358 9 79 323 84 6264 3 38327 950 28
Sample Output 2
52 59 82