Язык программирования

3 082 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Максимальная сумма смежных элементов#30767
На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальную сумму смежных элементов последовательности. N не превышает 1000000, каждый элемент последовательности не превосходит по модулю 100.
 

 

Примеры
№ Входные данные Выходные данные
1
9
-2
1
-3
4
-1
2
1
-5
4
 6
 
Пояснения: для заданной последовательности чисел (-2 1 -3 4 -1 2 1 -5 4) наибольшую сумму можно получить для смежной последовательности элементов: 4 -1 2 1.
Решение на 2 балла начисляются при прохождении программой 50% тестов, 3 балла - при прохождении программой 75% тестов.

 
Динамическое программированиеЕГЭ - вычислительные задачи
✓ 201✗ 331700средняяВойти и решать
Лифт#30720

Лифт

В доме Вилли установили скоростной лифт новой экспериментальной модели. В этом лифте кнопки с номерами этажей заменены двумя другими кнопками. При нажатии на первую кнопку лифт поднимается на один этаж вверх, а при нажатии на вторую – опускается на один этаж вниз.
 
Младшему брату Вилли Дилли очень нравится кататься на новом лифте. Он катается на нём до тех пор, пока не побывает на каждом из этажей хотя бы по одному разу. После этого Дилли довольный возвращается домой.
 
Зная порядок, в котором Дилли нажимал на кнопки лифта, попробуйте определить общее количество этажей в доме Вилли и Дилли.
 
Входные данные
Первая строка входного файла INPUT.TXT содержит последовательность нажатий на кнопки лифта. Символ «1» означает, что была нажата первая кнопка, а символ «2» – что была нажата вторая кнопка. Символы «1» и «2» не разделены пробелами. Количество нажатий от 1 до 100. Гарантируется, что лифт никогда не опускался ниже первого и не поднимался выше последнего этажа.
 
Выходные данные
Следует вывести одно число – количество этажей в доме Вилли и Дилли.

Ввод Вывод
11 3
21212 2
1221221221221 6

Задачи на моделированиеОдномерные массивы
—Войти и решать
Загранпаспорт#30718
Осень 2243-го года. Государства в прошлом, главным территориальным образованием является автономия. В результате терраформирования территория бывшей Евразии теперь представляет собой прямоульник, он разбит на w × h квадратных автономий, которые организованы в виде сетки из w автономий по ширине и h по высоте. Некоторые автономии входят в содружество Крипто, они представляют собой криптоанархистские технократические общества и не признают бюрократии. Остальные автономии входят в конфедерацию Бюрро, бюрократия в них доведена до высшего совершенства.

Для перемещения между автономиями необходим загранпаспорт. При въезде в автономию содружества Крипто предъявлять документы не нужно, но при въезде в автономию конфедерации Бюрро пограничная служба проверяет документ, заполняет специальные формы и проставляет в загранпаспорт путешественника штамп своей автономии. Один штамп занимает одну страницу паспорта, разные штампы ставятся на разные страницы.

Опытный путешественник по имени Вениамин хочет получить загранпаспорт нового образца. Чтобы это сделать досрочно, ему нужно заполнить все страницы своего старого паспорта штампами пограничных служб. На данный момент у него осталось n пустых страниц, соответственно ему нужно ровно n раз въехать в автономию Бюрро. Он хочет сделать это как можно быстрее. Вениамин путешествует таким образом, что за один день он переезжает из автономии, в которой он находится, в автономию, имеющую с ней общую сторону. Помогите Вениамину спланировать свое путешествие так, чтобы заполнить все оставшиеся страницы загранпаспорта и при этом сделать как можно меньше переездов между автономиями.

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

Формат входных данных
В первой строке входного файла содержатся три целых числа: w, h и n (1 ≤ w, h ≤ 500, 1 ≤ n ≤ 1 000). В каждой из следующих h строк содержится по w символов, они задают карту Евразии. Символ «A» обозначает автономию содружества Крипто, а «T» — автономию конфедерации Бюрро. Автономия, в которой Вениамин начинает свое путешествие, обозначена символом «V». Карта дана с севера на юг по строкам и с запада на восток по столбцам, таким образом, первый символ второй строки входного файла описывает самую северо-западную автономию. Гарантируется, что в Евразии есть хотя бы одна автономия Бюрро.

