Задача A. Топики ≡

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Кроме того, имеется P английских предложений. Каждое предложение состоит из одного или более слов. Между словами имеются произвольные последовательности разделителей, например first. :second third,,,,fourth. Предложение считается относящимся к i-й теме, если слов на эту тему в нём больше, чем на какую-либо другую. Если самые часто встречающиеся в предложении темы имеют одинаковую частоту, либо если в предложении вообще не встречается ни одного слова из словаря, то тема такого предложения считается неопределёной.

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

Формат входного файла

Входной файл содержит числа N P за которыми идут N строк вида wi ti, где wi — слово, ti — номер темы, а затем P строк, каждая из которых содержит одно предложение.

Формат выходного файла

В выходной файл должно быть выведено P чисел — темы предложений.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ P ≤ 2000, 1 ≤ ti ≤ 10000, длина каждого слова и каждого предложения не превосходит 255 символов,

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 6
a 1
b 2
c 3
a b c
a a b
a B b
c-a == c
d e f
This is a table.

0 1 2 3 0 1

Задача B. День бульдозериста ≡

Автор:И. Олейников, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

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

Требуется определить минимально необходимое число бульдозеров.

Формат входного файла

Входной файл содержит числа N и M за которыми идут M пар чисел ai bi — номера площадей, соединенных i-й улицей (по улице, соединяющей площади ai и bi, можно проехать либо из ai и bi, либо из bi в ai). Две площади могут быть соединены больше чем одной улицей.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 40000, 1 ≤ M ≤ 40000, 1 ≤ ai, bi ≤ N

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
1 2 
2 3 
3 1
 
1
2 
5 2 
1 2 
3 4
 
3

Задача C. Дружба и кефир ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Любимым напитком большинства учеников K-й средней школы является кефир. Однако, в последнее время в результате активной рекламной кампании всё больше учеников переходят на новый газированный напиток "UnhealthyCola". Этот факт беспокоит школьную администрацию. В результате социологического опроса учащихся выяснилось, что у каждого школьника в классе есть ближайшие друзья, с мнением которых он считается. Если больше половины ближайших друзей школьника уже пьют UnhealthyCola, то школьник поддаётся их дурному влиянию и, в свою очередь, влияет на оставшихся друзей. К сожалению, никакое количество друзей не способно переубедить школьника перейти обратно с UnhealthyCola на кефир.

На педагогическом совете было решено, что распространение UnhealthyCola можно было бы сдержать, если бы больше школьников дружили между собой.

Требуется подружить двух учеников школы таким образом, чтобы максимизировать количество школьников, которые останутся верны кефиру.

Формат входного файла

Входной файл содержит число школьников N, за которым идёт N чисел ci, где ci=0, если i-й ученик пьёт кефир, и ci=1, если он пьёт UnhealthyCola. Далее число пар друзей M, за которым идут M пар чисел ai bi, означающих, что школьники ai и bi — друзья.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 500, 0 ≤ M ≤ 1000, 1 ≤ ai, bi ≤ N

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
1 0 0
2
1 2
1 3

2 3
2 
9
1 0 0 0 0 1 1 1 0
7
1 2  2 3  3 4  4 5  6 2  7 3  8 4
 
9 2

Задача D. Ближайшая стенка ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Формат входного файла

Входной файл содержит число N за которым идут N троек чисел xi yi di  — координаты i-й точки и расстояние до ближайшей стороны. Все числа целые.

Формат выходного файла

Если решения не существует, то в выходной файл должно быть выведено число −1.

Если решение единственное, то в выходной файл должно быть выведено число 1, за которым следуют четыре целых числа x1 y1 x2 y2  — координаты двух противоположных вершин прямоугольника.

Если решений больше одного, то в выходной файл должно быть выведено число 0, за которым следуют четыре целых числа x1 y1 x2 y2  — координаты двух противоположных вершин любого прямоугольника, являющегося решением.

Ограничения

1 ≤ N ≤ 100, 0 ≤ xi, yi, di ≤ 10000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
50 50 1
 
0 49 49 51 51
2 
2
100 100 3 101 101 90
 
-1

Задача E. Салют ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Изображение праздничного салюта имеет вид прямоугольной таблицы, состоящей из H строк по W символов каждая. Салют представлен N вспышками различного радиуса. Вспышка радиуса 1 изображается символом '*' (ASCII 42), вспышка радиуса 2 выглядит так: 

\|/
-*-
/|\
Вспышка большего радиуса r изображается в виде центральной звёздочки и восьми расходящихся диагональных линий, нарисованных при помощи r-1 символов '-' (ASCII 45), '|' (ASCII 124), '/' (ASCII 47) либо '\' (ASCII 92) каждая. Все позиции, не занятые вспышками, должны быть заняты символами '.' (ASCII 46).

Требуется по описанию набора вспышек построить изображение салюта.

Формат входного файла

Входной файл содержит числа W H N за которыми идут N троек чисел xi yi ri, где x — номер колонки, y — номер строки, r — радиус вспышки.

Формат выходного файла

В выходной файл должно быть выведено H строк по W символов каждая — изображение салюта. Вспышки накладываются на изображение в том порядке, в котором они встречаются во входном файле.

Ограничения

1 ≤ W, H, N ≤ 100, −100 ≤ xi, yi ≤ 200, 1 ≤ ri ≤ 100

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
10 10 4
5 5 1
3 2 7
9 4 3
3 20 11
 
.\|/......
--*---\-|.
./|\...\|/
/.|.\.--*-
..|.*\./|\
..|.../.|.
..|....\..
..|.....\.
..........
..|.......

Задача F. rrrrr... ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Определим функцию r(p, q), где p и q — строки символов, следующим образом: функция удаляет первый символ из строки p, и присоединяет к концу получившейся строки первый символ строки q. Например, r('abc', 'def') = 'bcd'.

Исходя из данной строки x можно сгенерировать различные выражения, например r(x,x), r(r(x,r(x,x)),x) и т.п. Требуется сгенерировать выражение, значение которого равно строке y, либо определить, что это невозможно.

Формат входного файла

Входной файл содержит строки x и y.

Формат выходного файла

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

Ограничения

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

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
ab
ba
 
r(x,x)
2 
ab
xy
 
NO

Задача G. Отпуск программиста ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

После многих лет беспрерывной работы программист собрался наконец-то взять N дней отпуска. Во время отпуска он решил сходить в поход продолжительностью L дней.

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

Требуется определить оптимальный период для похода или выяснить, что сходить в поход не удастся. Если существует несколько оптимальных вариантов, следует вывести тот, который начинается раньше.

Формат входного файла

Входной файл содержит числа N L, за которыми следует N целых чисел ai — вероятности дождя в процентах.

Формат выходного файла

В выходной файл должно быть выведено единственное число — номер первого дня похода, либо −1, если поход невозможен.

Ограничения

1 ≤ L ≤ N ≤ 31, 0 ≤ ai ≤ 100

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 2
50 0 0 10
 
2
2 
7 3
0 75 64 30 0 0 100

-1
3 
10 4
0 0 1 2 0 3 4 0 100 0

2
0.163s 0.006s 25