Задача A. Код Грея

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

Формат входного файла

Во входном файле содержится строка из символов 0 и 1

Формат выходного файла

Выходной файл должен содержать 2N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
0
2
110
110
111
101
100
000
001
011
010

Задача B. Ископаемая арифметика

Автор:И. Бураго   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Анализ следов письменности позволил археологам определить, что индейцы использовали натуральные числа в диапазоне от 1 до 2N. Запись любого числа состояла из ровно N знаков двух видов. За сходство с латинскими буквами ученые назвали один из знаков Q-символом, другой — R-символом, а саму запись — QR-записью.

Выяснилось также, что индейцы сравнивали числа в QR-записи по следующему правилу:

  1. числа равны, если имеют идентичную запись;
  2. одно число меньше другого, если в записи первого количество R-символов меньше, чем в записи второго;
  3. при равном количестве R-символов числа сравниваются как строки (при этом Q-символ считается меньше R-символа).

Для облегчения работы археологам необходима программа для перевода натуральных чисел в QR-запись.

Формат входного файла

Во входном файле содержатся числа N и K.

Формат выходного файла

В единственной строке выходного файла должна содержаться QR-запись числа K. Строка должна состоять ровно из N символов, каждый из которых должен быть заглавной латинской буквой Q (ASCII 81) или R (ASCII 82).

Ограничения

1 ≤ N ≤ 30, 1 ≤ K ≤ 2N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
QQ
2
3 5
QRR

0.204s 0.018s 15