ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Учёные из Спилково

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Миша и Дима — молодые перспективные учёные. Совместно со своими коллегами по инновационному центру Спилково они каждый день совершают невероятные открытия. Сейчас Миша с Димой изучают свойства удивительной функции F, которая записывается следующим образом:
C++:
int F(int x, int n)
{
    return (((x & ((1 << (n / 2)) - 1)) << ((n + 1) / 2)) | (x >> (n / 2)));
}
Pascal:
function F(x, n: integer): integer;
begin
    F := (((x and ((1 shl (n div 2)) - 1)) shl ((n + 1) div 2)) or (x shr (n div 2)));
end;
Друзья хотят провести следующий численный эксперимент.
  1. В ряд выписываются все целые числа от 0 до 2n − 1.
  2. Каждое число x в этом ряду заменяется на F(x, n).
  3. Каждое получившееся на шаге 2 число записывается в виде бинарной строки, состоящей ровно из n бит (если число содержит менее n бит, слева дописываются ведущие нули, если более n бит — старшие биты отбрасываются).
  4. Результатом является бинарная строка минимальной длины, содержащая все строки, полученные на шаге 3, в качестве подстрок.
Если вы сможете провести такой эксперимент, быть может, вас тоже возьмут работать в Спилково!

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

В единственной строке записано целое число n (1 ≤ n ≤ 20).

Результат

Выведите искомую бинарную строку. Если существует несколько оптимальных решений, можно вывести любое из них.

Пример

исходные данныерезультат
1
10
Автор задачи: Илья Кучумов
Источник задачи: Уральская региональная командная олимпиада по программированию 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2004. Учёные из Спилково