В Команде проходит традиционная ежегодная олимпиада по теории магии среди младшекурсников. Завхозу смены Кате Медведевой поручили заняться распределением студентов по аудиториям.
Каждый факультет выставил своих лучших учеников на олимпиаду. От Звездочек участвует G студентов, от Солнышек S студентов, Травинок представляет H студентов и Подсолнухов — R студентов. В распоряжении Медведевой находится M аудиторий. На аудитории наложено особое заклятие расширения, поэтому при необходимости они могут вместить любое количество студентов. При рассадке необходимо учесть, что ученики одного факультета, находящиеся в одной аудитории, могут, воспользовавшись случаем, начать жульничать, обмениваясь идеями по решению задач. Поэтому в любой аудитории количество студентов с одного факультета, попавших в нее, следует свести к минимуму. Назовем рассадку, удовлетворяющую такому требованию, оптимальной.
Помогите посчитать, какое минимальное количество студентов с одного факультета все же придется посадить в одной аудитории даже при оптимальной рассадке.
В первой строке идут четыре целых числа G, S, H и R (1 ≤ G, S, H, R ≤ 1000) — количество учеников, представляющих каждый из факультетов школы.
Во второй строке идет целое число M (1 ≤ M ≤ 1000) — количество классов в распоряжении у завхоза.
Выведите минимальное количество студентов с одного факультета, которое Кате придётся посадить в одну аудиторию даже при оптимальной рассадке.
4 3 4 4
2
2
15 14 13 14
5
3
У Миши развитое эстетическое чувство. Он считает, что не все числа одинаково порядочные. Когда ему грустно, он начинает придумывать числа и приводить их в порядок.
Миша очень любит рассматривать сумму цифр числа. Для того чтобы привести в порядок число A, он сначала записывает само число. Потом он пишет сумму цифр этого числа. Затем — сумму цифр суммы цифр и так далее, до тех пор, пока очередное число не станет однозначным. Он считает, что результатом приведения в порядок числа A является сумма всех выписанных чисел, включая само число A.
Миша настолько любит этот процесс, что он даже заменяет ему счёт овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привёл в порядок число A, у него получилось число B. Но вот беда — он не помнит, какое именно он взял число A! Помогите ему в отыскании этого числа.
На ввод подаётся единственное целое число B (1 ≤ B ≤ \(10^9\) )
Если существует такое число A, что после приведения его в порядок, получается B, то выведите любое такое число. Если же Миша где-то ошибся в расчётах и такого числа не существует, то выведите -1.
42
29
20
-1
Пояснение к первому примеру. Последовательность сумм цифр для 29 состоит из чисел 29, 11, 2. Соответственно, после приведения в порядок число 29 превращается в число 42 = 29 + 11 + 2.
Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...
Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.
Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?
После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.
Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.
На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.
Длина строки лежит в пределах от 5 до 100 000 символов.
Для каждой буквы на листочке Лёши, выведите её, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.
hello
e: 8
h: 5
l: 17
o: 5
abacaba
a: 44
b: 24
c: 16
Пояснение к первому примеру. Если любимое Лёшино слово — "hello", то на листочке у Лёши будут выписаны следующие слова:
Аня — страстный любитель ювелирных изделий. Ее коллекция насчитывает множество бриллиантов, изумрудов и алмазов.
...Срочная новость! Бесценный змеиный рубин Клеопатры был украден!
Три дня назад мир потрясло сенсационное известие: исследовательская экспедиция обнаружила в одном из храмов, построенных во времена великой египетской императрицы Клеопатры, потайную комнату. В ней кроме бронзовой статуи императрицы обнаружилась поразительной красоты диадема, ранее считавшаяся бесследно утерянной! Ученые сообщили, что диадема увенчана алым a-каратным рубином в форме змеиной головы. Однако буквально пару часов назад поступила новость, что бесценное украшение было изувечено: кто-то пробрался в камеру хранения диадемы и вырезал из нее рубин! Полиция устанавливает круг подозреваемых...
Услышав о краже рубина, Аня сразу бросилась исследовать информацию на черных рынках. В течение дня она обнаружила N объявлений о продаже рубина в форме змеиной головы, утверждающих что это именно украденная древняя ценность. Аня не простит себе, если она упустит такой бесценный экспонат для своей коллекции, поэтому она приказала своему помощнику Глебу срочно купить все эти камни, надеясь приобрести среди них настоящую реликвию.
Купив все N камней, Глеб тут же провел несколько пробных измерений, взвесив некоторые наборы из них, и отправил результаты Ане по электронной почте. Тем временем она проконсультировалась с известным исследователем старины Андрэ Шесто-Мерта по поводу украденной драгоценности и узнала, что по всем имеющимся историческим источникам рубин весил не a карат, как утверждали журналисты, а b карат!
Зная результаты взвешиваний Глеба, и учитывая, что все поддельные камни весят a карат, и только настоящий змеиный рубин может весить b карат, определите, какие из купленных камней могут на самом деле являться потерянной реликвией великой императрицы прошлого.
В первой строке находятся четыре целых числа N, a, b и K (1 ≤ N ≤ 200, 1 ≤ a, b ≤ 1 000 000, a ≠ b, 1 ≤ K ≤ 1 000).
Далее идут K строк, описывающих взвешивания, проведенные Глебом.
Первое число в i-ом описании — wi (1 ≤ wi ≤ 200 000 000), суммарный вес группы камней, участвовавших в i-ом взвешивании.
Второе число — mi (1 ≤ mi ≤ N) — количество камней, участвовавших в i-ом взвешивании.
Далее следуют mi целых чисел, упорядоченных по возрастанию, — номера камней, участвовавших в i-ом взвешивании.
Если среди купленных Глебом камней змеиного рубина точно нет, выведите строку "Fail" (без кавычек).
Если украденный рубин может присутствовать среди камней, то выведите в первой строке количество всех возможных кандидатур на роль древней реликвии, а второй строке — номера возможных вариантов. Выводить номера можно в произвольном порядке.
Если же Глеб в некоторый момент ошибся в расчетах, и присланная им информация о взвешиваниях не может соответствовать действительности, выведите строку "Impossible" (без кавычек).
4 15 17 2
30 2 1 3
47 3 2 3 4
2
2 4
3 15 17 3
30 2 1 2
30 2 2 3
47 3 1 2 3
Impossible
2 1 2 2
1 1 2
1 1 1
Fail
В первом тесте из первого взвешивания мы делаем вывод, что первый и третий камни гарантированно поддельные. С другой стороны, среди второго, третьего и четвёртого камня точно есть настоящий. Значит настоящим может оказаться второй или четвёртый камень.
Во втором тесте Глеб ошибся в измерениях, потому что из первых двух измерений следует, что все камни фальшивые, а из последнего — что настоящий камень, тем не менее, среди них присутствует.
В третьем тесте из результатов явно следует, что оба приобретенных камня фальшивые.
Маленький Петя очень любит компьютеры и хочет научиться программировать.
В небольшом городке Маховники, где он живёт, работает сеть кружков по программированию самой разной тематики. Когда Петя пошёл записываться, он увидел большой список, состоящий из N кружков. Петя хочет быть всесторонне развитой личностью, поэтому он собрался отучиться во всех этих кружках. Но когда он собрался записаться на все занятия сразу, обнаружилось, что не всё так просто. Во-первых, в один момент времени разрешается учиться только в одном из этих N кружков. Во-вторых, некоторые преподаватели выдвигают входные требования к знаниям учеников, заключающиеся в знании курсов каких-то других кружков!
Петя хочет стать великим программистом, поэтому подобные мелочи его не останавливают. Действительно, ему достаточно всего-лишь составить правильный порядок посещения кружков, чтобы удовлетворить всем входным требованиям — это совсем простая задача, доступная даже совсем неопытному программисту.
Перед тем как сесть составлять порядок посещения кружков, Петя внимательно перечитал условия обучения и обнаружил ещё один важный пункт. Оказывается, для привлечения школьников, во всех кружках действует система поощрения учеников конфетами. Это означает, что по окончании очередного кружка ученику выдают несколько коробок конфет, всё больше и больше с каждым пройденным кружком. С другой стороны, в каждом кружке количество конфет в коробке своё, зависящее от сложности курса. Более конкретно — за прохождение i-го по счёту кружка, если этот кружок идёт в общем списке под номером j, ученику выдают аж Ni - 1·j конфет — такие щедрые люди программисты.
Петя решил совместить полезное с приятным — теперь он хочет выбрать такой порядок посещения кружков, чтобы при этом получить как можно больше конфет, однако эта задача ему уже не под силу. Помогите будущему великому человеку отыскать такой порядок.
В первой строке входного файла содержится целое число N (1 ≤ N ≤ 100 000) — количество кружков в Маховниках.
В последующих N строках идут описания входных требований кружков, в порядке их следования в общем списке. В i-ой строке сначала записано целое число ki (0 ≤ ki ≤ N - 1) — количество кружков, в которых нужно отучиться перед записью в i-й кружок, а потом ki номеров этих кружков.
Сумма ki не превосходит 200 000.
Гарантируется, что возможно посетить все эти кружки в некотором порядке, не нарушая условия посещения.
Выведите N номеров, разделённых пробелами — порядок, в котором Пете надо посещать кружки, чтобы съесть как можно больше конфет.
6
1 2
0
1 2
3 1 2 5
1 2
4 1 3 4 5
2 1 3 5 4 6
Пояснение к примеру. Посещая кружки в указанном порядке, Петя получит 60·2 + 61·1 + 62·3 + 63·5 + 64·4 + 65·6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 конфет.