Школа179: Правила игры в спички

https://server.179.ru/wiki     редакция: 19.08.2016 23:54:08
Информатика/Архив/2010/ИграВспички/Правила
Правила игры. В игру играет два человека, которые ходят по очереди. На столе лежит 50 спичек. Первым ходом можно взять одну или две спички. На каждом последующем ходу игрок может взять любое число спичек, не меньшее 1 и не более чем в два раза, чем взял предыдущий игрок. Тот, кто возьмет последнюю спичку, выиграл.

Вот пример партии:

Было – 50 спичек
1 игрок взял 1 спичку, осталось 49
2 игрок взял 2 спички, осталось 47
1 игрок взял 3 спички, осталось 44
2 игрок взял 6 спичек, осталось 38
1 игрок взял 11 спичек, осталось 27
2 игрок взял 8 спичек, осталось 19
1 игрок взял 3 спички, осталось 16
2 игрок взял 5 спичек, осталось 11
1 игрок взял 3 спички, осталось 8
2 игрок взял 2 спички, осталось 6
1 игрок взял 1 спичку, осталось 5
2 игрок взял 1 спичку, осталось 4
1 игрок взял 1 спичку, осталось 3
2 игрок взял 1 спичку, осталось 2
1 игрок взял 2 спички, осталось 0

Протокол такой партии можно записать в следующем виде:

1 50
1 49
2 47
3 44
6 38
11 27
8 19
3 16
5 11
3 8
2 6
1 5
1 4
1 3
1 2
2 0

Обратите внимание, в начальной позиции записано число 1, обозначающее ход предыдущего игрока, которого на самом деле не было. Это сделано для того, чтобы обозначить, что первым ходом игрок может взять 1 или 2 спички.

Напишите программу, которая играет в эту игру.
Программа получает на вход два числа: количество спичек, которое взял предыдущих игрок \(d\) и количество спичек на столе \(n\). Числа натуральные, не превосходят 100. Программа должна вывести два числа: количество взятых спичек \(d_1\) и количество оставшихся спичек \(n_1\), при этом \(1\le d_1\le 2d\), \(n_1=n-d_1\), \(n_1 \ge 0\).

Пример
ВходВыход
1 501 49
6 3811 27
1 22 0

Программа должна тратить не более 1 секунды на ход. Постарайтесь придумать наилучшую стратегию для этой игры.