Задача на теорию игр

Рейтинг: 2Ответов: 1Опубликовано: 06.01.2015

В начальный момент времени Снарк находится в точке прямой с целой неотрицательной координатой X. За ход он может оказаться в любой точке с целой координатой Y при условии, что |X-Y| <= S. Кроме того, Снарк не любит булочки, поэтому он никогда не прыгнет в клетку, где одна из этих противных штук лежит. Булочник не хочет, чтобы Снарк попал домой. После каждого хода Снарка Булочник может положить булочку в любую точку прямой при условии, что это не начало координат (дом Снарка) и в этой клетке нет Снарка. Определите, сможет ли Булочник помешать Снарку оказаться дома. Изначально в некоторых клетках лежат булочки.

Входные данные
В первой строке задаются целые числа 0 <= X < 10000, 0 < S <= 100 и 0 <= N < max(X-1, 0) - количество булочек, которые уже лежат на прямой. Далее идут N различных чисел 0 < bi < X - координаты точек, где лежит гадость.

Выходные данные
Выведите "YES", если Булочник сможет реализовать свои грязные планы, "NO" - если при любых действиях врага Снарк сможет припрыгать домой.

Ясно, что задача по теории игр. Подскажите идею решения (готовая программа мне не нужна, так как хочу сам написать).

алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Снарк хочет сделать минимальное число шагов, чтобы добраться до цели.

В каждом состоянии можно посчитать, какие конкретно шаги при такой стратегии он сделает. И через сколько шагов он окажется там или сям.

Это число шагов — число булок, которые успеет расставить Булочник.

Двигая «рамку» длиной в S от 1 до Снарка, для каждого ее положения можно посчитать недостающее число ходов для закрытия (построения сплошной преграды).

Сопоставляя недостающее число ходов с тем, как скоро там окажется Снарк, можно найти, или не найти решение.

Вряд ли тут стоит усложнять стратегию до «замедления» Снарка где-то загодя.. Эти же ходы лучше потратить непосредственно на строительство преграды, как мне поверхностно кажется.