Решение задач «Ограничение времени 2 секунды Ограничение памяти 512Mb»,
информатика в Новосибирске

Ограничение времени 2 секунды Ограничение памяти 512Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Операция побитового «или» для набора целых положительных чисел, записанных в двоичной системе счисления, устроена следующим образом. Результатом её применения является число, в двоичной записи которого единица устанавливается в тех разрядах, в которых содержится единица хотя бы у одного числа из набора. В редких случаях побитовое «или» можно использовать для сложения целых положительных чисел, записанных в двоичной системе счисления. Сумма набора чисел равна их побитовому «или», если для каждого разряда имеется не более одного числа из этого набора, у которого в этом разряде находится единица. Такие наборы чисел назовём красивыми. Задан набор целых положительных чисел 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 ? 3 0 0 0 0 0 ). Следующие n строк содержат двоичную запись целых положительных чисел a i , по одному в строке. Числа не содержат ведущих нулей, и суммарная длина их двоичных записей не превосходит 3 0 0 0 0 0 . Формат вывода Требуется вывести двоичную запись минимальной суммы искомого красивого набора b 1 , b 2 , … , b n . Ответ необходимо вывести без ведущих нулей. Пример 1 Ввод Вывод 2 10 10 110 Пример 2 Ввод Вывод 2 10100 1001 11101 Пример 3 Ввод Вывод 3 1 1 110 1011 Примечания Обозначим максимальную длину двоичной записи числа во входных данных как max L . В подзадачах 6 – 8 дополнительно a i = 2 k i для некоторого k i