Формат выходных данных
В выходной файл выведите одну строку из символов «N», «E», «S», «W» — план путешествия Вениамина. Эти символы означают, что Вениамину следует поехать на север, восток, юг или запад, соответственно. Число перемещений в плане необходимо минимизировать, в процессе путешествия Вениамин должен ровно n раз въехать в автономию Бюрро. Если возможных оптимальных планов путешествия несколько, можно вывести любой.
 
Ввод Вывод
5 3 6
AAATA
VAATA
AAAAT		 EEENSNSN
3 1 2
TVT		 WEE
Задача на реализацию
✓ 1✗ 1—Войти и решать
Перетягивание каната#30717
В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли n кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ ai ≤ 1000) — длины имеющихся кусков каната.

Формат выходных данных
Выведите единственное число — максимальную длину каната, которую можно получить.
 
Ввод Вывод
2 10
25 50		 55
5 2
4 5 6 7 8		 14
Алгоритмы сортировкиЗадача на реализацию
✓ 2✗ 16—Войти и решать
Вращающаяся пластина#30715
Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

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

Теперь Вася хочет забить в доску еще один гвоздь, который бы ограничил вращение пластины, но он еще не решил куда. Он наметил m возможных позиций, куда он хотел бы забить гвоздь, и для каждой из них хочет узнать, на какой угол он сможет поворачивать свою пластину, если забьет в доску гвоздь в этой точке. При этом как только пластина касается гвоздя, дальше ее поворачивать нельзя.

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 106 по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа αi и βi , где αi — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а βi — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите αi = βi = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10−6 .
 
Ввод Вывод
4
0 0
-3 -3
0 -6
3 -3
3
-8 0
-2 0
2 -1		 360.000000000000 360.000000000000
45.000000000000 225.000000000000
251.565051177078 18.434948822922

Пояснение


На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины.
Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на 45 гр.  по часовой стрелке или на 225 гр. против часовой стрелки.

 
Вычислительная геометрияЗадача на реализацию
✓ 0✗ 4—Войти и решать
Словарь синонимов#30711
Вам дан словарь, состоящий из пар слов. Каждое слово является синонимом к парному ему слову. Все слова в словаре различны. Для одного данного слова определите его синоним.
 
Входные данные
Программа получает на вход количество пар синонимов N. Далее следует N строк, каждая строка содержит ровно два слова-синонима. После этого следует одно слово.
 
Выходные данные
Программа должна вывести синоним к данному слову.
 
Пример
№ Входные данные Выходные данные
1
3
Hello Hi
Bye Goodbye
List Array
Goodbye
 Bye
Словари
✓ 217✗ 90500лёгкаяВойти и решать
Олег и двоичные последовательности#30708
Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из n элементов.
Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности s1, . . . , sn называется массив z[1..n], в котором:

• z[1] = 0;
• Если i > 1, то z[i] равно длине наибольшего общего префикса последовательности s и суффикса последовательности s, начинающегося с i-й позиции. Иначе говоря, z[i] равно максимальному k, такому что s1 = si , s2 = si+1, . . . , sk = si+k−1.

Например, для последовательности s = h0, 0, 1, 1, 0, 0, 1i Z-функция следующая: z = h0, 1, 0, 0, 3, 1, 0i.
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю 109 + 7. Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
Формат входных данных
В первой строке входного файла находится целое число n — длина исходной двоичной последовательности (1 ≤ n ≤ 1000). Во второй строке входного файла находятся n целых чисел z[1], . . . , z[n], где z[i] — значение Z-функции в позиции i, или −1, если значение в i-й позиции было закрашено (−1 ≤ z[i] ≤ n).

Формат выходных данных
В выходной файл выведите единственное число — остаток от деления числа подходящих двоичных последовательностей на число 109 + 7.
 
Ввод Вывод
3
0 0 1		 2
4
0 0 1 0		 0
3
0 3 -1		 0
3
-1 -1 -1		 8


Пояснение
В первом примере подходят последовательности {0, 1, 0 }  и { 1, 0, 1 }.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере z[2] = 3, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.
Обход в глубинуПрименение обхода в глубинуРазбор случаев
✓ 1✗ 0—Войти и решать
Редактор скобочной последовательности#30705
Задана строка, состоящая только из:
• прописных и строчных букв английского алфавита;
• символов подчёркивания (они используются в качестве разделителей);
• круглых скобок (как открывающих, так и закрывающих).

