Игра в спички

Учащиеся гимназии №1.
Предлагаем Вам принять участие в битве программ
или стать зрителем данной игры.

Наверное большинству известно идея «битвы программ»: есть задача, чаще всего игра, не очень сложная, чтобы её можно было запрограммировать школьникам, и не всегда с очевидным алгоритмом (чтобы было интересно). Необходимо двум (или более) участникам написать программу делающую всего один ход в этой игре (т.е. программа получает текущую обстановку, обрабатывает её по оригинальному алгоритму и совершает один единственный ход). Таким образом запуская по очереди две разные программы (для этого можно написать третью программу, которая будет при этом проверять правильность-честность хода) и получаем что две программы играют друг с другом.

Правила игры

В игру играет два человека, которые ходят по очереди. На столе лежит 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. Программа должна вывести два числа: количество взятых спичек d1
и количество оставшихся спичек n1, при этом 1 <=d1<=2d, n1=n-d, n1>=0.

Пример

Вход Выход
1 50 1 49
6 38 11 27
1 2 2 0

 

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

Приносите исходные файлы, написанные на С++ или Pascal.

Битва на определение «лучшей» программы состоится во вторник,  ориентировочно в 14.00, в кабинете информатики.

P.S. Модуль для поочередного запуска программ соперников, анализа честности хода, а также визуализации процесса подготовлен учеником 11Б класса Плоткиным Артёмом.

Поделиться в соц. сетях

Опубликовать в Facebook
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники
Опубликовать в Яндекс

Оставить комментарий

Вы должны войти, чтобы оставлять комментарии.