Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 32981. Распродажа
Темы: "Два указателя"    Словари   

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

Входные данные
Первая строка входных данных содержит общее количество ценников N, 2 <= N <= 105, N – чётное число. Следующие N строк содержат целые положительные числа, не превосходящие 109, идущие в порядке неубывания по одному в строке – числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны,то есть решение существует.

Выходные данные
Программа должна вывести N/2  целых чисел в порядке неубывания – стоимости товаров после понижения цен.

 
Примеры
Входные данные Выходные данные Примечание
1
6
30
40
42
45
56
60
30
42
45
До распродажи цены товаров были 40, 56, 60, после снижения цены
на эти товары стали равны 30, 42, 45.

ID 37788. Синонимы
Темы: Словари   

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

Входные данные
Программа получает на вход количество пар синонимов N. Далее следует N строк, в каждой из которых содержится ровно два слова-синонима. В последней N+1 строке следует одно слово.

Выходные данные
Выведите на экран синоним к данному слову.

Примечание
Используйте в своей программе словарь.
 


Примеры
Входные данные Выходные данные
1 2
Dictionary Map 
List Array
Array
List

 

ID 29635. Интернет-магазин
Темы: Словари   

Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида:
Покупатель товар количество,
где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара.
 
Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.
 
 
Входные данные
В первой строке входного файла содержится число N (\(1<=N<=100000\)) —количество записей содержащихся в данной базе данных. Вводятся сведения о покупках в указанном формате.
 
Выходные данные 
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.
 
 
Пример
Входные данные Выходные данные
1
6
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

ID 29634. Файловая система
Темы: Словари   

В файловую систему одного суперкомпьютера проник вирус, который сломал контроль за правами доступа к файлам. Для каждого файла Ni известно, с какими действиями можно к нему обращаться:
 
запись W
чтение R
запуск X
 
Вам требуется восстановить контроль над правами доступа к файлам (ваша программа для каждого запроса должна будет возвращать OK, если над файлом выполняется допустимая операция, или же Access denied, если операция недопустима).
 
Входные данные
В первой строке содержится число N (1 <= N <= 10000) - количество файлов содержащихся в данной файловой системе.
В следующих N строках содержатся имена файлов и допустимых с ними операций, разделенные пробелами. Длина имени файла не превышает 15 символов.
Далее указано число M (1 <= M <= 50000) - количество запросов к файлам.
В последних M строках указан запрос вида Операция Файл. К одному и тому же файлу может быть применено любое количество запросов.
 
Выходные данные
Для каждого из M запросов нужно вывести в отдельной строке Access denied или OK.
 
 
Пример
Входные данные Выходные данные
1
4
helloworld.exe R X
pinglog W R
nya R
goodluck X W R
5
read nya
write helloworld.exe
execute nya
read pinglog
write pinglog
OK
Access denied
Access denied
OK
OK

ID 37852. Сортируем словарь
Темы: Словари   

Алфавитно-частотный словарь - это частотный словарь, в котором слова с указанием их частоты (встречаемости) расположены по алфавиту.
Постройте словарь, отсортированный по частоте слов, в котором слова расположены порядке уменьшения их частоты встречаемости, справа от каждого слова должно быть указано сколько раз оно встречается в тексте. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке.  Признаком окончания текста является "END!". 

Входные данные
На вход подаются строки текста. Последняя строка содержит одно единственное слово "END!" и является признаком окончания текста.

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

 

Примеры
Входные данные Выходные данные
1 один два
три один
два
END!
два 2
один 2
три 1

ID 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

ID 30711. Словарь синонимов
Темы: Словари   

Вам дан словарь, состоящий из пар слов. Каждое слово является синонимом к парному ему слову. Все слова в словаре различны. Для одного данного слова определите его синоним.
 
Входные данные
Программа получает на вход количество пар синонимов N. Далее следует N строк, каждая строка содержит ровно два слова-синонима. После этого следует одно слово.
 
Выходные данные
Программа должна вывести синоним к данному слову.
 
Пример
Входные данные Выходные данные
1
3
Hello Hi
Bye Goodbye
List Array
Goodbye
Bye

ID 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 

 

ID 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

 

ID 37875. Настоящие друзья всегда заботятся друг о друге
Темы: Словари   