Гарантируется, что каждая открывающая скобка имеет парную закрывающую, идущую следом. Аналогично, каждая закрывающая скобка имеет парную открывающую, которая расположена до неё. Для каждой пары соответствующих скобок верно, что между ними нет каких-либо других скобок. Иными словами, каждая скобка в строке входит в пару «открывающая-закрывающая», и такие пары не вкладываются друг в друга.
Например, допустимой строкой является: _Hello_Vasya(and_Petya)__bye_(and_OK)
Словом называется нерасширяемая последовательность подряд идущих букв, то есть последовательность букв, где слева и справа от неё находится скобка или символ подчёркивания, или соответствующий символ отсутствует.
Приведенный пример содержит семь слов: «Hello», «Vasya», «and», «Petya», «bye», «and» и «OK».

Напишите программу, которая найдет:
• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет),
• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).
 
Входные данные: в первой строке записано целое число n (\(1 <= n <= 255\)) — длина заданной строки. Во второй строке записана строка, состоящая только из строчных и прописных английских букв, открывающих и закрывающих скобок, а также символов подчёркивания.
 
Выходные данные: выведите два числа:
• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет);
• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).
 
Примеры
№ Входные данные Выходные данные
1 37
_Hello_Vasya(and_Petya)__bye_(and_OK)		 5 4
2
37
_a_(_b___c)__de_f(g_)__h__i(j_k_l)m__
 2 6
3
27
(LoooonG)__shOrt__(LoooonG)
 5 2
4
5
(___)
 0 0

Примечание
В первом примере слова «Hello», «Vasya» и «bye» записаны вне скобок, а слова «and», «Petya», «and» и «OK» — внутри. Обратите внимание, что слово «and» встречается дважды, и учитывать в ответе его тоже следует два раза.
Строки
✓ 273✗ 682700средняяВойти и решать
Замена подстроки#30704
Найти в строке указанную подстроку и заменить ее на новую. Строка s, ее подстрока s1 для замены и новая подстрока s2 вводятся.

P.S. Искомые подстроки в исходной строке не пересекаются.
P.P.S. В строках не содержатся пробелы.
P.P.P.S. Искомая подстрока может встречаться неоднократно.
P.P.P.P.S. Все буквы строчные.
P.P.P.P.P.S. Нет символов помимо строчных латинских букв.

На вход подаются 3 строки: s, s1, s2. Длина всех строк не превосходит 100.
 
Примеры
№ Входные данные Выходные данные
1 abcde
ab
fg		 fgcde
2
ababc
ab
c
 ccc

 
Строки
✓ 705✗ 1 506500лёгкаяВойти и решать
Спутник "Восход" -2#30698

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи натуральное число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии количество пар таких показаний прибора, произведение которых кратно 6 и между моментами передачи которых прошло не менее трех минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.


Задача А (2 балла). Напишите, на любом языке программирования, программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего проверены все возможные пары элементов.

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


Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N>3\). В каждой из следующих N строк задаётся одно натуральное число – очередное показание прибора.

 

 

Примеры
№ Входные данные Выходные данные
1
5
6
2
4
1
3
 3
В приведённом наборе из 5 чисел имеются три пары (6, 3), (2, 3) и (6, 1), удовлетворяющих условию задачи.


 
ЕГЭ - вычислительные задачи
✓ 268✗ 522700средняяВойти и решать
Подсчет пар с суммой кратной 12#30697

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых \(1 < i < j < N\) и сумма элементов кратна 12. 

Напишите эффективную по времени и памяти программу для решения этой задачи. 

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Выходные данные
Выведите ответ на задачу

 

Примеры
№ Входные данные Выходные данные
1
5
7
5
6
12
24
 2
В приведённом наборе из 5 чисел имеются две пары (7, 5) и (12, 24), сумма элементов которых кратна 12.
 
ЕГЭ - вычислительные задачи
✓ 506✗ 548500лёгкаяВойти и решать
Подсчет пар с произведением кратным 6#30696

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 <= i < j <= N и произведение элементов кратно 6. 

Напишите эффективную по времени и памяти программу для решения этой задачи. 

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 100000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Выходные данные
Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1
4
7
5
6
12
 5
