Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

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

(Время: 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

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Олимпиадные задачи по программированию, 2006
 Тренировка 1
 Тренировка 2
 Тренировка 3
 Тренировка 4
 Тренировка 5
 Тренировка 6
 Тренировка 7
 Тренировка 8
 Тренировка 9
 Тренировка 10
 Тренировка 11
 Тренировка 12
 Тренировка 13
 Тренировка 14
 Тренировка 15
 A. Диалог компьютеров
 B. Бросание кубика
 C. Игра с монетами
 D. Бассейн реки
 E. Ближайшее число
 F. Прямоугольное деление

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru