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

Задача . Gangs of Instanbull_Cowstantinople


Задача

Темы: Жадный алгоритм

Коровы сформировали банды, пронумерованные от 1 до M.
Теперь эти банды борются за контроль над большим пастбищем.
Каждую минуту одна корова идет в поле. Если это поле пустое, считается, что ее банда взяла контроль над ним. Если поле уже под контролем этой банды, то корова просто начинает на нем пастись. Иначе возникает конфликт между новой коровой, и той коровой из другой банды, которая там паслась.
В результате этого конфликта обе коровы "аннигилируются" (то есть выходят из своих банд и покидают это поле). Поле становится пустым и бесконтрольным. Никакая банда его не контролирует.
Беси знает сколько коров в каждой банде. Беси хочет чтобы ее банда контролировала поле после завершения конфликта.
Помогите Беси определить, может ли ее банда (номер 1) контролировать поле в конце.
Если это возможно, Беси хочет знать максимальное количество коров из ее банды, которое может остаться на поле в конце.
Выведите это количество и лексикографически раннюю перестановку коров, которая приведет к этому числу.
Перестановка X называется более ранней чем перестановка Y, если есть некоторое k, для которого X[k] < Y[k] и X[i]=Y[i] для всех i < k.
PROBLEM NAME: gangs
Формат входных данных
* Строка 1: N (1 <= N <= 100) и M (1 <= M <= N) разделенные пробелом. N - общее число коров во всех бандах. M - общее число банд.
* Строки 2..1+M: (1+i)-ая строка указывает количество коров в банде i. В каждой банде есть хотя бы одна корова.
Формат выходных данных
* Строка 1: Выведите YES на одной строке, если банда Беси может взять контроль над полем, иначе выведите NO.
* Строка 2: Если банда Беси сможет взять контроль над полем выведите здесь максимальное количество коров, которые там будут пастись после окончания конфликта.
* Строки 3..2+N: На (i+2)-ой вывести индекс банды коровы, которая должна появится на i-ой минуте на поле в лексикографически ранней перестановке которая обеспечит максимальное количество коров в поле после конфликта.
Примечание
Только одна корова из банды Беси может остаться на поле
Примеры
№Входные данныеВыходные данные
1 
5 3
2
1
2
 
YES
1
1
3
2
3
1
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

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


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

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