[ROI 2018] Addition without carry

ID: 10315

远端评测题

2000ms

512MiB

尝试: 0

已通过: 0

难度: 9

上传者:

Hydro

标签>

2018

ROI（俄罗斯）

Background

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

Problem Description

For a set containing only natural numbers, if the sum of all numbers in the set equals the bitwise $\mathtt{OR}$ of all numbers in the set, then we call it a “beautiful set”.

Given $a_1 \ldots a_n$ , there exists a “beautiful set” consisting of the sequence $b_1 \ldots b_n$ , such that:

For all $i = 1 \ldots n$ , $b_i \ge a_i$ , and
$\sum b_i$ is minimized.

Find $\sum b_i$ of the new sequence.

For convenience, the given $a_i$ are all in binary form, and your answer should also be in binary form.

Input Format

The first line contains an integer $n$ .

The next $n$ lines each contain a binary number $a_i$ .

Output Format

Output the resulting binary value of $\sum b_i$ .

2
10
10

2
10100
1001

Hint

For all testdata, $1 \le n \le 3 \times 10^5$ .

(In binary) the number of bits of $a_i$ does not exceed $3 \times 10^5$ , and the sum of bit lengths of all $a_i$ does not exceed $3 \times 10^5$ .

The subtask dependencies are for reference only. There are no subtask dependencies in the Luogu judging.

Constraints

Subtask	Score	$n$	$\max L$	Subtasks that must be passed
1	4	$n=2$	$\max L \le 10$
2	2		$\max L \le 20$	1
3			$\max L \le 100$	1,2
4			$\max L \le 1000$	1--3
5			$\max L \le 300\,000$	1--4
6	4	$n \le 100$	$\max L \le 100$	Guaranteed that $a_i$ is a power of $2$
7		$n \le 1000$	$\max L \le 1000$	6, guaranteed that $a_i$ is a power of $2$
8		$n \le 300\,000$	$\max L \le 300\,000$	6,7, guaranteed that $a_i$ is a power of $2$
9		$n \le 5$	$\max L \le 5$	U
10		$n \le 5$	$\max L \le 1\,000$	U,1--4,9
11		$n \le 1\,000$	$\max L \le 5$	U,9
12		$n \le 10$	$\max L \le 10$	U,1,9
13		$n \le 50$	$\max L \le 50$	U,1,2,9,12
14	7	$n \le 100$	$\max L \le 100$	U,1--3,6,9,12,13
15	7	$n \le 300$	$\max L \le 300$	U,1--3,6,9,12--14
16	8	$n \le 1000$	$\max L \le 1000$	U,1--4,6,7,9--15
17	8	$n \le 3000$	$\max L \le 3000$	U,1--4,6,7,9--16
18	6	$n \le 10\,000$	$\max L \le 10\,000$	U,1--4,6,7,9--17
19	7	$n \le 30\,000$	$\max L \le 30\,000$	U,1--4,6,7,9--18
20	7	$n \le 100\,000$	$\max L \le 100\,000$	U,1--4,6,7,9--19
21	6	$n \le 300\,000$	$\max L \le 300\,000$	U,1--20

Translated by ChatGPT 5

#P9293. [ROI 2018] Addition without carry

Background

Problem Description

Input Format

Output Format

Hint

还没有账户？

登录