日本情報オリンピック 第4回 女性部門

2024年1月22日
情報オリンピック日本委員会

問題文

JOI 高校の葵さんは，N 行 N 列のマス目の各マスに整数を十進数表記で書くことにした．具体的には上から i 行目 (1 ≦ i ≦ N)，左から j 列目 (1 ≦ j ≦ N) のマスには A_i + B_j を十進数表記で書く．

葵さんは数字を何文字書くことになるかを知りたい．つまり，葵さんが書く N² 個の整数の桁数の合計を求めたい．

A_i (1 ≦ i ≦ N) と B_j (1 ≦ j ≦ N) が与えられたとき，葵さんが書く N² 個の整数の桁数の合計を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 150 000．
• 1 ≦ A_i ≦ 999 999 999 (1 ≦ i ≦ N)．
• 1 ≦ B_j ≦ 999 999 999 (1 ≦ j ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (5 点) N = 1．
2. (11 点) N ≦ 2 000．
3. (15 点) A_i ≦ 2 000 (1 ≦ i ≦ N)，B_j ≦ 2 000 (1 ≦ j ≦ N)．
4. (8 点) 100 000 000 ≦ A_i ≦ 500 000 000 (1 ≦ i ≦ N)，100 000 000 ≦ B_j ≦ 500 000 000 (1 ≦ j ≦ N)．
5. (22 点) 100 000 000 ≦ A_i (1 ≦ i ≦ N)，100 000 000 ≦ B_j (1 ≦ j ≦ N)．
6. (12 点) A_i ≦ 150 000 (1 ≦ i ≦ N)，B_j = j (1 ≦ j ≦ N)．
7. (13 点) B_j = j (1 ≦ j ≦ N)．
8. (14 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A₁   A₂   …   A_N
B₁   B₂   …   B_N

出力

葵さんが書く N² 個の整数の桁数の合計を 1 行で出力せよ．

入出力例

入力例 1
3
97 79 7
20 2 21

出力例 1
20

葵さんが各マスに書く整数は以下の図のようになる．

例えば，葵さんは上から 1 行目，左から 1 列目のマスには A₁ + B₁ = 97 + 20 = 117 を書く．また，上から 3 行目，左から 2 列目のマスには A₃ + B₂ = 7 + 2 = 9 を書く．

葵さんが書く 9 個の整数は 117, 99, 118, 99, 81, 100, 27, 9, 28 であり，それぞれの桁数は 3, 2, 3, 2, 2, 3, 2, 1, 2 である．

よって，葵さんが書く 9 個の整数の桁数の合計は 3 + 2 + 3 + 2 + 2 + 3 + 2 + 1 + 2 = 20 となるため，20 を出力する．

この入力例は小課題 2, 3, 8 の制約を満たす．

入力例 2
4
8 97 996 9995
1 2 3 4

出力例 2
46

葵さんが各マスに書く数字は以下の図のようになる．

例えば，葵さんは上から 2 行目，左から 3 列目のマスには A₂ + B₃ = 97 + 3 = 100 を書く．この整数の桁数は 3 である．また，上から 4 行目，左から 2 列目のマスには A₄ + B₂ = 9 995 + 2 = 9 997 を書く．この整数の桁数は 4 である．

葵さんが書く 16 個の整数の桁数の合計は 46 となるため，46 を出力する．

この入力例は小課題 2, 6, 7, 8 の制約を満たす．

入力例 3
1
500000000
500000000

出力例 3
10

葵さんが書く整数は 1 個で，その値は 500 000 000 + 500 000 000 = 1 000 000 000 である．この整数の桁数は 10 である．

よって，葵さんが書く 1 個の整数の桁数の合計は 10 となるため，10 を出力する．

この入力例は小課題 1, 2, 4, 5, 8 の制約を満たす．

入力例 4
7
436981378 523812834 456708479 413571178 506402783 598271009 523936624
401203104 501634329 506090236 527167431 485527116 439442403 568364549

出力例 4
463

この入力例は小課題 2, 5, 8 の制約を満たす．