← 返回题目列表

AtCoder · arc222_d

D. 移位并添加

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

定义 数字总和 非负整数的 非负整数的 n 作为数字的总和 n 以十进制表示。例如,数字和 2026 is 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 最小化数字和 X_k 可能有所不同。

约束

  • 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) 有以下四种:

  • X = (0, 123, 1674)
  • X = (0, 123, 1452)
  • X = (0, 456, 5004)
  • X = (0, 456, 4782)

的最小可能数字和 X_1 is 6,这是 123.

的最小可能数字和 X_2 is 9,这是 5004.


示例输入 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