В приведённом наборе из 4 чисел имеются пять пар (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), произведение элементов которых кратно 6.
ЕГЭ - вычислительные задачи
✓ 558✗ 708500лёгкаяВойти и решать
Выборка чисел из тройки для максимальной суммы, не кратной 4#30695

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. 

Напишите эффективную программу, решающую поставленную задачу.


Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000. 

Выходные данные
Выведите ответ на задачу

 

 

Примеры
№ Входные данные Выходные данные
1
6
1 3 2
5 12 12
6 8 12
5 4 12
3 3 12
1 1 13
 63


 

ЕГЭ - вычислительные задачи
✓ 548✗ 1 194600лёгкаяВойти и решать
НОД для пары чисел#30694

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. 

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

Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. 

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.


Входные данные
На вход программе в первой строке подаётся количество пар N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000. 

 

Входные данные
Выведите ответ на задачу

 

 

Примеры
№ Входные данные Выходные данные
1
6
1 3 
5 15  
6 9  
5 4  
3 3  
36 40  
 3 1
ЕГЭ - вычислительные задачи
✓ 689✗ 1 133600лёгкаяВойти и решать
Цифры в числах#30693
На вход программы поступает последовательность из N натуральных чисел, каждое из которых не больше 10000. Требуется вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления. Если какие-то цифры встречаются одинаковое число раз, они выводятся в порядке убывания. 

Входные данные
На вход программе подаётся натуральное число N (\(N <= 10000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

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

 

Примеры
№ Входные данные Выходные данные
1
3 
456
20
3452
 6 3 0 5 4 2
ЕГЭ - вычислительные задачи
✓ 754✗ 1 112500лёгкаяВойти и решать
Сортировка вектора: Начало#30686
Дана последовательность, состоящая из целых чисел. Напишите программу, которая создает и сортирует массив по убыванию.
 
Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел.
 
Выходные данные
Необходимо вывести массив, отсортированный по убыванию.
 
Примеры
№ Входные данные Выходные данные
1 5
4 56 23 67 100		 100 67 56 23 4
Массивы
✓ 287✗ 157300лёгкаяВойти и решать
Отрезки#30685
Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
 
Входные данные
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
 
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.

 
Примеры
№ Входные данные Выходные данные
1
3
1 3
4 5
2 4
 1 2 1
2
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
 1 2 3 4 5 4 3 2 1

 
 
Множества
✓ 56✗ 172900средняяВойти и решать
Симметричная запись из цифр#30680

На вход программы поступает последовательность из N натуральных целых чисел, каждое из которых не больше 1000. Требуется определить, можно ли записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). 

Если требуемую строку составить невозможно, то программа должна вывести на экран число 0, а если возможно, то вывести число 1.

Входные данные
На вход программе подаётся натуральное число N (\(N <= 100000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных
3
13
22
32

Пример выходных данных для приведённого примера входных данных:
0
Из цифр D, 1, 6, 2, 0 нельзя составить симметричную строку.

Пример входных данных:
4
186
68
171
14

Пример выходных данных для приведённого примера входных данных:
1
Из цифр A, B, 4, 4, A, B, D можно составить симметричную строку

Напишите эффективную по времени и по памяти программу, которая решает поставленную задачу.
ЕГЭ - вычислительные задачи
✓ 583✗ 631600лёгкаяВойти и решать
Финал#30658
Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.
 
Входные данные
В первой сроке входного файла находится три натуральных числа Р (1 ≤ P ≤ 100000) — количество команд, принявших участие в полуфинале, N (1 ≤ N ≤ P ) и k (1 ≤ k ≤ P ) . В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные латинские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образам если название университета записано в i -той строке (2 ≤ i ≤ P + 1) , то эта команда заняла i - 1 место на полуфинале и имеет номер, записанный на i - 1 месте в P + 2 строке.
 
Выходные данные
В выходной файл выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел #номер команды.
 
Пример
№ Входные данные Выходные данные
1
9 5 2
Fantasy University
Crazy University
Fantasy University
Fantasy University
Very Good U
Good U
Very Good U
Crazy University
Good U
1 1 2 3 2 1 1 2 2
Fantasy University #1
Crazy University #1
Fantasy University #2
Very Good U #2
Good U #1
Словари
✓ 385✗ 689800средняяВойти и решать
Поделиться
Класснуть