Экономическая игра "П&Т"
Задано два неотрицательных целых числа A и B. Два игрока – Поставщик (П) и Транзитер (Т), ходят по очереди и придерживаясь наилучшей стратегии, играют в игру, в которой П всегда начинает первым. За один ход нужно от большего с чисел вычесть натуральное число, кратное меньшому, получив при этом неотрицательный результат. Проиграл тот, кто не смог сделать ход.
Технические условия
Вход: Первая строка – количество тестов 1 <= N <= 10. В последующих N строк по два числа в каждой – значения A и B (A,B < 2*109).
Выход: В единственной строке последовательность из N чисел 1 или 2, записанных подряд без пробелов, где 1, 2 - номера выигравших игроков (1 – выиграл П, 2 – Т).
Информация о задаче
Лимит времени: 1 секундаЛимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 31% 70/101
Классификация: Теория игр
Пример
Пример входных данных3 25 7 15 10 5 5 |
Пример выходных данных121 |
| ← Количество дней | Список задач | Факториал - 2 → |