Задача №113918. Сложение без переносов
Операция побитового «или» для набора целых положительных чисел, записанных в двоичной системе счисления, устроена следующим образом. Результатом её применения является число, в двоичной записи которого единица устанавливается в тех разрядах, в которых содержится единица хотя бы у одного числа из набора.
В редких случаях побитовое «или» можно использовать для сложения целых положительных чисел, записанных в двоичной системе счисления. Сумма набора чисел равна их побитовому «или», если для каждого разряда имеется не более одного числа из этого набора, у которого в этом разряде находится единица. Такие наборы чисел назовём красивыми .
Задан набор целых положительных чисел a 1 , a 2 , ..., a n . Необходимо построить красивый набор целых положительных чисел b 1 , b 2 , ..., b n , чтобы для всех i от 1 до n выполнялось условие b i ≥ a i , а сумма b 1 + b 2 + ... + b n была минимальна.
Требуется написать программу, которая по двоичной записи чисел a 1 , a 2 , ..., a n определяет двоичную запись минимального значения суммы искомого красивого набора b 1 , b 2 , ..., b n .
В первой строке записано целое число n — количество чисел в наборе ( 2 ≤ n ≤ 300 000 ).
Следующие n строк содержат двоичную запись целых положительных чисел a i , по одному в строке. Числа не содержат ведущих нулей, и суммарная длина их двоичных записей не превосходит 300 000 .
Требуется вывести двоичную запись минимальной суммы искомого красивого набора b 1 , b 2 , ..., b n . Ответ необходимо вывести без ведущих нулей.
Обозначим максимальную длину двоичной записи числа во входных данных как max L .
2 10 10
110
2 10100 1001
11101
3 1 1 110
1011