Словари

73 задачи
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
3 коровы#38835
Склиссы — "сумчатые парнокопытные" в виде коровы с перепончатыми крыльями с планеты Шешинеру. Несмотря на способность летать, склисс, как и любая земная корова, достаточно ленива и тугодумна (почитайте побольше про склиссов ). 
Профессор Игорь Селезнев взял на борт трех склиссов для изучения: Бесси (Bessie), Элси (Elsie) и Милдред (Mildred), каждая из которых изначально дает 7 галлонов молока в день. Поскольку известно, что надой склисса со временем может измениться, профессор Селезнев проводит периодические измерения в течение следующих 100 дней и записывает их в журнал. Записи в его журнале выглядят так:

35 Bessie -2
14 Mildred +3

Первая запись указывает на то, что на 35-й день надой Бесси был на 2 галлона ниже, чем при последнем измерении. Следующая запись указывает, что на 14-й день надой молока у Милдред увеличился на 3 галлона по сравнению с тем, когда он был измерен в последний раз.
Профессор Селезнев занят во многих исследованиях, поэтому он может сделать не более одного измерения в день. К сожалению, он не всегда успевает сразу записать все в журнал и, поэтому его измерения могут идти не в хронологическом порядке.

Чтобы поддерживать мотивацию склиссов, Игорь Селезнев с гордостью вывешивает на стене организованной фермы фотографию склисса с самым высоким надоем молока (если таких склиссов несколько, то он вывешивает все их фотографии).
Определите количество дней, в течение которых профессору Игорю Селезневу нужно было бы менять фотографию.

Входные данные
Первая строка ввода содержит N, количество измерений, которые сделал профессор. Каждая из последуюших N строк описывает одно измерение, в формате, описанном выше: день (целое число от 1 до 100), имя склисса, и изменение производительности (ненулевое целое число). Количество молока, которое даёт любой склисс, всегда будет в интервале 0..1000.

Выходные данные
Выведите е количество дней, в течение которых профессору Игорю Селезневу нужно было бы менять фотографию.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 
4
7 Mildred +3
4 Elsie -1
9 Mildred -1
1 Bessie +2
 
3
 Иначально все склиссы дают по 7. В день 1 производительность Бесси вырастет до 9, делая её единственной победительницей и вынуждающей профессора сменить фотографию. В день 4 производительность Элси уменьшится до 6, но это не изменит того факта, что лидером останется Бэсси. В день 7 Милдред выйдет в лидеры, в день 8 Милдред сравняется с Бесси, что опять приведёт к смене карточек.
Словари
✓ 70✗ 151800средняяВойти и решать
Подматрица - 1#38791
У Фили есть квадратная матрица A размера N×N, но она кажется ему слишком большой. Ему гораздо больше нравятся матрицы размера k×k (k<N).
Филя хочет получить матрицу нужного размера взяв некоторую подматрицу исходной матрицы.
Подматрицей k×k матрицы A в данном случае Филя считает матрицу B такую, что bi,j=ai+x,j+y, для всех i, j от 1 до k. Из данного определения можно заметить, что подматрица исходной матрицы задается парой чисел (x, y).
Для того, чтобы выбрать наиболее интересную для себя подматрицу, Филя хочет узнать, сколько есть способов выбрать из исходной матрицы две различные (характеризующие пары (x, y) отличаются хотя бы в одной позиции) равные подматрицы k×k. Две матрицы Q и P размера k×k считаются равными, если для любых i,j:1≤i,j≤k выполняется qi,j=pi,j.
Если условия равенства не выполняется, матрицы считаются неравными.

Входные данные
В первой строке входного файла содержатся два натуральных числа N и k - размеры исходной и нужной матрицы.
(1<=k<=N<=10). В следующих N строках заданы через пробел по N натуральных чисел ai,j - элементы исходной матрицы (1<=ai,j<10).

Выходные данные
В единственной строке выходного файла выведите одно число - количество способов выбрать из исходной матрицы две различные равные подматрицы размера k×k.
 
Примеры
№ Входные данные Выходные данные
1 3 1
1 2 3
4 5 6
7 8 9		 0
2 3 1
1 1 1
1 1 1
1 1 1		 36
3 3 2
1 2 1
1 1 2
1 1 1		 1
Словари
✓ 0✗ 1—Войти и решать
Пропуск в общежитие - 1#38790
На входе в общежитие стоит турникет. Чтобы через него пройти, требуется приложить пропуск. Пропуск надо прикладывать и при входе в общежитие и при выходе из него. Для того, чтобы исключить несанкционированные проходы, пропуск не работает два раза подряд на вход и два раза подряд на выход.

