| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 13 | 3 | 3 | 75.000% |
Операция побитового <<или>> для набора целых положительных чисел, записанных в двоичной системе счисления, устроена следующим образом. Результатом её применения является число, в двоичной записи которого единица устанавливается в тех разрядах, в которых содержится единица хотя бы у одного числа из набора.
В редких случаях побитовое <<или>> можно использовать для сложения целых положительных чисел, записанных в двоичной системе счисления. Сумма набора чисел равна их побитовому <<или>>, если для каждого разряда имеется не более одного числа из этого набора, у которого в этом разряде находится единица. Такие наборы чисел назовём красивыми.
Задан набор целых положительных чисел $a_1, a_2, \ldots, a_n$. Необходимо построить красивый набор целых положительных чисел $b_1, b_2, \ldots, b_n,ドル чтобы для всех $i$ от 1ドル$ до $n$ выполнялось условие $b_i \ge a_i,ドル а сумма $b_1+b_2+\ldots+b_n$ была минимальна.
Требуется написать программу, которая по двоичной записи чисел $a_1, a_2, \ldots, a_n$ определяет двоичную запись минимального значения суммы искомого красивого набора $b_1, b_2, \ldots, b_n$.
В первой строке записано целое число $n$ --- количество чисел в наборе (2ドル \leq n \leq 300,000円$).
Следующие $n$ строк содержат двоичную запись целых положительных чисел $a_i,ドル по одному в строке. Числа не содержат ведущих нулей, и суммарная длина их двоичных записей не превосходит~300ドル,000円$.
Требуется вывести двоичную запись минимальной суммы искомого красивого набора $b_1, b_2, \ldots, b_n$. Ответ необходимо вывести без ведущих нулей.
Обозначим максимальную длину двоичной записи числа во входных данных как $\max L$.
В подзадачах 6 -- 8 дополнительно $a_i = 2^{k_i}$ для некоторого $k_i$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $n = 2,ドル $\max L \le 10$ |
| 2 | 2 | $n = 2,ドル $\max L \le 20$ |
| 3 | 2 | $n = 2,ドル $\max L \le 100$ |
| 4 | 2 | $n = 2,ドル $\max L \le 1000$ |
| 5 | 2 | $n = 2,ドル $\max L \le 300,000円$ |
| 6 | 4 | $n \le 100,ドル $\max L \le 100$ |
| 7 | 4 | $n \le 1000,ドル $\max L \le 1000$ |
| 8 | 4 | $n \le 300,000円,ドル $\max L \le 300,000円$ |
| 9 | 4 | $n \le 5,ドル $\max L \le 5$ |
| 10 | 4 | $n \le 5,ドル $\max L \le 1,000円$ |
| 11 | 4 | $n \le 1,000円,ドル $\max L \le 5$ |
| 12 | 4 | $n \le 10,ドル $\max L \le 10$ |
| 13 | 4 | $n \le 50,ドル $\max L \le 50$ |
| 14 | 7 | $n \le 100,ドル $\max L \le 100$ |
| 15 | 7 | $n \le 300,ドル $\max L \le 300$ |
| 16 | 8 | $n \le 1000,ドル $\max L \le 1000$ |
| 17 | 8 | $n \le 3000,ドル $\max L \le 3000$ |
| 18 | 6 | $n \le 10,000円,ドル $\max L \le 10,000円$ |
| 19 | 7 | $n \le 30,000円,ドル $\max L \le 30,000円$ |
| 20 | 7 | $n \le 100,000円,ドル $\max L \le 100,000円$ |
| 21 | 6 | $n \le 300,000円,ドル $\max L \le 300,000円$ |
2 10 10
110
2 10100 1001
11101
3 1 1 110
1011