Три кучи

Два игрока, Петя и Ваня, играют в игру с тремя кучами камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Например, если в первой куче 10 камней, во второй 7, а в третьей 4 камня, то за один ход можно получить одну из шести позиций: (13, 7, 4), (20, 7, 4), (10, 10, 4), (10, 14, 4), (10, 7, 7), (10, 7, 8).

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее N. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет N или больше камней. В начальный момент в первой куче было A камней, во второй куче B камней, в третьей куче – S камней (0 < A + B + S < N).

Нужно ответить на следующие вопросы:

1. При некотором значении S Ваня одержал победу своим первым ходом после неудачного хода Пети. Нужно указать минимальное значение S, при котором это возможно.
2. Найти минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.
3. Найти минимальное значение S, при котором одновременно выполняются два условия:
   1. у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
   2. у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Входной файл INPUT.TXT в первой строке содержит натуральное число Q – количество наборов, в каждом из которых содержится по три натуральных числа A, B, N (1 < A, B, N < 1000; 1 ≤ Q ≤ 20).

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

В выходной файл OUTPUT.TXT для каждого теста и каждого вопроса в отдельной строке выведите ответ на задачу.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

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

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