Элегантное решение задачи о спичках [спортивное программирование]

В этой статье будет описан способ решения одной не очень известной задачи спортивного программирования. Решение требует всего несколько строк кода и очень эффективно, однако требует объяснения.

Суть задачи

Для начала, прочтем текст (взят с informatics.mccme.ru):

Петя придумал новую игру. На стол кладется кучка из N спичек, и затем Петя с Ваней по очереди берут спички из кучки. Первым берет Петя, ему разрешается взять от 1 до K спичек. Затем игрок может взять любое количество спичек, не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Например, если N = 10, K = 5, то на первом ходу Петя может взять 1, 2, 3, 4 или 5 спичек, если Петя возьмет 3, то на следующем ходу Ваня может взять 1, 2, 3 или 4, и если Ваня возьмет 1, то Петя затем может взять 1 или 2, и т. д. Проигрывает тот, кто возьмет последнюю спичку.

Теперь Петя хочет рассчитать какое количество спичек он должен взять на первом ходу, чтобы выиграть при любой игре Вани. Помогите ему.

Важно заметить, что имеется ввиду нахождение всех возможных вариантов кол-ва спичек, при которых Петя победит.

Обычно подобные задачи решаются методом динамического программирования (то есть находим необходимые решения для кол-ва спичек < N, а затем, зная решения, решаем для N).

Однако конкретно эта задача имеет более элегантное решение.

Код (на языке С++)

#include <iostream>
#include <set>

using std::set;
using std::cin;
using std::cout;

int main() {
	int n, k;
	cin >> n >> k;
	set<int> ans;
	for (int i = 5; i <= 2 * n + 1; i *= 2) {
		if (n % i - 1 && n % i - 1 <= k) {
			ans.insert(abs(n % i - 1));
		}
	}
	if (!ans.empty()) {
		for (auto j: ans) std::cout << j << " ";
	} else {
		cout << "0";
	}
	return 0;
}

Если ваша первая реакция — это недоумение, то это нормально. Сейчас я попробую объяснить, что к чему.

Алгоритм

Суть алгоритма в том, чтобы у противника было всего 2 варианта:
1) оставить противнику ровно одну спичку
2) оставить противнику столько спичек, чтобы для выигрыша ему нужно было забрать больше, чем он может на данном ходе

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

1 2 3 4 5 6 7 8 9 10 11…

Теперь проанализируем, сколько спичек нужно взять первому игроку, если есть всего 1 спичка, всего 2 и т. д.

0 1 2 3 1 0 1 2 3 1 0… < — последовательность (1) (первая итерация)

То есть, для единицы первый игрок всегда проигрывает, для двойки ему нужно взять 1 спичку, чтобы выиграть, для тройки — 2, четверки — 3, для пяти нам следует «сослаться» на четвёрку, на которой оппонент гарантированно не сможет взять три спички. После этого последовательность повторяется.

Почему 6-ти и 11-ти соответствует 0?

Потому что на первой итерации мы полагаем, что наибольшие кол-во спичек, которые мы можем взять, меньше 5-ти.

Почему меньше 5-ти?

Потому что в последовательности (1) есть переход… 3 1 х…
х не может ссылаться на 3, потому что соперник сможет взять 2 + 1 = 3 спички. Единственный способ — «перепрыгнуть» порог… 3 1… и сослаться на самое начало, однако на первой итерации мы рассматриваем только «ближайшие» ссылки. Таким образом образовался цикл длинной 5.

Следует заметить, что длинна цикла зависит от того, насколько больше спичек может взять соперник.

Таким образом мы обнаружили периодическую последовательность, которая соответствует формуле |(n mod 5) — 1|. Но на самом деле мы можем ссылаться не только на ближайшее подходящее кол-во спичек, но и на другие. Чтобы убедиться в этом на практике достаточно в последовательности (1) предположить, что есть возможность взять до девяти спичек и построить новую последовательность, базируясь на изложенных рассуждениях:

0 1 2 3 1 5 1 2 3 1 0 1 2 3 1 5…

То есть теперь мы находим ссылки по модулю 10, и формула имеет вид |(n mod 10) — 1|.
Дальше тот же процесс нужно повторить по модулю 20, 40 и т.д., пока мы не убедимся, что не получим новых остатков (отсюда ограничения цикла 2 * n + 1).

P.S. Задача была предложена преподавателем на 2-ом курсе университета. Алгоритм придуман мной и моим соседом по комнате. Код протестирован на том же сайте, где было найдено условие.

Автор: Лунтик

Источник