Однако, хитрые студенты придумали, как обойти это ограничение. Чтобы войти или выйти вдвоем по одному пропуску, они прикладывают его с нужной стороны, потом с противоположной, но никто не проходит, а затем снова с нужной. 

Начальник охраны решил разобраться с данной проблемой и сделать выговоры всем нарушителям. По каждому событию входа/выхода есть запись в журнале событий. Он считает нарушителями тех владельцев пропусков, у которых произошло три события вида вход-выход-вход менее чем за dt минут.

Вам дан журнал событий турникета. Требуется вывести список тех студентов, кому будет сделан выговор

Входные данные
В первой строке задано два числа n и dt — число записей в журнале событий турникета и ограничение времени, выбранное начальником охраны, соответственно (1≤n≤1000, 3≤dt≤1440).
В следующих nn строках даны записи в журнале событий в хронологическом порядке. Запись в журнале состоит из трех частей, разделенных пробелом:
  •  Время события в формате hh:mm
  •  Фамилия студента, состоящая из не более чем 20 букв латинского алфавита, первая из которых заглавная.
  •  Тип события: in, если произошел вход и out, если произошел выход.

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


Выходные данные
В первой строке выведите число нарушителей. После чего выведите фамилии нарушителей в лексикографическом порядке.
 

Примеры
№ Входные данные Выходные данные
1 6 10
01:23 Petrov in
01:24 Ivanov out
01:25 Petrov out
01:27 Ivanov in
01:32 Petrov in
01:33 Ivanov out		 1
Petrov
2 6 10
01:23 Petrov in
01:24 Ivanov out
01:25 Petrov out
01:27 Ivanov in
01:33 Petrov in
01:34 Ivanov out		 0
Словари
✓ 37✗ 129600лёгкаяВойти и решать
Пропуск в общежитие - 2#38789

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

Однако, хитрые студенты придумали, как обойти это ограничение. Чтобы войти или выйти вдвоем по одному пропуску, они прикладывают его с нужной стороны, потом с противоположной, но никто не проходит, а затем снова с нужной.

Начальник охраны решил разобраться с данной проблемой и сделать выговоры всем нарушителям. По каждому событию входа/выхода есть запись в журнале событий. Он считает нарушителями тех владельцев пропусков, у которых произошло три события вида выход-вход-выход менее чем за dt минут.

Вам дан журнал событий турникета. Требуется вывести список тех студентов, кому будет сделан выговор.

Входные данные

В первой строке задано два числа n и dt — число записей в журнале событий турникета и ограничение времени, выбранное начальником охраны, соответственно (1≤n≤1000, 3≤dt≤1440).

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

  • Время события в формате hh:mm
  • Фамилия студента, состоящая из не более чем 20 букв латинского алфавита, первая из которых заглавная.
  • Тип события: in, если произошел вход и out, если произошел выход.

 

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

Выходные данные

В первой строке выведите число нарушителей. После чего выведите фамилии нарушителей в лексикографическом порядке.
 

Примеры
№ Входные данные Выходные данные
1 6 10
01:23 Petrov in
01:24 Ivanov out
01:25 Petrov out
01:27 Ivanov in
01:32 Petrov in
01:33 Ivanov out		 1
Ivanov
2 6 10
01:23 Petrov in
01:24 Ivanov out
01:25 Petrov out
01:27 Ivanov in
01:33 Petrov in
01:34 Ivanov out		 0
Словари
✓ 10✗ 37700средняяВойти и решать
Свойства объектов - 2#38788
В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 109.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит. Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество удаленных свойств у объекта r
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Входные данные
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 105). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= ki <= 100, 1 <= pi,j <= 109).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 105. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 105).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 109);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

Выходные данные
Для всех запросов на нахождение количества оставшихся свойств у объекта, в отдельных строках, в порядке их поступления для каждого запроса выведите это количество.
 
Примеры
№ Входные данные Выходные данные
1 2
3 1 2 4
3 2 3 5
12
- 1
? 1
? 2
- 2
? 1
? 2
- 5
? 1
? 2
- 6
? 1
? 2		 1
0
2
1
2
2
2
2


Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта 1 удаленное свойство, а у второго все еще 0.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта теперь 2 удаленных свойства, а у второго 1.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов становится 2 удаленных свойства.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество удаленных свойств у объектов.
 
