#113130

Имена собственные

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г., Имена собственные ] [ Личные олимпиады, Нижегородская олимпиада школьников, XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г., Задача A ]

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

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

Более формально: вам дан текст, содержащий только английские маленькие и большие буквы, пробелы, переводы строк и знаки препинания. Символы «точка», «восклицательный знак» и «вопросительный знак» считаются символами конца предложения , они разбивают текст на предложения. А именно, первым предложением считается последовательность символов от начала текста до первого символа конца предложения, вторым предложением "— последовательность символов между первым и вторым символами конца предложения, и т.д.

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

Слово считается частью имени собственного , если оно начинается с большой буквы и при этом не является первым словом в предложении. Именем собственным считается каждая последовательность слов"=частей имени собственного, принадлежащих одному предложению и ограниченных с обеих сторон или концами предложения, или словами, не являющимися частями имени собственного.

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

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

Выходной файл содержит заданный текст. В тексте встречаются только маленькие и большие латинские буквы, пробелы, переводы строки и следующие знаки препинания: !?.;:,"()- . Длина текста не превосходит 100 000 символов. Гарантируется, что текст заканчивается на символ конца предложения, после которого могут идти несколько пробелов и/или переводов строки.

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

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

Слова в имени собственном разделяйте пробелами; знаки препинания должны отсутствовать в выходном файле.

Примеры

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

This is the living-room of the house
occupied by the eminent Professor
Michael Verres-Evans, and his wife,
Mrs Petunia Evans-Verres, and
their adopted son, Harry James
Potter-Evans-Verres. There is a 
letter lying on the living-room
table, and an unstamped envelope of 
yellowish parchment, addressed to 
Mr H Potter in emerald-green ink.

The Professor and his wife are 
speaking sharply at each other, 
but they are not shouting. 
The Professor considers shouting 
to be uncivilised.

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

Professor Michael Verres Evans 
Mrs Petunia Evans Verres 
Harry James Potter Evans Verres 
Mr H Potter 
Professor 
Professor

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

The week after Taffimai Metallumai
(we will still call her Taffy, Best Beloved) 
made that little mistake about her Daddy spear
and the Stranger-man and the picture-letter
and all, she went carp-fishing again with
her Daddy. Her Mummy wanted her to stay at
home and help hang up hides to dry on the
big drying-poles outside their Neolithic
Cave, but Taffy slipped away down to her
Daddy quite early, and they fished.

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

Taffimai Metallumai 
Taffy Best Beloved 
Daddy 
Stranger 
Daddy 
Mummy 
Neolithic Cave 
Taffy 
Daddy

#113131

B

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г., Задача B ]

На сайте Берляндских Железных Дорог (БЖД) любой может купить билет. Для этого ему лишь нужно заполнить несложную форму, а затем пройти еще несколько простых шагов. Руководство БЖД недавно задумалось о том, насколько легко людям использовать эту форму, и поручило вам провести измерения, чтобы оптимизировать количество действий, нужных для заполнения формы.

Форма состоит из двух полей: станция отправления и станция назначения. Когда человек заходит на сайт, в этих полях уже введены станции — те, которые сайт считает наиболее вероятными. Также под каждым полем есть список названий некоторых, самых популярных, станций — клик по элементу списка подставляет название станции в соответствующее поле. Наконец, есть кнопка «Поменять местами станцию отправления и станцию назначения». Кроме того, конечно, пользователь также волен ввести названия нужных ему станций вручную. К сожалению, из-за ошибки в коде сайта, редактировать введенное или выбранное название нельзя, можно только ввести его заново.

Для целей эксперимента клик по кнопке смены станций отправления и назначения или по станции в списке популярных станций оценивается в одно очко действия. Ввод названия станции вручную стоит столько очков действия, сколько символов (включая пробелы и дефисы) содержит это название.

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

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

В первой строке входного файла записано количество тестов в этом файле — единственное целое число K (1 ≤ K ≤ 10) . В последующих строках записаны K тестов.

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

В третьей строке — текущее введенное название станции отправления. В четвертой строке — текущее введенное название станции назначения.

В пятой строке — одно целое число N (0 ≤ N ≤ 100) — количество популярных вариантов станции отправления. В следующих N строках записаны эти варианты, по одному на строке. Все варианты различны.

После этого записано количество популярных вариантов станции назначения — одно целое число M (0 ≤ M ≤ 100) . В следующих M строках записаны эти варианты, по одному на строке. Все варианты различны.