Стич всегда готов поделиться кусочком пирога с другом, помочь Лило построить лучший замок из песка и приготовить завтрак для всей семьи. Бери пример :)

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


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

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

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

 

ID 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), либо не поставлено ни одного ударения.

 

ID 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

 

ID 38117. Acowdemia II
Темы: Словари   

Беси поступает на работу в компьютерную лабораторию. Она хочет определить степерь важности каждого из 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.

 

ID 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

ID 38779. Запас продуктов
Темы: Словари   

Знайка из Цветочного города изобрел ракету. В один прекрасный день было решено лететь на Луну. Для удачного полета, на ракете должен быть определенный запас продуктов. Чтобы любой коротышка не грустил во время полета, было решено у каждого спросить его любимый продукт и количество упаковок, которое ему необходимо на весь полет. В итоге у Знайки оказался на руках очень большой список, в котором наименования продуктов повторялось с разным количеством. Знайка просит вас о помощи. Ему нужен список продуктов в лексикографическом порядке с указанием общего числа упаковок каждого продукта.

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

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

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

ID 38783. Запас продуктов - 2
Темы: Словари   

Знайка из Цветочного города изобрел ракету. Для полета на Луну было решено сделать запас некоторого количества различных продуктов. После опроса всех коротышек, у Знайки оказался на руках очень большой список, в котором записано пожелание каждого коротышшки в виде наименования продукта и количества упаковок. На собрании было решено, что не рационально брать с собой продукты, у которых суммарное количество упаковок меньше 50. Помогите коротышкам определить, запас каких продуктов делать не нужно. Выведите эти продукты в лексикографическом порядке (от a до z).

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

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

Примеры
Входные данные Выходные данные
1
cookies 10
cookies 50
syrup 9
syrup 8
cookies 1
apples 2
END!
apples
syrup

ID 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

ID 38787. Свойства объектов - 1
Темы: Словари   

В хранилище Васи находится 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 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.
 

ID 38788. Свойства объектов - 2
Темы: Словари   

В хранилище Васи находится 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 нет ни у одного объекта, поэтому его удаление не меняет количество удаленных свойств у объектов.
 

ID 38789. Пропуск в общежитие - 2
Темы: Словари   

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

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

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

ID 38790. Пропуск в общежитие - 1
Темы: Словари   

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

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

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

ID 38791. Подматрица - 1
Темы: Словари   

У Фили есть квадратная матрица 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

ID 38835. 3 коровы
Темы: Словари   

Склиссы — "сумчатые парнокопытные" в виде коровы с перепончатыми крыльями с планеты Шешинеру. Несмотря на способность летать, склисс, как и любая земная корова, достаточно ленива и тугодумна. 
Профессор Игорь Селезнев взял на борт трех склиссов для изучения: Бесси (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 Милдред сравняется с Бесси, что опять приведёт к смене карточек.

ID 43792. Генераторы словарей - 1
Темы: Словари   

Используя генератор, запишите одну строку, которая получит словарь result , в котором ключом будет позиция числа в списке numbers (начиная с 0), а значением – его квадрат.
 

Пример списка numbers
numbers = [34, 10, -4, 6]

ID 43793. Генераторы словарей - 2
Темы: Словари   

Используя генератор, запишите одну строку, которая получит словарь result , состоящий из всех элементов словаря colors, кроме тех, у которых значением является None.
 

Пример словаря colors
colors = {'c1': 'Red', 'c2': 'Grey', 'c3': None, 'c4': 'Green'}

ID 43794. Генераторы словарей - 3
Темы: Словари   

Используя генератор, запишите одну строку, которая получит словарь result , состоящий из всех элементов словаря favorite_numbers, значения которых являются двузначным числом.
 

Пример словаря favorite_numbers
f = {'timur': 17, 'ruslan': 7, 'larisa': 19, 'roman': 123}

ID 43795. Генераторы словарей - 4
Темы: Словари   

В переменной s хранится строка пар число:слово. Используя генератор, запишите одну строку, которая получит словарь result , в котором числа будут ключами, а слова – значениями. Ключи словаря должны быть целыми числами (иметь тип int), значения – строками (иметь тип str).

 
Пример строки s
s = '1:men 2:kind 90:number 0:sun 34:book'