Словари
✓ 2✗ 21 000средняяВойти и решать
Свойства объектов - 1#38787
В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 109.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Входные данные
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 105). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= ki <= 100, 1 <= pi,j <= 109).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 105. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 105).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 109);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

Выходные данные
Для всех запросов на нахождение количества оставшихся свойств у объекта, в отдельных строках, в порядке их поступления для каждого запроса выведите это количество.
 
Примеры
№ Входные данные Выходные данные
1 2
3 1 2 4
3 2 3 5
12
- 1
? 1
? 2
- 2
? 1
? 2
- 5
? 1
? 2
- 6
? 1
? 2		 2
3
1
2
1
1
1
1

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта остается 2 свойства, а у второго все еще 3.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта остается 1 свойство, а у второго - 2.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов остается 1 свойство.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.
 
Словари
✓ 18✗ 42800средняяВойти и решать
Генеалогическое древо - 2. Потомки#38786

Генеалогическое древо — это графическая схема, описывающая родственные связи в пределах одной семьи. Начало такого дерева — это один предок (родоначальник) или супруги и далее цепочка строится вниз. По заданному генеалогическому древу, определите у каждого элемента число его потомков (не считая самого элемента). 


Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

Выходные данные

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента, необходимо вывести число его потомков.
 

Пример
№ Входные данные Выходные данные
1 
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
 
Alexander_I 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3
Деревьяпоиск в глубину и подобноеСловари
✓ 38✗ 65900средняяВойти и решать
Генеалогическое древо - 1. Высота#38785

Генеалогическое древо — это графическая схема, описывающая родственные связи в пределах одной семьи. Начало такого дерева — это один предок (родоначальник) или супруги и далее цепочка строится вниз. Сопоставим с каждым элементов дерева целое неотрицательное число, называемое высотой.  У самого верхнего предка высота 0, у каждого следующего потомка высота на 1 больше, чем у его родителя. 

По заданному генеалогическому древу, определите высоту всех его элементов.


Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

Выходные данные

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
 

Пример
№ Входные данные Выходные данные
1 
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
 
Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2
Линейные алгоритмыСловари
✓ 68✗ 86800средняяВойти и решать
Ништячки юных программистов#38784

БЕСКОНЕЧНЫЙ ВВОД PYTHON?
На летних сборах по программированию за каждую решенную задачу давали некоторое количество фанфиков. В течении смены юные программисты могли тратить эти фанфики на покупку различных ништячков. По окончании смены у организаторов скопился большой список, каждая строка которого представляет собой запись вида Программист ништячок количество, где Программист -  имя юного программиста (строка без пробелов), ништячок - наименование купленного ништячка (строка без пробелов), количество — количество приобретенных единиц ништячка. 

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

Входные данные
Программа получает на вход набор строк в указанном в условии задачи формате.

Выходные данные
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите, в круглых скобках, общее число приобретенных ништячков, затем, после двоеточия, выведите список названий всех приобретенных данным программистом ништячков в лексикографическом порядке, после названия каждого ништячка выведите количество единиц приобретенного ништячка. Информация о каждом ништячке выводится в отдельной строке.
 
Примеры
№ Входные данные Выходные данные
1 
Ivanov paper 10
Petrov pens 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5

Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pens 5
Словари
✓ 0✗ 1—Войти и решать
Запас продуктов - 2#38783
Знайка из Цветочного города изобрел ракету. Для полета на Луну было решено сделать запас некоторого количества различных продуктов. После опроса всех коротышек, у Знайки оказался на руках очень большой список, в котором записано пожелание каждого коротышшки в виде наименования продукта и количества упаковок. На собрании было решено, что не рационально брать с собой продукты, у которых суммарное количество упаковок меньше 50. Помогите коротышкам определить, запас каких продуктов делать не нужно. Выведите эти продукты в лексикографическом порядке (от a до z).

Входные данные
Программа получает список строк. Каждая строка содержит наименование продукта, затем через пробел идет количество упаковок, которое указал коротышка. Список заканчивается словом END!.

Выходные данные
Выведите наименование всех ненужных продуктов в лексикографическом порядке. Каждый продукт выводите в отдельной строке.
 
Примеры
№ Входные данные Выходные данные
1 
cookies 10
cookies 50
syrup 9
syrup 8
cookies 1
apples 2
END!

apples
syrup
Словари
✓ 140✗ 222600лёгкаяВойти и решать
Страны мира#38782

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