Названия станций могут состоять из больших и маленьких латинских букв, пробелов и дефисов. Длина каждого названия не превышает 100 символов. Названия станций всегда начинаются и заканчиваются буквой. Любой пробел или дефис обязательно окружен буквами.

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

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

Примечание

Первый пример состоит из двух тестов. В первом тесте пользователю достаточно кликнуть по Nizhny Novgorod в списке популярных станций отправления, чтобы заменить Samara на желаемую станцию отправления, а затем кликнуть по Moskva в списке популярных станций назначения, чтобы заменить Petrozavodsk на желаемую станцию. Два клика требуют двух очков действия.

Во втором тесте у пользователя нет выбора, кроме как ввести названия станций вручную. Ввод Moskva потребует 6 очков действий, а ввод Nizhny Novgorod — 15 очков. В сумме требуется 21 очко.

Второй пример стоит из единственного теста. В этом тесте пользователю достаточно сначала кликнуть по Nizhny Novgorod в списке популярных станций отправления, а затем нажать на кнопку «Поменять местами станцию отправления и станцию назначения». На это потребуется два очка.

Иллюстрация ко второму примеру:

$\text{[math]}$

Примеры

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

2
Nizhny Novgorod
Moskva
Samara
Petrozavodsk
2
Arkhangelsk
Nizhny Novgorod
2
Moskva
Samara
Moskva
Nizhny Novgorod
Moskv
Novgorod
2
Arkhangelsk
Ulyanovsk
2
Volgograd
Samara

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

2
21

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

1
Moskva
Nizhny Novgorod
Arkhangelsk
Moskva
3
Nizhny Novgorod
Ulyanovsk
Kazan
3
Volgograd
Kazan
Samara

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

#113132

C

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г., Задача C ]

На доске записано n целых чисел a ₁ , a ₂ , ..., a _n . Миша может стереть любые два числа a _i и a _j и вместо них записать их сумму a _i + a _j . При этом Миша выплачивает своему другу Жене количество монет, равное минимуму из этих двух стертых чисел.

Миша хочет оставить на доске ровно одно число, отдав Жене как можно меньше монет. Помогите ему в этом.

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

В первой строке входных данных находится число n ( 1 ≤ n ≤ 10 ³ ). Во второй строке находится последовательность чисел a ₁ , a ₂ , ..., a _n , записанная через пробелы ( 1 ≤ a _i ≤ 10 ³ ).

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

Выведите единственное число — минимальное количество монет, которое необходимо Мише заплатить Жене, чтобы на доске осталось ровно одно число.

Примечание

Во втором примере Миша может сначала стереть числа 20 и 30 и записать на доске число 50. Затем стереть числа 10 и 50 и записать 60. Итого Миша должен отдать Жене 20 + 10 = 30 монет.

Примеры

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

2
7 3

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

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

3
10 20 30

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

#113133

D

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г., Задача D ]

Недавно Петин учитель рассказал ему об операции деления с остатком. Число p называется частным , а число q — остатком от деления x на y , если x = y · p + q , а также 0 ≤ q < y , и p и q целые. С вычислением частного у Пети проблем не возникает, а вот получение остатка дается ему с трудом. Но так как Петя — отличник, он решил поупражнятся в вычислении остатка.

Дома Петя нашел его любимую последовательность чисел a ₁ , a ₂ , ..., a _n . Теперь Петя будет выбирать числа b ₁ , b ₂ , ..., b _m и с каждым b _i из них выполнять следующие операции:

Делить с остатком b _i на a ₁ ,
Получившийся остаток делить с остатком на a ₂ ,
Получившийся после второй операции остаток делить на a ₃ , и так далее,
...
Остаток от ( n - 1) -ого деления делить с остатком на a _n .

Для того, чтобы проверять себя, Петя попросил вас написать программу, которая по заданным последовательностям a ₁ , a ₂ , ..., a _n и b ₁ , b ₂ , ..., b _m найдет для каждого b _i остаток от последнего ( n -ого) деления. Помогите Пете!

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

В первой строке входных данных находится число n ( 1 ≤ n ≤ 10 ⁵ ). Во второй строке находится последовательность a ₁ , a ₂ , ..., a _n , записанная через пробелы ( 1 ≤ a _i ≤ 10 ⁹ ). Далее следует число m ( 1 ≤ m ≤ 10 ⁵ ), а после него на четвертой строке — числа b ₁ , b ₂ , ..., b _m , разделенные пробелами ( 0 ≤ b _i ≤ 10 ⁹ ). Все числа во входных данных целые.

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

