Задача A. Игра со спичками
Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?
Формат входных данных
Вводится одно натуральное число — N ( 1≤ N≤ 10000) начальное количество спичек в кучке.
Формат выходных данных
Выведите 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.
Примеры входных и выходных данных
|
Ввод |
Вывод |
|
2 |
1 |
|
3 |
2 |
Задача B. Игра со спичками
На столе лежит кучка из N спичек. Двое играют в такую игру. За один ход разрешается взять из кучки одну, две или три спички, так чтобы оставшееся количество спичек не было простым числом (Например, можно оставить в кучке 1 или 4 спички, но нельзя оставить 2 или 3). Выигрывает тот, кто забирает последнюю спичку. Требуется определить, кто из игроков имеет выигрышную стратегию.
Формат входных данных
Вводится одно число N (1<=N<=10000).
Формат выходных данных
Выведите число 1, если выигрышую стратегию имеет начинающий игрок, или число 2, если выигрышную стратегию имеет второй игрок.
Пример
|
Входные данные |
Выходные данные |
|
3 |
1 |
|
4 |
2 |
Задача C. Игра с фишками
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
|
|
|
Двое друзей играют в игру на бесконечной ленте. У каждого из них есть по одной фишке. В начале игры обе фишки стоят на первой клетке. Кроме этого, есть набор карточек с числами.
Игра состоит в том, что игроки по очереди выбирают одну из карточек и передвигают свою фишку по ленте на то количество клеток, какое число написано на карточке. После этого карточка выбрасывается.
Игра завершается, когда карточки закончились. Победившим считается игрок, у которого фишка стоит на поле с большим номером.
Известен набор карточек. Напишите программу, которая определит победителя и номера клеток, на которых будут стоять фишки по окончанию игры. Известно, что оба друга играют по оптимальной стратегии.
Формат входных данных
Сначала вводится число N — количество карточек с числами (1≤N≤100000). Далее записаны N натуральных чисел — числа, написанные на карточках. Каждое из этих чисел не превышает 10000.
Формат выходных данных
Выведите номер клетки, на которой будет стоять в конце игры фишка победителя, и номер клетки, на которой будет стоять фишка его противника, если оба использовали оптимальную стратегию.
Примеры
| Входные данные | Выходные данные |
| 4 5 1 8 2 | 11 7 |
| 4 1 1 1 1 | 3 3 |
Задача D. Камни
| Ограничение по времени: | 2 секунды |
| Ограничение по памяти: | 64 MB |
На столе лежат N камней. За ход игрок может взять
Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.
Формат входных данных
Вводится целое число 0 < N <= 100.
Формат выходных данных
Выведите 1 или 2 – номер игрока, который выиграет при правильной игре.
Примеры
|
Входные данные |
Выходные данные |
| 3 | 2 |
|
5 |
1 |
Задача E. Великая сеча
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Алеша Попович и Добрыня Никитич сражаются со стаей двух- и трехголовых драконов. Они по очереди взмахивают мечами, и одним махом могут отрубить любое (по своему желанию) число голов, но только у одного дракона. Отрубивший последнюю голову у последнего дракона получает в жены прекрасную принцессу.
Кто из богатырей (начинающий или второй) может получить в жены принцессу независимо от действий другого?
Формат входных данных
Во входном файле записано два числа N и M — количество двух- и трехголовых драконов соответственно (оба числа целые из диапазона от 0 до 100).
Формат выходных данных
В выходной файл выведите сначала число 1 или 2 определяющее, кто из богатырей имеет все шансы получить в жены принцессу (1 — тот, кто начинает, 2 — второй). В случае 1 выведите также все варианты его первого хода, которые к этому приводят: сначала выведите количество различных выигрышных ходов (при этом отрубание одинакового количества голов у разных двухголовых драконов считается одним и тем же ходом, так же и для трехголовых), а затем сами ходы. Каждый ход задается парой чисел: первое число определяет у сколькиголового дракона нужно отрубать головы, а второе — сколько голов нужно отрубать.
Примеры
| Входные данные | Выходные данные |
| 2 2 | 2 |
| 1 2 | 1 2 2 2 3 2 |