Задача Идем к ним?
«У крота и землеройки имеется [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
«Эффективный поиск выигрышного хода можно провести при помощи функции Шпрага-Гранди.» — действительно можно!
«область значений функции можно сузить до двух элементов: { 1, -1 }.» — но тогда это уже не функция Шпрага-Гранди!
То что Вы делаете, называется выигрышно-проигрышный анализ или же «выигрышно-проигрышное разбиение» позиций (даже специально нашел этот термин, например, здесь ).
А функция Шпрага-Гранди — это более тонкий механизм, который понадобится Вам для задачи «Ним, нимберы и функция Шпрага-Гранди» — которую я наконец-то доделал.
По решению есть одно существенное замечание: для того чтобы определить, является ли позиция step выигрышной, в строке 14 Вы пишете for(int i = step; ... ; el--) и затем проверяете значение sprague[i] — т.е. изначально sprague[step], которая еще не заполнена (в ней хранится мусор) — ее не надо проверять, минимальный ход — взять 1 зерно, пропускать ход нельзя. Ну и el— явная опечатка, наверное имелось в виду i— (el в программе больше не участвует). Последний вариант программы обязательно проверяйте на тестах, если все работало раньше, то не факт, что будет работать после изменений.
Еще в пункте «3. Если значение функции Шпрага-Гранди …» небольшая опечатка в формуле (формула расщепилась на две почему-то).
В остальном претензий нет, все четко описано и реализовано. Вы используете метод динамического программирования для анализа позиций игры (последовательное вычисление элементов массива, используя предыдущие значения).
Доработал отчет и подкорректировал код программы.
Регрессионное тестирование выполнил, результаты остались прежними.
Спасибо за замечания и уточнения, особенно за статью.
Еще раз обращу внимание: for(int i = step; i >= step - step / m && !good; i--) Вы начинаете перебор возможных ходов с хода «взять ноль зерен» — который однако невозможен. Программа работает только потому, что в том мусоре, который хранится изначально в массиве int result[n + 1]; отсутствуют значения -1.
Добавил очистку массива от мусора.
Проблему понял. Теперь анализ начинается с позиции n = m, из которой возможно сделать ход в одно зернышко.
Ну Вы даете! Я всего-то имел в виду, что нужно исправить строчку for(int i = step; i >= step - step / m && !good; i--) на for(int i = step-1; i >= step - step / m && !good; i--), так как из позиции step можно перейти в позиции step-1 (взять 1 зерно), step-2 (взять 2 зерна), …, step — step / m (взять число зерен step/m, т.е. одну m-тую от количества зерен округленное вниз). Вы же переделали всю программу кардинально.
Теперь по пунктам:
1. очистка массива от мусора — необязательна, если правильно реализовать программу, то мусор не используется; но эта очистка и не мешает — будем считать что сделано на всякий случай.
2. Вы решили экономить память — на m ячеек меньше. Ладно. Но
2а) страдает наглядность. Вам нужно вычитать m из индекса. Но это еще полбеды, хуже что Вы вычитаете индексы по разному: result[step - m] — логично, i = step - m, … result[i] — другой способ, а ведь суть i та же самая, что и step — номер позиции, оно же число зерен.
2б) i >= ((step - step / m) - m) && !good — а тут вообще скрытый подводный камень, так как ((step — step / m) — m) вполне себе оказывается меньше нуля. А нет, я неправ, ((step — step / m) — m) вроде как всегда больше либо равно нуля, но мне пришлось крепко задуматься, чтобы догадаться до этого.
2в) теперь у Вас не учтен случай n
Привел к исходному и виду и изменил строку 17. Надеюсь, теперь я вас понял правильно. Спасибо за подробный анализ.
В прошлом комментарии 2в) должен быть: теперь у Вас не учтен случай n меньше m, кстати такой тест желательно добавить. Нужно тестировать крайние случаи, а не только «нормальные».
Но из-за того что меньше было значком, конец предложения пропал, а я и не заметил.
Так что лучше добавить тест, где n меньше m. Он у Вас должен пройти в таком варианте … почти … в строчке 10 переменная i изменяется от 0 до m, включительно (кстати, почему до m? ведь m — уже выигрышная — это я тоже не доглядел в первый раз). А если n меньше m, то заполняется больше элементов массива, чем выделено памяти под массив.
Очень здорово, что на первом курсе уже разбираются такие задачи.
Можно данную задачу решить не за O(n^2 / m), а за O(n). Если Вас заинтересует, предлагаю подумать, как это можно сделать.
Следующий этап — за O(log n).
Засчитана Java-версия, 10 баллов.