#2850. 「ROI 2018 Day 2」无进位加法

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2018 Day2 T4. Сложение без переносов (Addition without carry)

对于一个只含自然数的集合,如果集合中所有数之和 = 集合中所有数的 \mathtt{OR} 和,那么我们称之为「美丽的集合」。

给出 a_1\ldots a_n, 存在一个数列 b_1\ldots b_n 满足:

  • \forall i=1\ldots n, b_i\geq a_i,
  • \sum b_i 最小。

试求出新数列的 \sum b_i

为了简便起见,我们给出的 a_i 均为二进制形式,你的答案也应是二进制形式。

样例

样例输入 1

2
10
10

样例输出 1

110

样例输入 2

2
10100
1001

样例输出 2

11101

样例输入 3

3
1
1
110

样例输出 3

1011

数据范围与提示

(在二进制下) a_i 的位数不超过 \max L .

子任务 # 分值 n⩽ \max L⩽ 子任务依赖 额外限制
0  0  样例
1 4 =2 10
2  2  20 1
3 2 100 1,2
4  2  1000 1-3
5 2 3×10^5 1-4
6 4 100 对于部分 k_i, a_i=2^{k_i}
7  4  1000 6
8 4 3×10^5 6,7
9  4  5 0
10 4 5 1000 0,1-4,9
11  4  1000 5 0,9
12 4 10 0,1,9
13  4  50 0-2,9,12
14 7 100 0-3,6,9,12,13
15  7  300 0-3,6,9,12-14
16 8 1000 0-4,6,7,9-15
17  8  3000 0-4,6,7,9-16
18 6 1×10^4 0-4,6,7,9-17
19 7 3×10^4 0-4,6,7,9-18
20  7  1×10^5 0-4,6,7,9-19
21 6 3×10^5 0-20