Входные данные
Программа получает на вход количество стран N. Далее идет N строк словаря: каждая строка начинается с названия страны, затем идут названия городов этой страны. В следующей строке записано число M, далее идут M слов - названия M городов. Гарантируертся, что такой город есть в словаре.

Выходные данные
Для каждого города выведите название страны, в которой он находится.
 
Пример
№ Входные данные Выходные данные
1 
2
Russia Moscow Petersburg Novgorod Kaluga
Ukraine Kiev Donetsk Odessa
3
Odessa
Moscow
Novgorod
 
Ukraine
Russia
Russia
реализацияСловари
✓ 68✗ 85600лёгкаяВойти и решать
Любимый фрукт#38781
У всех жителей Цветочного города спросили его любимый фрукт.  Определите самый любимый фрукт среди всех жителей Цветочного города.

Входные данные
Программа получает на вход текст (количество строк может быть много). Текст заканчивается строкой END!. 

Выходные данные
Выведите любимый фрукт среди всех жителей Цветочного города. Если таких фруктов несколько, выведите тот, который меньше в лексикографическом порядке.
 
Пример
№ Входные данные Выходные данные
1 apple orange banana banana orange
END!		 banana
Использование сортировкиСловари
✓ 65✗ 172600лёгкаяВойти и решать
Запас продуктов#38779
Знайка из Цветочного города изобрел ракету. В один прекрасный день было решено лететь на Луну. Для удачного полета, на ракете должен быть определенный запас продуктов. Чтобы любой коротышка не грустил во время полета, было решено у каждого спросить его любимый продукт и количество упаковок, которое ему необходимо на весь полет. В итоге у Знайки оказался на руках очень большой список, в котором наименования продуктов повторялось с разным количеством. Знайка просит вас о помощи. Ему нужен список продуктов в лексикографическом порядке с указанием общего числа упаковок каждого продукта.

Входные данные
Программа получает список строк. Каждая строка содержит наименование продукта, затем через пробел идет количество упаковок, которое указал коротышка. Список заканчивается словом END!.

Выходные данные
Выведите наименование всех продуктов в лексикографическом порядке, затем, через пробел, общее количество упаковок данного продукта.
 
Примеры
№ Входные данные Выходные данные
1 
cookies 10
cookies 5
syrup 9
syrup 8
cookies 1
END!

cookies 16
syrup 17
Словари
✓ 72✗ 98500лёгкаяВойти и решать
Воздушные шарики#38778
В Цветочном городе намечается Праздник Весны. К празднику было решено надуть большое количество воздушных шариков. Каждый коротышка получил неограниченный запас воздушных шариков. Чтобы ускорить подсчет надутых шариков, Винтик и Шпунтик изобрели робота, который ведет подсчет всех надутых шариков.

Каждый коротышка, в момент когда рядом с ним оказывается робот, может поступить одним из двух способов.
  1. Нажать кнопку 1, назвать свое имя и сказать, сколько он надул шариков (назвать положительно число) или сколько шариков у него лопнуло (назвать отрицательное число). После этого робот считает количество надутых шаров у данного коротышки.
  2. Нажать кнопку 2, назвать имя любого коротышки. После этого робот показывает на экране количество надутых шаров у указанного коротышки.  Если робот еще ни разу не проезжал мимо указанного коротышки (не запоминал его шарики), то робот выдает слово ERROR.
Обратите внимание, что в ситуации, когда коротышка лопнул ровно столько шариков, сколько надул, сумма у робота становится равной 0; но, раз робот уже считал его шарики, нулевое значение не является основанием выводить ERROR.

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

Помогите Винтину и Шпунтику написать программу для робота. Обязательно используйте словари (ассоциативные массивы). 

Входные данные
Программа получает на вход количество запросов N (1 < N < 100000) - количество коротышек, мимо которых должен проехать робот. Далее следуют N строк в каждой из которых описаны способы выбора кнопок коротышкой.
Форматы строк:
- при нажатии кнопки 1: 1 <имя> <число>;
- при нажатии кнопки 2: 2 <имя>.
<имя> - любая последовательность латинских символов.


Выходные данные
При нажатии кнопки 2 программа должна выводить, с новой строки, текущее значение воздушных шариков у указанного коротышки (или слово ERROR). В последней строке необходимо вывести общее количество надутых шаров всеми коротышками.

 
Пример
№ Входные данные Выходные данные
1 
7
1 neznayka 3
1 ponchik 5
2 neznayka
1 neznayka -2
2 neznayka
2 lala
2 ponchik
 
