Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2009-2010 уч. год, 7-9 классы, 1-й тур

Тематика

Теория игр

Примерная сложность

18%

Ссылки в Интернете

Условие –

Разбор –

Тесты –

Сдача решения –

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 24.05.2012

 

026. Игра со спичками

(Время - 1 сек., память - 16 Мб)

Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?

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

В единственной строке входного файла input.txt записано одно натуральное число — N (1 ≤ N ≤ 10000) начальное количество спичек в кучке.

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

В единственную строку выходного файла output.txt нужно вывести 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.

Примеры

input.txt

output.txt

1

2

1

2

3

2

Разбор

Если бы можно было брать только одну или две спички, то такая игра называется игрой Баше. Для неё существует следующая выигрышная стратегия: надо брать столько спичек, чтобы осталось количество, кратное трём. И тогда, если количество спичек вначале было кратно трём, то выиграет второй игрок, иначе – первый. Проанализируем нашу игру. Если спичек меньше 1000, то надо придерживаться выигрышной стратегии игры Баше. Если спичек 1000, то выиграет первый игрок, сразу забрав их все. Но он может взять и одну спичку, тогда останется 999 спичек и он тоже выиграет. Если спичек 1001, то первый игрок, взяв две спички, сводит задачу к своему выигрышу. Если спичек 1002, то все варианты взятия спичек первым игроком приводят к его проигрышу. Дальнейший анализ показывает, что если один из игроков берёт 1000 спичек, то другой игрок, взяв одну или две спички, сводит игру к выигрышной позиции. Таким образом, в нашей игре оказывается такая же выигрышная стратегия, как и в игре Баше.

Программа на Паскале

var n : integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(n); if n mod 3=0 then write(2) else write(1); close(output)

end.

Программа на С