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

Задачи из рубрикатора

Тег: Словари

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

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

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

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

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

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 строке.
 
Выходные данные
В выходной файл выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел #номер команды.
 
Ввод Вывод
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 37788: Синонимы
Синонимы
Темы: Словари   

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

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

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


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

 

ID 37873: Стич считает слова
Стич считает слова
Темы: Словари   

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

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

Входные данные: на вход подается текст. Признаком конца текста является слово 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 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 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 символов.
Далее указано чиcло 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 30711: Словарь синонимов
Словарь синонимов
Темы: Словари   

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

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

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

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


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

Выходные данные: выведите всех блюд в лексикографическом порядке, затем, через пробел, общее количество, которое необходимо приготовить Стичу.
 
Примеры
Входные данные Выходные данные
1 Yapper 10
Yapper 5
Clip 9
Clip 8
Yapper 1
END!
Clip 17
Yapper 16