#113129

Лягушачьи бои

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2016, Задача E ]

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

Итак, лягушек выставляют на поле, имеющее форму кольца, разделённого на $m$ клеток. Клетки пронумерованы от $1$ до $m$ по кругу, после клетки номер $m$ идёт клетка номер $1$. $i$-я лягушка изначально может прыгнуть на $a_i$ клеток вперёд.

Лягушки ходят по очереди, начиная с лягушки с номером $1$. На своём ходу $i$-я лягушка прыгает на $\text{a}_i$ клеток вперёд, сбрасывая с поля всех других лягушек на своём пути, в том числе и ту, которая находится в конечной клетке текущего прыжка. После этого её значение $a_i$ уменьшается на количество удалённых во время данного прыжка лягушек. Если $a_i$ становится равным нулю или отрицательным, то $i$-я лягушка не сможет прыгать в дальнейшем.

После того, как лягушка с номером $1$ заканчивает свой ход, ходит лягушка с номером $2$, затем лягушка с номером $3$ и так далее. После того, как сходит лягушка с номером $n$, снова ходит лягушка с номером $1$. Если лягушка с каким-то номером уже была сброшена с поля, то считается, что она всегда пропускает свой ход. Великому комбинатору уже не терпится узнать, какие из лягушек в конце концов останутся на поле. Помогите ему узнать это.

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

В первой строке содержатся два числа $n$ и $m$ ($1 \le n \le 100\,000, 2 \le m \le 10^9, n \le m$) — количество лягушек и размер поля соответственно.

В следующих $n$ строках содержатся описания лягушек. Каждое описание состоит из двух чисел $p_i$ и $a_i$ ($1 \le p_i,\, a_i \le m$) — номер клетки, на которой стоит лягушка, и изначальная длина её прыжка соответственно.

Гарантируется, что все значения $p_i$ различны.

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

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

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

Пояснения к примерам

В первом примере первая лягушка прыгает на одну клетку и оказывается в клетке номер $3$. Затем вторая прыгает на $3$ клетки и также оказывается в клетке номер $3$, удаляя при этом первую лягушку с поля. Величина следующего прыжка у неё теперь равна $2$. Третья лягушка прыгает в клетку номер $2$. Затем вторая лягушка прыгает в клетку $5$. Третья догоняет её и удаляет с поля. На поле осталась только она.

Во втором примере первая лягушка прыгает на две клетки, удаляя с поля лягушек, стоящих на клетках $2$ и $3$. Величина её следующего прыжка при этом становится равной нулю. Затем прыгает четвёртая лягушка, удаляет с поля пятую и тоже останавливается. В итоге на поле остаются две лягушки.

Примеры

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

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

1
3

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

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

2
1 4

#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