|
Игра - 2
(Время: 1 сек. Память: 16 Мб Сложность: 45%)
Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
3 2 5 4 | 1 |
| 2 | 6
5 5 5 5 5 5 | 0 |
| 3 | 9
2 1 3 2 9 1 2 3 1
| 2 |
| 4 | 10
2 5 3 12 4 6 13 7 1 3 | 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