3
1
ERROR
5
6
Словари
✓ 116✗ 124700средняяВойти и решать
Acowdemia II#38117
Беси поступает на работу в компьютерную лабораторию. Она хочет определить степерь важности каждого из N работников лаборатории (1≤N≤100). Все степени важности различны. То есть, нет двух работников с одинаковой степенью важности. Для определения степени важности сотрудников Беси использует список публикаций лаборатории.

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

Например, если лаборатория состоит (в порядке возрастания важности) из студентки Elsie, проф. Mildred и проф. Dean, они могут быть авторами статьи (Elsie-Mildred-Dean), если они все внесли различное количество усилий. А именно, Elsie внесла больше усилий чем Mildred, а Mildred больше чем Dean. Однако у них также может быть статья в порядке Elsie-Dean-Mildred если Mildred и Dean внесли одинаковое количество усилий, а Elsie больше их обоих.

По заданным K публикациям этой лаборатории (1≤K≤100), помогите Беси определить для всех пар сотрудников этой лаборатории кто более важен, если это возможно определить.

ФОРМАТ ВВОДА 
Первая строка содержит два целых числа K и N.
Вторая строка содержит N разделённых одиночными пробелами строк, содержащих имена членов лаборатории. Каждое имя состоит не более чем из 10 маленьких латинских букв.

Каждая из следующих K строк содержит N разделённых одиночными пробелами строк, указывающих список авторов в одной публикации.

ФОРМАТ ВЫВОДА 
Вывод должен состоять из N строк, по N символов в строке. На строке i, для любого j≠i, j-ый символ должен быть 1, если i-ый член более важный чем j-ый, 0, если i-ый член менее важный чем j-ый, и ? если невозможно определить при заданном списке публикаций.
i-ый символ в строке i должен быть B потому что это любимый символ Беси.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 1 3
dean elsie mildred
elsie mildred dean		 B11
0B?
0?B		 В первом примере одна статья (elsie-mildred-dean) не даёт достаточно информации, чтобы определить кто важнее elsie или mildred. Однако точно Dean более важен чем оба. Поэтому возможны оба порядка Elsie<Mildred<Dean и Mildred<Elsie<Dean
2 2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred		 B00
1B0
11B		 В этом втором примере единственный возможный порядок удовлетворяющий обоим статьям: Elsie<Mildred<Dean поскольку вторая публикация помогает определить, что Mildred важнее, чем Elsie.

 
Словари
✓ 5✗ 31 100средняяВойти и решать
Стич учит английский#37878
Лило и Нани учат Стича английским словам. Кроме запоминания самих слов, Стичу необходимо правильно расставлять в них ударения. У Нани есть словарь, который содержит все английские слова с указанием ударения в них.
Лило решила потренировать Стича правильно произносить слова. Но так как сама еще не выучила некоторые слова, то для проверки использует словарь Нани. К сожалению, в этом словаре присутствуют не все слова. Лило решила, что в словах, которых нет в словаре, она будет считать, что ударение поставлено верно, если оно поставлено только на одну букву.
Оказалось, что в некоторых словах ударение может быть поставлено больше, чем одним способом. В этом случае слово можно произносить по разному.

Используя данный словарь, проверьте речь Стича на правильность расстановки ударения. Определите количество ошибок, которое сделает Стич.

Входные данные
Сначала вводится число N — количество слов в словаре (\(0 <= N <=20000\)).
Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет запись разговора Стича. Разговор представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Стич поставил ударение). Стич мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные 
Выведите количество ошибок в речи Стича.
 
Примеры
№ Входные данные Выходные данные Примечание
1 
4
cAnnot
cannOt
fOund
pAge
thE pAge cAnnot be found
 
2
 В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Стичем - это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Стич поставил ровно одно ударение, признается верным.
2 
4
cAnnot
cannOt
fOund
pAge
The PAGE cannot be found
 
4
 Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

 

Словари
✓ 310✗ 848600лёгкаяВойти и решать
Самое главное – это семья!#37876

