Задача на Python

ты на каком курсе учишься в колледже

подсказка: попробуй уменьшать размерность задачи, глядя на старший разряд k и x
например, если оба старших разряда равны 0, то число на последнем шаге 3 было в первой половине списка, и ответ для них будет такой же, как для k' и x' с обрезанными старшими разрядами, а если в k разряд 1, а в x 0, то такого быть не может, а если оба разряда 1, то ..., а если оба разряда ?, то...

Развёрнуто?

лучше научись приводить скан в читаемый вид.

Надо писать такие ответы

1780. Код Грея

Ограничение времени: 0.5 секунды

Ограничение памяти: 64 МБ

Денис, Ваня и Федя собрались на свою первую командную тренировку. Федя рассказал, что выучил алгоритм генерации кода Грея:

Создадим список из двух элементов: {0, 1}.

Добавим в конец списка все его элементы в обратном порядке: {0, 1, 1, 0}.

К первой половине элементов списка допишем слева 0, ко второй половине элементов списка допишем слева 1: {00, 01, 11, 10}.

Будем повторять шаги 2 и 3 до тех пор, пока длина всех элементов списка не станет равна n.

Число n называется длиной кода Грея. Так, код длины 3 выглядит следующим образом: {000, 001, 011, 010, 110, 111, 101, 100}.

Когда Денис применил алгоритм Феди, у него получилось, что на k-й позиции в списке (если нумеровать позиции с нуля) стоит двоичное число x. Ваня записал на бумажку числа k и x в двоичной системе счисления. Спустя много лет эта бумажка попала к вам в руки. К сожалению, некоторые цифры на ней стёрлись за эти годы. Сможете ли вы по оставшимся цифрам восстановить числа, которые были на ней записаны?

Исходные данные

В первой строке записано число k в двоичной системе счисления. Стёршиеся цифры обозначены символом «?». Во второй строке в аналогичном формате записано число x. Длины обоих чисел совпадают и не превосходят 105. Числа могут содержать ведущие нули.

Результат

Если по уцелевшим цифрам можно однозначно восстановить числа k и x, выведите их, заменив символы «?» на символы «0» и «1». Если существует несколько способов сделать это, выведите «Ambiguity». Если Денис или Ваня ошиблись, и восстановить числа невозможно, выведите «Impossible».

подсказка: попробуй уменьшать размерность задачи, глядя на старший разряд k и x
например, если оба старших разряда равны 0, то число на последнем шаге 3 было в первой половине списка, и ответ для них будет такой же, как для k' и x' с обрезанными старшими разрядами, а если в k разряд 1, а в x 0, то такого быть не может, а если оба разряда 1, то ..., а если оба разряда ?, то...