Через неделю стартует первый этап ACM ICPC в Украине. В связи с этим, я просматривал задачи и результаты прошлых лет, и наткнулся на одну интересную задачу с первого этапа позапрошлого года.

Примечательна она тем, что на контесте по ней было 15 удачных посылок (сравнительно не самое малое число), однако из первых 60-ти команд-участниц, ни одна команда эту задачу так и не сдала. То-есть в основном её порешали весьма слабые команды, а сильные не осилили)

Условие задачи весьма простое: Есть перестановка из n чисел. Два игрока по очереди стирают по одному числу, пока не останется два числа. Какое из оставшихся чисел меньше, тот игрок и победил. Ну и стандартный вопрос: кто победит при оптимальной игре?

Вот собственно полное условие задачи.

Сам я так и не придумал, как решать эту задачу. Поэтому и спрашиваю здесь.