Задача A. Фигурное программирование ≡

Условие

В математической школе появился новый вид соревнований — фигурное программирование. На этих соревнованиях каждому участнику предлагается одна простая задача, решение которой необходимо красиво оформить, причем важна именно красота оформления. Качество оформления оценивают N экспертов. Каждый из них выставляет оценку, которая представляет собой число от 1 до 6 в десятичной записи с двумя знаками после десятичной точки. Эти числа заносятся в протокол.

Известный школьный двоечник и хулиган Юкка не был допущен на это соревнование, и его заставили начисто переписывать протокол. Из плохих побуждений Юкка фальсифицировал итоговый протокол лучшего ученика Пекки, пропустив при переписывании некоторые K оценок из N. Для того чтобы все окончательно запутать, из оставшихся N−K оценок он стер одну минимальную и одну максимальную. По оставшимся оценкам эксперты подсчитали число A — средний балл Пекки.

Когда проделка Юкки открылась, директор школы решил его проучить. Для этого он предложил на основании A и черновика протокола с полным набором N оценок определить, какие именно оценки были пропущены при переписывании или стерты.

От страха Юкка забыл их. А Вы можете найти эти оценки?

Формат входного файла

Первая строка содержит 2 целых числа N и K. Числа N и K разделены пробелом. Во второй строке содержатся N разделенных пробелами вещественных чисел из черновика протокола. Каждое число дается с точностью до двух знаков после десятичной точки. В третьей строке содержится вещественное число A, округленное до двух знаков после десятичной точки. Гарантируется, что входные данные корректны, и их проверка не требуется.

Формат выходного файла

В произвольном порядке выведите K+2 оценки, которые не учитывались при подсчете A. Числа должны располагаться в первой строке файла, разделитель между числами — пробел. Если имеется несколько вариантов, выведите любой из них.

Ограничения

Примеры тестов

7 2
2.35 3.50 4.00 2.83 4.12 5.01 5.56
3.48

2.35 4.00 5.56 5.01

5 1
2.00 2.00 2.00 3.00 3.00
2.50

2.00 2.00 3.00

Задача B. Пекка развлекается ≡

Условие

Недавно у Пекки появилось новое развлечение. Он взял A₁ одинаковых карточек, на каждой из которых написана единица, A₂ карточек с двойками, …, A_N карточек с числом N. Его интересует, каким числом способов можно расположить все карточки в ряд так, чтобы в полученной последовательности любой карточке с числом k+1 предшествовала бы по крайней мере одна карточка с числом k, при k>0. Помогите Пекке, пожалуйста.

Пояснение

Возможные расстановки в примере: 1 1 2 2, 1 2 1 2, 1 2 2 1 — всего три расстановки.

Формат входного файла

В первой строке входного файла записано натуральное число N. Во второй строке — N разделенных пробелами натуральных чисел: A₁, A₂, …, A_N.

Формат выходного файла

В выходной файл необходимо вывести число различных способов расстановки карточек, соответствующих условию задачи.

Ограничения

Примеры тестов

2
2 2

3

Задача K. Посылка ≡

Условие

Почтовый поезд уже готов к отправлению, и тут рядом с платформой останавливается дилижанс, из которого выскакивает сам начальник почтового отделения. Он подбегает к поезду и вручает Бобу посылку. Боб заходит внутрь вагона и обнаруживает, что места на такую большую посылку уже точно не осталось. Свободна только одна маленькая полочка под самым потолком. Но начальник уверяет, что эту посылку просто необходимо доставить. Похоже, придется переставлять коробки с одной полки на другую. А ведь времени осталось так мало!

Согласно инструкции, Боб может действовать следующим образом: за одно действие он может взять коробку с некоторой полки и перенести ее на другую полку.

Для каждой полки известен максимальный вес коробки, которую можно на ней разместить. При этом, поскольку времени очень мало, Бобу нужно постараться освободить полку для вновь прибывшей посылки, совершив минимальное количество действий.

К сожалению, Боб не очень быстро соображает, так что вы очень поможете ему, если напишете программу, которая найдет для него нужный порядок действий.

Формат входного файла

На первой строке записано целое число n — количество полок в вагоне.

На второй строке содержатся n целых чисел c_i, разделенных пробелами. i-е из них задает максимальный вес предмета, который можно поставить на полку номер i.

На третьей строке задано n − 1 натуральное число w_i — веса коробок, стоящих на соответствующих полках (последняя полка изначально пуста).

В последней строке задан вес a новой посылки, которую требуется поставить.

Формат выходного файла

На первой строке выходного файла запишите минимальное число действий m, которое придется совершить Бобу.

На второй строке выведите описания этих действий — m − 1 натуральное число, задающие, предмет с какой полки перемещается на ту, которая свободна в текущий момент времени (последним действием ставится привезенная посылка). Если поставить посылку невозможно ни при какой последовательности действий, выходной файл должен содержать число −1.

Ограничения

Примеры тестов

4
4 5 7 2
1 3 4
6

3
1 3

4
4 3 7 2
1 2 5
6

-1