Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

















Игра с монетами

(Время: 1 сек. Память: 16 Мб Сложность: 47%)

Гриша и Дима играют в следующую игру: они разложили однокопеечные монетки в стопки (в разных стопках может быть различное количество монет), а стопки расположили на столе перед собой в ряд слева направо. Затем Гриша и Дима по очереди делают ходы. На каждом ходе один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается.

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

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

Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1 ≤ N ≤ 180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке – не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 ≤ K ≤ 80). Все числа в строке разделены пробелом.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13  4 9 1  314
24  1 2 2 7  35
35  3 4 8 1 7  218

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки] [Решение]


 
     
Югорский НИИ ИТ, Югорский ФМЛ