Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Китайская игра «Цзяньшидзы»

(Время: 1 сек. Память: 16 Мб Сложность: 69%)

В древнем Китае было придумано множество интересных игр. Все знают очень известную игру «Majong». В данной задаче мы рассмотрим другую интересную китайскую игру «Цзяньшидзы». Кратко сформулируем правила игры:

Из двух куч каменей, двое играющих поочередно могут брать:

  1. Произвольное ненулевое число камней из одной кучи.
  2. Одновременно по одинаковому произвольному ненулевому числу камней из обеих куч.

Выигрывает тот, кто возьмет своим ходом последний камень.

Не сложно определить в каких случаях выигрывает первый, а в каких случаях выигрывает второй игрок. Задача сводится к нахождению так называемых проигрышных пар (ai, bi), означающих, что при кучах камней содержащих ai и bi камней проигрывает тот, кто в данный момент совершает свой ход. Вам предстоит решить эту задачу, но немного в другом виде.

Обозначим проигрышную, для ходящего позицию, когда в кучках a и b камней (a, b). Так как порядок куч не играет роли, то всегда будем считать, что a ≤ b. Упорядочим все проигрышные позиции в лексикографическом порядке, иначе говоря:

(a1, b1) < (a2, b2), если (a1< a2) или ((a1= a2) и (b1< b2)).

Занумеруем проигрышные пары, начиная с 0. Ваша задача: найти k-ю пару проигрышных куч.

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

В первой строке входного файла INTPUT.TXT находится число N, (1 ≤ N ≤ 1000) - количество тестов в файле. В следующих N строках содержатся числа ki, (0 ≤ ki ≤ 109) порядковый номер пары проигрышных куч, которую требуется найти.

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

В выходной файл OUTPUT.TXT выведите N пар чисел (aki, bki) по одной в каждой строке.

Пример

INPUT.TXTOUTPUT.TXT
13
0
1
2
0 0
1 2
3 5

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru