Задача Идем к ним?
«У крота и землеройки имеется [latex]n[/latex] зёрен чего-то вкусного. Они по очереди съедают любое количество зерен, но не более половины оставшегося количества. Можно съедать только целое число зёрен. Если игрок не может сделать очередной ход, то он считается проигравшим и ему приходится бежать в магазин за следующей порцией вкусных зёрен. На каждом шаге можно съедать не более [latex]m[/latex]-й части оставшихся зёрен. Составьте программу, которая определяет величину первого выигрышного хода по заданным числам n и m. Если выигрышного хода нет, то нужно вывести [latex]-1[/latex].»
Анализ задачи:
- Первыми в голову приходят методы решения, основанные на полном переборе или на поиске производящей функции (к примеру, для [latex]m = 2[/latex] все позиции [latex]n = 2^{k}-1[/latex] — проигрышные), но количество стратегий растет достаточно быстро, а выделение закономерностей в рекурсивных последовательностях — задача нетривиальная. Следовательно, имеет смысл продолжить анализ, но уже с применением теории игр.
- Предложенная игра представляет собой версию игры ним. Отличие в том, что множество объектов одно, а количество допустимых на данном шаге ходов зависит от ситуации на игровом поле.
- Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.
- Выигрышные позиции отличаются только расстоянием до проигрышной для противника (в зернах), следовательно, можно воспользоваться выигрышно-проигрышным разбиением позиций и ввести соответстенные характеристики позиций: [latex]\left\{ 1, -1 \right\}[/latex].
- Если все позиции, в которые можно попасть из данной, являются выигрышными для противника (при условии, что он не играет в поддавки), считать её проигрышной.
Алгоритм решения:
- Построение базы анализа: позиция [latex]n = m[/latex] — выигрышная (единственным доступным ходом мы заканчиваем игру), следовательно, [latex]n = m + 1[/latex] — проигрышная.
- Если на расстоянии [latex]\left\lfloor \frac {step}{m} \right\rfloor [/latex] от текущей позиции [latex]step[/latex] все значения равны [latex]1[/latex], пометить [latex]step[/latex] как [latex]-1[/latex]. В противном случае пометить как [latex]1[/latex].
- Если значение для [latex]step = n-1[/latex], то вывести на экран [latex]-1[/latex]. В противном случае вывести расстояние до ближайшей проигрышной для противника позиции.
Результаты тестирования:
Для всех [latex]n[/latex] при [latex]m = 2[/latex] программа предсказуемо выдает последовательность проигрышных ходов при [latex]n = 2^{k}-1[/latex].
На малых значениях [latex]n[/latex] при [latex]m > 2[/latex] установлена корректность алгоритма.
| n | m | Результат |
| 7 | 2 | -1 |
| 8 | 2 | 1 |
| 10 | 3 | 3 |
| 7 | 3 | -1 |
| 12 | 4 | 2 |
| 10 | 4 | -1 |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/*Решение WoW_3 при помощи выигрышно-проигрышного разбиения позиций*/ #include <iostream> using namespace std; int main() { int n; cin >> n; //количество зерен int m; cin >> m; //часть, которую можно съесть за ход int result[n + 1]; //массив значений for(int i = 0; i < m + 1; i++) result[i] = -1; //все позиции с n = [0; m) - проигрышные int take_to_win = 0; //расстояние до ближайшей выигрышной позиции for(size_t step = m; step < n + 1; step++) //заполнение массива result[] { bool good = false; //есть ли возможность перейти на выигрышную позицию из данной //проверка всех позиций, в которые можно попасть за ход for(int i = step - 1; i >= step - step / m && !good; i--) { if(result[i] == -1){ //если выигрышная позиция достижима good = true; //уведомить об этом программу take_to_win = n - i; //зафиксировать расстояние до позиции } } if(good) result[step] = 1; //если возможно, пометить позицию как выгрышную else result[step] = -1; //иначе пометить как прогрышную } if(result[n] == 1) //вывести на экран оптимальное количество зерен на первом шаге cout << take_to_win << endl; else //или указать, что позиция проигрышная cout << -1 << endl; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.*; import java.io.*; import java.math.*; class Ideone { public static void main(String args[]) { Scanner in = new Scanner(System.in); int n = in.nextInt(); //количество зерен int m = in.nextInt(); //часть, которую можно съесть за ход int[] result = new int[n-m+1]; //массив значений for(int i = 0; i < n-m+1; i++) result[i] = 0; result[0] = 1; //в позиции n = m следуте взять одно зерно и выиграть result[1] = -1; //в позиции n = m + 1 выиграть нельзя int takeToWin = 0; for(int step = m+1; step < n+1; step++){ boolean good = false; //есть ли возможность перейти на выигрышную позицию из данной //проверка всех позиций, в которые можно попасть за ход for(int i = step-m; i >= ((step - step/m)-m) && !good; i--){ if(result[i] == -1){ //если выигрышная позиция достижима good = true; //уведомить об этом программу takeToWin = n-m-i; //зафиксировать расстояние до позиции } } if(good) result[step-m] = 1; //если возможно, пометить позицию как выгрышную else result[step-m] = -1; //иначе - пометить как проигрышную } for(int i = 0; i < n-m+1; i++) //вывод типа позиции System.out.println(i+m+":\t"+result[i]); if(result[n-m] == 1) //вывести на экран оптимальное количество зерен на первом шаге System.out.println(takeToWin); else //или указать, что выигрышных ходов нет System.out.println(-1); } } |
Детали реализации:
Для хранения характеристик позиций использован динамически объявляемый массив (VLA — Variable Length Array). Для упрощения анализа использована булева переменная [latex]good[/latex].При решении применялись методы динамического программирования.
Протестировать работу программы можно по ссылке: http://ideone.com/5nmDxl.
Реализация на Java: http://ideone.com/D5R49n