Решение задачи "Кормен — лучший друг человека" с Codeforces

Без пояснения   Просмотров: 10


Недавно Поликарпу наконец купили собаку, которую он назвал Корменом. Теперь у Поликарпа появилось так много хлопот! Например, Кормен очень любит прогулки.

Опытным путем Поликарп установил, что псу требуется не менее k прогулок суммарно за любые два последовательных дня, чтобы чувствовать себя отлично. Например, если k = 5 и вчера Поликарп гулял с собакой 2 раза, то сегодня он должен будет погулять не менее 3-х раз.

Поликарп проанализировал все свои дела на ближайшие n дней вперед и составил последовательность из n целых чисел a1, a2, ..., an, где ai — количество прогулок с собакой, которые он совершит в i-й день, исполняя все свои дела во время них (например, ему надо сходить в магазин, выбросить мусор и так далее).

Помогите Поликарпу определить наименьшее количество прогулок сверх намеченных, которые ему нужно совершить за n дней для того, чтобы Кормен чувствовал себя отлично на протяжении всех n дней. Вы можете считать, что в день до первого и в день после n-го Поликарп выгуливал Кормена ровно по k раз.

Напишите программу, которая найдет наименьшее количество дополнительных прогулок и соответствующее расписание — последовательность целых чисел b1, b2, ..., bn (bi ≥ ai), где bi обозначает суммарное количество прогулок в i-й день.

Код

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,a[510],k,f=0;
	cin >> n >> k;
	cin >> a[0];
	for (int i=1; i<n; i++){
		cin >> a[i];
		if (a[i]+a[i-1]<k){
			f+=k-a[i]-a[i-1];
			a[i]=k-a[i-1];
		}
	}
	cout << f << endl;
	for (int i=0; i<n; i++){
		cout << a[i] << ' ';
	}
	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться