Как определить, что игроки играют оптимально?

[k1r1ch]

Вот задачка:

Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.

Входные данные

В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.

Пример

INPUT.TXT/OUTPUT.TXT
4
3 2 5 4 / 1
-----------------------------------
6
5 5 5 5 5 5 / 0
-------------------------------------
9
2 1 3 2 9 1 2 3 1 / 2
--------------------------------------
10
2 5 3 12 4 6 13 7 1 3 / 1

Я тут криво оформил - она здесь есть, если что.
Вопрос - как определить, что игроки играют оптимально?
Я могу получить список всех решений, но какое из них оптимальное - для меня загадка...

[LeBron]

Оптимальное решение - не совсем верное определение для теории игр. Оптимальная стратегия - стратегия, позволяющая достичь оптимального для даного игрока результата. Проще говоря, Ваше задание - определить исход игры, если оба противника будут действовать наилучшим образом.
Я бы не советовал сейчас такое решать. Вы готовитесь к районной олимпиаде, а на районной олимпиаде не бывает настоящих задач. Это - задача. Не особо сложная, но задача. А Вам сейчас для наилучшего результата надо набить руку на кодинговых упражнениях.
З.Ы. надо будет в ближайшем будущем ее здать, а то эту задачу я еще не написал

[k1r1ch]

Ну если можно, просто объясните решение (охота знать сам принцип)

[LeBron]

Я бы ее писал 2-д динамикой, похожей на Шпрага-Гранди таблицу. Тоесть снизу вверх определеям для каждой позиции значения игровой функции подстроки, а потом уже динамим эту таблицу.

[LeBron]

Все, написал, сдал, прошло. 2-д динамика показала
Pascal
Accepted
*
0,072
988 Кб
Следовательно, я был прав, и такое решение подходит. Этой задачей закрыл первую страницу, из задач с номерами 1-50 она у меня была последней не сданой, как выяснилось (просто обычно сортирую по сложности, а не по номеру).
После сдачи сел обсуждение читать - согласен с постами там, задача действительно несколько раз проскакивала на ИОИ. Отгуглил старые ИОИ, если хотите понять само задание более правильно и четко, то взгляните на IOI'96 Day 1
Problem 1: A Game. Там суть более доступно выложена, чем в варианте, который Сергей Николаевич написал для АСМП.
По поводу сложности задачи, хочу сказать, что она и сейчас не являеться столь простой для большинства новичков и кодеров "ниже среднего уровня" (как я уже говорил раньше, повторю еще раз "для закрепления"), хотя программирование и пошло далеко вперед, эта задача, которая была симплом (и одновременно сэмплом) межнара школьников по информатике 13 лет назад, и сейчас еще могла бы быть первой задачей ВсеРоса (что бы у всех были хоть какие-то баллы, на уровне ВсеРоса ее полностью или почти полностью сделает наверно бОльшая половина участников) или довольно неплохой (выше средней сложности) задачей на соревнованиях на 1 уровень ниже.