Двоичная машина

На вход некоторой двоичной машине подается n-разрядное двоичное число. Машина подвергает поданное число следующим преобразованиям:

1. Записывает исходное число в регистры A и B размером N двоичных разрядов (бит).
2. N-1 раз выполняет следующие действия: циклически сдвигает регистр B на один бит влево (при этом самый старший бит переходит в самый младший); прибавляет к значению регистра A значение регистра B по модулю 2^N .
3. К регистру A применяется побитовая операция логического отрицания
4. К регистру A прибавляется 1 по модулю 2^N.
5. Значение регистра A выдается в качестве результата c отбрасыванием ведущих (незначащих) нулей.

Например, если на вход машине подать число 1001, то будут выполнены следующие преобразования:

№ шага	A	B	Result
1.	1001	1001
2. (повтор. 1)	1100	0011
2. (повтор. 2)	0010	0110
2. (повтор. 3)	1110	1100
3.	0001	1100
4.	0010	1100
5.	0010	1100	10

Напишите программу, которая по заданному числу возвращает результат преобразования согласно описанному алгоритму работы двоичной машины.

Входные данные

Первая строка входного файла INPUT.TXT содержит число N – количество двоичных разрядов (N ≤ 100 000). Вторая строка содержит ровно N двоичных разрядов (нулей или единиц) – входное число.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ – результат преобразования в двоичном виде без ведущих нулей.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]