eolymp
bolt
Try our new interface for solving problems
Məsələlər

Прохождение коридора

Прохождение коридора

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Как мы уже знаем, в игре Пети есть коридор, разбитый на N участков. Предположим, что каждый из участков покрыт некоторым числом единичных плит. Персонаж в игре, которым управляет игрок, находится в начале коридора перед первым участком и может пройти по этому участку, потратив на это один ход. Если на нем была хотя бы одна плита, то после прохождения по участку одна плита с него исчезает. Таким образом количество плит уменьшится на 1. Если же на участке не было ни одной плиты, то персонаж погибает, соответственно игрок теряет одну жизнь, после чего на этом участке появляется K новых плит, а у игрока появляется новый персонаж в начале коридора. Если игрок удачно прошел участок и не погиб, то он оказывается перед следующим участком, который он может пройти, если на нем есть хотя бы одна плита, или погибнуть, если плит нет. В любом случае потребуется один ход. Разрешается лишь движение вперед. Считается, что игрок прошел коридор, если его персонаж в какой-то момент окажется в конце коридора, то есть пройдет последний участок и не погибнет на нем. Помогите игроку узнать, сколько потребуется жизней и ходов для прохождения коридора.

Giriş verilənləri

В первой строке даны два целых числа N и K (1N10000, 1K100) – длина коридора и количество появляющихся после гибели персонажа плит на участке. Во второй строке записано N целых чисел, каждое из которых определяет количество плит, которыми покрыт изначально соответствующий участок. Эти числа могут принимать значения от 0 до K включительно.

Çıxış verilənləri

Выведите сколько жизней потеряет игрок и сколько ходов он сделает до того момента, когда его персонаж попадет в конец коридора.

Nümunə

Giriş verilənləri #1
3 3
2 2 2
Çıxış verilənləri #1
0 3
Müəllif Антон Лунёв
Mənbə Зимняя школа, Харьков 2011, День 6