В начальный момент времени Снарк находится в точке прямой с целой неотрицательной координатой X. За ход он может оказаться в любой точке с целой координатой Y при условии, что |X-Y| <= S. Кроме того, Снарк не любит булочки, поэтому он никогда не прыгнет в клетку, где одна из этих противных штук лежит. Булочник не хочет, чтобы Снарк попал домой. После каждого хода Снарка Булочник может положить булочку в любую точку прямой при условии, что это не начало координат (дом Снарка) и в этой клетке нет Снарка. Определите, сможет ли Булочник помешать Снарку оказаться дома. Изначально в некоторых клетках лежат булочки.
Входные данные
В первой строке задаются целые числа 0 <= X < 10000, 0 < S <= 100 и 0 <= N < max(X-1, 0) - количество булочек, которые уже лежат на прямой. Далее идут N различных чисел 0 < bi < X - координаты точек, где лежит гадость.
Выходные данные
Выведите "YES", если Булочник сможет реализовать свои грязные планы, "NO" - если при любых действиях врага Снарк сможет припрыгать домой.
Ясно, что задача по теории игр. Подскажите идею решения (готовая программа мне не нужна, так как хочу сам написать).
Ответ
Снарк хочет сделать минимальное число шагов, чтобы добраться до цели. В каждом состоянии можно посчитать, какие конкретно шаги при такой стратегии он сделает. И через сколько шагов он окажется там или сям. Это число шагов — число булок, которые успеет расставить Булочник. Двигая «рамку» длиной в S от 1 до Снарка, для каждого ее положения можно посчитать недостающее число ходов для закрытия (построения сплошной преграды). Сопоставляя недостающее число ходов с тем, как скоро там окажется Снарк, можно найти, или не найти решение. Вряд ли тут стоит усложнять стратегию до «замедления» Снарка где-то загодя.. Эти же ходы лучше потратить непосредственно на строительство преграды, как мне поверхностно кажется.
Комментариев нет:
Отправить комментарий