Выведите m чисел — остатки от последней операции для каждого b _i .

Примечание

В примере b ₃ = 27 . Последовательность действий, выполняемая Петей, будет следующая. Сначала разделим 27 на a ₁ = 10 , получим в остатке 7. Далее разделим 7 на a ₂ = 9 , получим в остатке 7. Разделим 7 на a ₃ = 5 , получим в остатке 2. Разделим 2 на a ₄ = 7 , получим в остатке 2, это и будет число, которое необходимо вывести.

Примеры

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

4
10 9 5 7
5
14 8 27 11 25

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

4 3 2 1 0

#113134

Передача опыта

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, XII Городская олимпиада школьников по информатике им. В. Д. Лелюха, 2016 г., Задача E ]

Как известно, Берляндия — хорошо развитая страна, а поэтому в каждом городе есть школа. На недавнем съезде учителей стало ясно, что методики преподавания различных предметов во всех школах разные. Чтобы исправить это недоразумение, а также для улучшения качества образования было решено, что школам необходимо обмениваться опытом. Так как школы действительно разные, и у каждой имеется уникальный опыт, поступило предложение из каждой школы в каждую другую отправить делегата для перенимания опыта.

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

Каждой дорогой владеет одна из K компаний, и для проезда по дорогам любой компании человек должен один раз купить проездной у этой компании. После этого он может проезжать по любым дорогам этой компании без дополнительной платы. Стоимость проездного i -ой компании ( 1 ≤ i ≤ K ) равна c _i бурлей.

Каждому из делегатов нужно купить необходимые ему проездные. Помогите учителям посчитать, сколько же всего бурлей будут стоить все проездные для всех делегатов. Так как это число может быть большим, найдите остаток от деления этого числа на 1 000 000 007 ( 10 ⁹ + 7 ).

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

В первой строке входных данных находятся два натуральных числа N и K ( 1 ≤ N ≤ 1 500 000 , 1 ≤ K ≤ 1 500 000 ) — число городов в Берляндии и число компаний-владельцев дорог соответственно. На следующих ( N - 1) строках дано описание дорог Берляндии, на i -ой из этих строк (эти строки нумеруются с единицы, города тоже нумеруются с единицы) находятся два числа b _i и t _i ( 1 ≤ b _i ≤ N , 1 ≤ t _i ≤ K ), означающие, что существует дорога из города с номером i + 1 в город с номером b _i , и владеет ей компания с номером t _i . По всем дорогам можно передвигаться в обе стороны; также, гарантируется, что из любого города можно добраться в любой другой по существующим дорогам.

На последней строке входных данных находятся 4 числа A , B , C , c ₀ ( 1 ≤ C ≤ 1 000 000 001 , 0 ≤ A , B , c ₀ < C ), задающие стоимости проездных. Стоимости проездных вычисляются по формуле $\text{[math]}$ , где c _i "— стоимость проездного i -ой компании, а « $\text{[math]}$ » — остаток от деления X на Y .

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

Выведите единственное число — остаток от деления суммарной стоимости необходимых проездных на 1 000 000 007 .

Примечание

$\text{[math]}$

В первом тесте из примера карта дорог выглядит так, как показано на рисунке. Кружками обозначены города, линиями — дороги, а числа в квадратах около дорог обозначают номера компаний, обслуживающих эти дороги. Цены проездных в этом примере равны c ₁ = 3 бурля, c ₂ = 5 бурлей. Таким образом, делегаты, едущие из первого города в третий, или обратно, должны купить оба проездных, остальным делегатам нужно проехать только одну дорогу, поэтому им нужно купить только один проездной. Итоговая стоимость проездных равна 2·(3 + 5) + 2·3 + 2·5 = 32 бурлей.

Во втором тесте схема дорог выглядит так же, а компания-владелец только одна. Стоимость проездного равна 3 бурля. Поэтому все 6 делегатов должны купить единственный проездной, и суммарная стоимость 6·3 = 18 бурлей.

Тесты, в которых выполняются дополнительные ограничения 1 ≤ N , K ≤ 100 , имеют суммарную стоимость не менее 30 баллов.

Тесты, в которых выполняются дополнительные ограничения 1 ≤ N , K ≤ 1000 , имеют суммарную стоимость не менее 50 баллов.

Тесты, в которых выполняются дополнительные ограничения 1 ≤ N , K ≤ 100 000 , имеют суммарную стоимость не менее 75 баллов.

Примеры

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

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

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

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