Одна из самых известных цитат из мультфильма: «Охана — значит семья, в семье не бросят никого и никогда и не забудут…» Что тут еще добавить? Так и есть!

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


Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует \(N-1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид:
имя_потомка имя_родителя.

Далее до конца файла идут строки, содержащие имена двух элементов дерева.


Выходные данные
Для каждого такого запроса выведите одно из трех чисел:
1 - если первый элемент является предком второго;
2 - если второй является предком первого;
0 - если ни один из них не является предком другого.

 

Примеры
№ Входные данные Выходные данные
1 
9
Keaka Kayla
Ikika Kayla
Akeneki Kayla
Neolani Keaka
Ley Ikika
Kianalu Ley
Aalona Kianalu
Iukini Kianalu
Ikika Iukini
Neolani Kayla
Keaka Kianalu
END!	
1 2 0

 

Словари
✓ 149✗ 434800средняяВойти и решать
Настоящие друзья всегда заботятся друг о друге#37875
Стич всегда готов поделиться кусочком пирога с другом, помочь Лило построить лучший замок из песка и приготовить завтрак для всей семьи. Бери пример :)

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


Входные данные
Каждая строка содержит название блюда, затем через пробел идет количество (натуральное число не превышающее 500000). Последняя строка содержит единственное слово "END!" - признак окончания ввода.

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

 
Примеры
№ Входные данные Выходные данные
1 Yapper 10
Yapper 5
Clip 9
Clip 8
Yapper 1
END!		 Clip 17
Yapper 16

 

Словари
✓ 534✗ 534500лёгкаяВойти и решать
Каждый имеет право на второй шанс#37874

Стич - генетический эксперимент 626, созданный злым гением Джамбой Джукибой. И на сколько бы милым не получился Стич по окончании эксперимента, Джамбо все-таки увидел в нем разрушительный потенциал и продолжил работу над ним. Но до того, как закончить работу над Стичем они оба были задержаны Галактической полицией.
Стич был приговорен Верховной Советницей к пожизненной ссылке на пустынный астероид, но по пути сбегает и оказывается на нашей планете на гавайском острове Кауаи, где любовь и забота Лило превратили злого инопланетянина в доброго и отзывчивого друга! Джамбо Джукибо - инопланетянин с планеты Квилтакуан (Kweltikwan). Был отправлен на Землю для поимки Эксперимента 626. Чтобы миссия состоялась Джамбо должен был изучить английский язык. Для этого он создал англо-квилтакуанский словарь. К каждому английскому слову, которое он встречал, Джамбо записывал в словарь несколько слов-переводов на квилтакуанском.
К сожалению, он поздно понял, что ему также необходим квилтакуанско-английский словарь. Он решил сделать квилтакуанско-английский словарь из англо-квилтакуанского за время полета. 
Для каждого квилтакуанского слова, встречающегося в словаре, Джамбо хочет найти все его переводы (то есть все английские слова, для которых квилтакуанское слово встречалось в его списке переводов), и считать их и только их переводами этого квилтакуанского слова.
Помогите Джамбо выполнить работу по созданию квилтакуанско-английского словаря, чтобы он успел к моменту прилета на нашу планету его выучить.

Входные данные
В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на квилтакуанский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.
Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100000.

Выходные данные
Выведите соответствующий данному квилтакуанско-английский словарь, в точности соблюдая формат входных данных. В первой строке необходимо вывести, количество слов в словаре. Далее в каждой отдельной строке должны идти слова и их перевод. В частности, первым должен идти перевод лексикографически минимального квилтакуанского слова, далее — второго в этом порядке и т.д. 

Порядок вывода слов может быть любым. Это касается как самих слов в словаре, так и слов, означающих перевод.

 

Примеры
№ Входные данные Выходные данные
1 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

 

Словари
✓ 172✗ 454700средняяВойти и решать
Стич считает слова#37873
Жизнерадостный инопланетянин Стич пытается освоиться на нашей планете и выучить английский язык. Пока он мало что может произнести, но уже может отличить одно слово от другого, хотя возможно он их и не понимает. Сейчас Стич проводит наблюдения за Лилой, и для каждого услышанного слова он произносит сколько раз оно уже было произнесено Лилой ранее. Когда Лило надоедает слушать бормочущего Стича, она называет его по имени и Стич останавливается. Джамба Джукиба, который стал другом Лило и Нани, решил проверить Стича, правильно ли он ведет счет. Помогите ему написать для этого программу.

Пояснение
Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов или символами конца строки. 

Входные данные
Программа получает на вход текст. Признаком конца текста является слово STITCH, которое располагается в последней строке, других слов в последней строке нет. 

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

 

Примеры
№ Входные данные Выходные данные
1 one two one tho three
STITCH		 0 0 1 0 0
2 a b a c a b a d a b a c a b a
STITCH		 0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 

 

Словари
✓ 104✗ 148600лёгкаяВойти и решать
Поделиться
Класснуть