Вася и Петя играют в следующую игру. Они взяли некоторую последовательность символов и дальше получают из нее новые последовательности, отбрасывая несколько первых символов исходной последовательности (разрешается в том числе не отбрасывать ни одного символа, но не разрешается отбрасывать сразу все символы). Каждый называет по одной такой последовательности. Выигрывает тот, чья последовательность будет идти раньше в алфавитном порядке.
Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.
Напишите программу, которая по данной последовательности определит, что нужно назвать Васе, чтобы не проиграть Пете.
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.
В выходной файл выведите выигрышную последовательность.
Примеры
| Входные данные | Выходные данные | Комментарии |
| 4 MAMA | A | Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A |
| 4 ALLO | ALLO | Выигрышной является исходная строка |
| 5 BBABB | ABB |
|
Васю угостили конфетами, а он решил частью конфет поделиться со своим младшим братом Петей. Однако он хочет разделить конфеты не поровну, а по-братски.
Для этого Вася решил сыграть сам с собой в следующую игру. Он разложил конфеты на столе в несколько кучек, которые расположил в ряд. Если кучек не меньше двух, то из первой и последней в этом ряду кучек он выбирает ту, в которой меньше конфет. Пусть в наименьшей кучке оказалось B конфет. Тогда он B конфет перекладывает из первой кучки во вторую, и также B конфет перекладывает из последней кучки в предпоследнюю. При этом, естественно, одна из кучек (или даже две, если в первой и последней кучках конфет было поровну) становится пустой, и Вася забывает про ее существование. Он повторяет эти операции до тех пор, пока на столе не останется одна или две кучки.
Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.
Напишите программу, которая по исходному распределению конфет в кучках определит, чем закончится Васина игра.
Начальное расположение кучек конфет будет описываться K парами чисел Ai, Ni, которые обозначают, что на столе выложено подряд Ni кучек конфет, по Ai конфет в каждой.
Во входном файле задано сначала число K (1≤K≤105). Затем идет K пар чисел Ai, Ni (1≤Ai≤100, 1≤Ni≤108). Общее количество кучек так же не превысит 108.
В выходной файл выведите сначала 1 или 2 — количество кучек конфет, которые останутся в конце игры. Затем выведите соответственно одно или два числа — количества конфет в оставшихся кучках.
Комментарии к примерам тестов
1. Исходно конфеты расположены в следующих кучках: 2 кучки по 2 конфеты, две кучки из 3-х конфет и одна из 2-х:
2 2 3 3 2
Далее по 2 конфеты перекладывается из 1 и 5кучек во 2 и 4, при этом и 1 и 5 кучки становятся пустыми, т.е. на столе остается только 3 кучки:
4 3 5
Теперь по 4 конфеты перекладываются из 1 и 3 кучек во 2-ю и на столе остается две кучки, игра заканчивается с результатом 11 1
2. Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация:
2 1 1 1 1 2
После второго:
3 1 3
После третьего останется одна кучка с 7 конфетами.
3. Изначально имеется 6 кучек:
1 2 3 4 5 5
После первого перекладывания получим:
3 3 4 6 4
После второго:
6 4 9 1
После третьего:
5 5 10
Наконец, получим:
15 5
3 2 2 3 2 2 1
2 11 1
1 1 7
1 7
5 1 1 2 1 3 1 4 1 5 2
2 15 5
В классе учатся N человек. Классный руководитель получил указание направить на субботник R бригад по С человек в каждой.
Все бригады на субботнике будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.
Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!
Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по три человека в каждой. Тогда одним из вариантов является такой:
1 бригада: люди с ростом 225, 205, 225
2 бригада: люди с ростом 160, 190, 170
При этом число неудобства первой бригады будет равно 20, а число неудобства второй — 30. Максимальное из чисел неудобств будет 30, и это будет наилучший возможный результат.
Формат входных данных
Сначала вводятся натуральные числа N, R и C — количество человек в классе, количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ N ≤ 100 000). Далее вводятся N целых чисел — рост каждого из N учеников. Рост ученика — натуральное число, не превышающее 1 000 000 000.
Формат выходных данных
Выведите одно число — наименьше возможное значение максимального числа неудобства сформированных бригад.
8 2 3 170 205 225 190 260 130 225 160
30
Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе кепку, майку, штаны и ботинки так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды.
В наличии имеется N1 кепок, N2 маек, N3 штанов и N4 пар ботинок (1 ≤ Ni ≤ 100 000). Про каждый элемент одежды известен его цвет (целое число от 1 до 100 000). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.
Для каждого типа одежды i (i = 1, 2, 3, 4) сначала вводится количество Ni элементов одежды этого типа, далее в следующей строке — последовательность из Ni целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят 100 000.
Выведите четыре целых числа — цвета соответственно для кепки, майки, штанов и ботинок, которые должен выбрать Глеб из имеющихся для того, чтобы выглядеть наиболее стильно. Если ответов несколько, выведите любой.
3 1 2 3 2 1 3 2 3 4 2 2 3
3 3 3 3
1 5 4 3 6 7 10 4 18 3 9 11 1 20
5 6 9 20
Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.
К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.
Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все английские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.
Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.
В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на латинский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.
Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100 000.
Выведите соответствующий данному латинско-английский словарь, в точности соблюдая формат входных данных. В частности, первым должен идти перевод лексикографически минимального латинского слова, далее — второго в этом порядке и т.д. Внутри перевода английские слова должны быть также отсортированы лексикографически.
«Лексикографический порядок» означает, что слова идут по алфавиту. Иначе говоря, если у двух слов A и B несколько первых символов совпадают, то раньше идет то, у которого первая буква после общей части идет в алфавите раньше (например, слова solution и solve идут именно в таком порядке, так как первые 3 буквы в этих словах совпадают, а 4-я буква u в слове solution идет по алфавиту раньше буквы v слова solve). Если слово A является началом слова B, то раньше идет слово A (например, сначала идет слово school, а затем слово schoolboy).
3 apple - malum, pomum, popula fruit - baca, bacca, popum punishment - malum, multa
7 baca - fruit bacca - fruit malum - apple, punishment multa - punishment pomum - apple popula - apple popum - fruit