Codeforces Round 377 (Div. 2) |
---|
Закончено |
Недавно Поликарпу наконец купили собаку, которую он назвал Корменом. Теперь у Поликарпа появилось так много хлопот! Например, Кормен очень любит прогулки.
Опытным путем Поликарп установил, что псу требуется не менее k прогулок суммарно за любые два последовательных дня, чтобы чувствовать себя отлично. Например, если k = 5 и вчера Поликарп гулял с собакой 2 раза, то сегодня он должен будет погулять не менее 3-х раз.
Поликарп проанализировал все свои дела на ближайшие n дней вперед и составил последовательность из n целых чисел a1, a2, ..., an, где ai — количество прогулок с собакой, которые он совершит в i-й день, исполняя все свои дела во время них (например, ему надо сходить в магазин, выбросить мусор и так далее).
Помогите Поликарпу определить наименьшее количество прогулок сверх намеченных, которые ему нужно совершить за n дней для того, чтобы Кормен чувствовал себя отлично на протяжении всех n дней. Вы можете считать, что в день до первого и в день после n-го Поликарп выгуливал Кормена ровно по k раз.
Напишите программу, которая найдет наименьшее количество дополнительных прогулок и соответствующее расписание — последовательность целых чисел b1, b2, ..., bn (bi ≥ ai), где bi обозначает суммарное количество прогулок в i-й день.
В первой строке входных данных записаны два целых числа n и k (1 ≤ n, k ≤ 500) — количество дней и минимальное суммарное количество прогулок Кормена за любые два подряд идущих дня.
Во второй строке записаны целые числа a1, a2, ..., an (0 ≤ ai ≤ 500) — количество прогулок Кормена в i-й день, которые уже запланированы Поликарпом.
В первую строку выведите наименьшее дополнительное количество прогулок, которые нужно совершить за n дней для того, чтобы Кормен всегда чувствовал себя отлично.
Во вторую строку выведите n целых чисел b1, b2, ..., bn, где bi — суммарное количество прогулок в i-й день в соответствии с найденным решением (ai ≤ bi для всех i от 1 до n). Если решений несколько, разрешается вывести любое из них.
3 5
2 0 1
4
2 3 2
3 1
0 0 0
1
0 1 0
4 6
2 4 3 5
0
2 4 3 5
Название |
---|