H. Холодильник продолжает умничать
Задачу добавил: alef
Успешно сдано решений: 6
Ограничение по памяти: 256 Мб
Министр экономики Калистрат новую функцию холодильника в целом одобрил. Но заметил, что в любых закупках важна регулярность и планирование. Следить за сроками годности и разнообразием йогуртов важно, но надо доработать функцию, чтобы можно было закупать йогурты на нужное количество дней.
В магазине есть видов йогуртов. Для каждого вида йогурта известен срок годности, записанный как количество дней, в течение которых этот йогурт ещё можно съесть. Если срок годности — значит, йогурт надо непременно съесть сегодня, если срок годности — то йогурт можно съесть сегодня или завтра, и т.д.
Царь Пантелеймон съедает один йогурт в день. Закупить йогурты нужно на ближайших дней. Царь не против, чтобы в течение этих дней он съел несколько одинаковых йогуртов. Однако он хочет, чтобы количество йогуртов одного вида, которое он съест в течение этих дней, было минимально возможным. Кроме того, царь желает, чтобы при соблюдении этого условия количество различных видов йогуртов в закупке было максимально возможным.
Ваша задача — определить, сколько и каких йогуртов следует приобрести, чтобы выполнить требования царя.
Примечание. По крайней мере один вид йогуртов имеет срок годности, позволяющий съесть его в последний из дней.
В первой строке содержатся целые числа и — количество видов йогуртов в магазине и количество дней, на которые следует закупить йогурты.
Во второй строке содержится целых чисел , — срок годности йогурта вида .
Гарантируется, что хотя бы один йогурт имеет срок годности, позволяющий съесть его в последний из дней.
В первой строке выведите два целых числа: максимальное количество йогуртов одного вида и количество разных видов йогуртов в списке.
Во второй строке выведите чисел — виды йогуртов в том порядке, в котором их следует съесть.
Если существует несколько вариантов ответа, выведите любой из них.
11 14 3 2 0 8 11 17 2 8 2 8 4
3 10 3 7 2 1 11 4 10 4 8 5 6 5 6 6
Поясним приведённый пример.
Как можно видеть, приходится приобрести одинаковых йогурта вида . Обойтись двумя одинаковыми йогуртами не получится: начиная со дня мы можем использовать только два вида йогуртов: и , а в дни и у нас и вовсе нет иных вариантов, кроме йогурта вида .
Добиться большего количества использованных йогуртов, нежели , не получится. Как можно видеть, дважды повторяется лишь йогурт , но заменить его можно разве что йогуртами вида , вида и уже упоминавшимися вида и вида : все остальные ко дню не будут иметь подходящий срок годности.
Заметим, что этот ответ не является единственным. Например, вместо йогурта вида , вида или вида можно поместить в итоговый список йогурт вида .