Задача H. Конкильони
Задачу добавил: alef
Успешно сдано решений: 5
С тех пор, как Кеша научился готовить, его друзья часто заходят к нему в гости. Вот и сегодня ему позвонили товарищи, и сказали, что через четверть часа заглянут "на огонек". Кеша решил сварить конкильони. Конкильони - это такие большие макаронные изделия в форме ракушек. Их советуют фаршировать морепродуктами, но Кеше больше нравится начинка из сыра Фета с грецкими орехами. Как раз можно успеть сделать ее за 10-15 минут, пока макаронные изделия варятся.А еще очень хороши с конкильони салатные листья - на них выкладывают еще горячие ракушки с начинкой.
Кеша положил на каждую тарелку по салатному листу и уже на этот лист положил конкильони - так, чтобы они полностью помещались на листе. Поскольку листы салата имеют разные размеры, на тарелках получилось разное количество конкильони.
Он едва успел разложить все ракушки, как пришли гости. Их не надо было долго уговаривать сесть за стол. Первый из вошедших довольно быстро нашел тарелку с тем количеством конкильони, которое он хотел съесть и взял ее. Так же поступил и второй гость. Однако третий уже был разочарован: ни на одной тарелке он не увидел желаемого количества ракушек. Поэтому (с разрешения хозяина, разумеется) каждый очередной гость поступал следующим образом. Он выбирал тарелку с количеством конкильони, наиболее близким к желаемому (пусть, для определенности, минимальная разница составляла D штук); при этом если находилась тарелка, на которой было больше желаемого количества ракушек на D штук, и тарелка, на которой было меньше желаемого ракушек на D штук, он выбирал первую. Далее, если была выбрана тарелка, на которой было больше конкильони, нежели хотел съесть гость, он откладывал "лишние" конкильони на ту из оставшихся тарелок, где их было меньше всего. Если же была выбрана тарелка, где конкильони недоставало, то среди оставшихся тарелок гость выбирал ту, на которой было больше всего конкильони, и забирал с нее столько, сколько требовалось для достижения желаемого количества. Если на тарелке с самым большим количеством конкильони не хватало для достижения желаемого количества, гость забирал оттуда все, а затем перекладывал конкильони со следующей тарелки с максимальным их количеством - и так до тех пор, пока не набирал столько, сколько нужно.
Последним тарелку взял Кеша и проделал то же самое.
Ваша задача - определить следующие величины:
- сколько суммарно было произведено перекладываний ракушек
- сколько осталось тарелок с конкильони, и какое количество ракушек осталось на этих тарелках
Формат входного файла input.txt
Первая строка - целые числа T и G через пробел - количество тарелок и гостей (1 < G+1 < T <= 50000).
Вторая строка - T целых чисел Ki, соответствующих количеству конкильони, лежащих на тарелках (1 <= Ki <= 10000, i = 1, 2, ..., T)
Третья строка - G+1 целое число Wj (1 <= Wj <= 10000), соответствующих количеству конкильони, которые желают съесть гости с соответствюущими номерами. Последнее число соответствует количеству конкильони, которое хочет съесть Кеша.
Гарантируется, что количество конкильони таково, что желания всех гостей и Кеши будут выполнены.
Формат выходного файла output.txt
Первая строка - целое число R - общее количество конкильони, которые гости перекладывали
Вторая строка - целое число N - количество оставшихся непустыми тарелок, затем N целых чисел через пробел в порядке неубывания - количества конкильони, оставшихся на тарелках.
Пример входного файла
13 4
3 8 10 4 10 3 14 1 1 3 5 2 3
11 11 10 18 15
Пример выходного файла
26
2 1 1
Рецепт
Собственно конкильони надо отварить до готовности (10-15 минут), они должны оставаться достаточно твердыми. Варить их надо в большом количестве воды.
Для начинки (на 500 г - пачку - конкильони) понадобится 300 граммов мягкого сыра (фета, но можно обойтись и творогом, но тогда, возможно, надо будет добавить соли), грецкие орехи - по вкусу. Их надо порубить и добавить в растертый сыр. Рекомендуют также добавлять в растертый сыр сливки (33% жирности, 200 мл).
Начиненные конкильони укладывают на любые салатные листья. Можно полить их маслом.