Олимпиадный тренинг

Задача . Mooo Moo


Задача

Темы: Задача о рюкзаке

Фермер Джон совершенно забыл, сколько у него коров. Он хочет их пересчитать с помощью микрофонов на полях, на которых собираются его коровы, поскольку он может определить количество коров по уровню шума.
N полей ФД (1 <= N <= 100) организованы в ряд вдоль длинной прямой дороги. Каждое поле может содержать различные виды коров. Всего у ФД имеется B видов коров (1 <= B <= 20), и корова вида I шумит с уровнем V(i) (1 <= V(i) <= 100). Кроме того, уровень шума распространяется строго в одном направлении по следующему закону: Если в некотором поле уровень шума X, то в следующем поле этот уровень становится X-1, следующем за ним, X-2 и т.д.
По заданному уровню шума, зафиксированном на каждом из полей, определите минимально возможное количество коров у ФД.
Уровень зафиксированного шума на каждом из полей не более 100,000.
PROBLEM NAME: mooomoo
Формат входных данных
* Строка 1: Целые числа N и B.
* Строки 2..1+B: Строка i+1 содержит целое число V(i).
* Строки 2+B..1+B+N: Строка 1+B+i содержит суммарный уровень шума всех коров, мычащих в поле i.
Формат выходных данных
* Строка 1: Минимальное количество коров у ФД, или -1, если не существует конфигурации коров, соответствующей входным данным


Примечание
Всего имеется 2 коровы вида #1 и 1 корова вида #2 на поле 2 и ещё есть 1 корова вида 1 в поле 4.


Примеры
№Входные данныеВыходные данные
1 
5 2
5
7
0
17
16
20
19
 
4
Статистика успешных решений по компиляторам
 Кол-во
С++1
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет