/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
非負整数 n の桁和を，n を 10 進法で表したときの各桁の和と定義します．例えば 2026 の桁和は 2+0+2+6=10 です．
正整数列 A=(A_1,A_2,\ldots,A_N)，B=(B_1,B_2,\ldots,B_N) が与えられます．
A, B を用いて，整数列 X=(X_0,X_1,X_2,\ldots,X_N) を次のようにして定めます．
- X_0 = 0 と定める．
- 各 i=1,2,\ldots,N について，X_i = 10X_{i-1} + A_i と X_i = 10X_{i-1} + B_i のどちらか一方を選んで，X_i を定める．
各 k=1,2,\ldots,N に対して，X_k の桁和としてありうる最小値を求めてください．
各 k について独立に解いてください．つまり，異なる k に対して，X_k の桁和を最小化する場合の整数列 X の定め方は同じである必要はありません．
制約
- 1\leq N\leq 20000
- 1\leq A_i \leq 10^9-1
- 1\leq B_i \leq 10^9-1
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられます．
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
k=1,2,\ldots,N に対して，X_k の桁和としてありうる最小値を，空白区切りで出力してください．
入力例 1
2 123 444 456 222
出力例 1
6 9
整数列 X=(X_0,X_1,X_2) としてありうるのは，次の 4 通りです．
- X = (0, 123, 1674)
- X = (0, 123, 1452)
- X = (0, 456, 5004)
- X = (0, 456, 4782)
X_1 の桁和としてありうる最小値は，123 の桁和である 6 です．
X_2 の桁和としてありうる最小値は，5004 の桁和である 9 です．
入力例 2
15 47640 28384 12457 87254 35032 27915 72870 32688 59091 95771 44037 44252 82222 87110 45829 41522 28795 85247 87801 45150 79509 15308 17923 75921 14992 71984 7601 42312 98436 36545
出力例 2
14 18 26 19 28 33 28 34 29 27 29 39 35 43 41
Score : 700 points
Problem Statement
Define the digit sum of a non-negative integer n as the sum of the digits when n is written in decimal notation. For example, the digit sum of 2026 is 2+0+2+6=10.
You are given positive integer sequences A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
Using A and B, define an integer sequence X=(X_0,X_1,X_2,\ldots,X_N) as follows:
- Set X_0 = 0.
- For each i=1,2,\ldots,N, choose one of X_i = 10X_{i-1} + A_i and X_i = 10X_{i-1} + B_i to determine X_i.
For each k=1,2,\ldots,N, find the minimum possible digit sum of X_k.
Solve independently for each k. That is, for different k, the way to determine the integer sequence X that minimizes the digit sum of X_k may be different.
Constraints
- 1\leq N\leq 20000
- 1\leq A_i \leq 10^9-1
- 1\leq B_i \leq 10^9-1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
For k=1,2,\ldots,N, output the minimum possible digit sum of X_k, space-separated.
Sample Input 1
2 123 444 456 222
Sample Output 1
6 9
The possible integer sequences X=(X_0,X_1,X_2) are the following four:
- X = (0, 123, 1674)
- X = (0, 123, 1452)
- X = (0, 456, 5004)
- X = (0, 456, 4782)
The minimum possible digit sum of X_1 is 6, which is the digit sum of 123.
The minimum possible digit sum of X_2 is 9, which is the digit sum of 5004.
Sample Input 2
15 47640 28384 12457 87254 35032 27915 72870 32688 59091 95771 44037 44252 82222 87110 45829 41522 28795 85247 87801 45150 79509 15308 17923 75921 14992 71984 7601 42312 98436 36545
Sample Output 2
14 18 26 19 28 33 28 34 29 27 29 39 35 43 41