В этом году для помощи в подготовке олимпиады IQ ПФО жюри решило пригласить Рудольфа, раз уж он является главным героем всех задач. Рудольф с радостью согласился и не только придумал несколько задач о себе, но и предложил членам жюри для интереса сделать ставки на результаты решения задач.
Сначала каждый из N членов жюри вносит в банк S биткойнов, формируя призовой фонд. Затем каждый член жюри делает прогноз, записывая, сколько команд, по его мнению, решат первую, вторую, ..., последнюю задачу. В олимпиаде участвуют M команд, а пакет включает K задач.
Погрешностью прогноза по одной задаче называется модуль разности между прогнозируемым и фактическим количествами команд, решивших эту задачу. Общей погрешностью прогноза называется его суммарная погрешность по всем задачам. Призовой фонд получает тот член жюри, прогноз которого имеет наименьшую общую погрешность. Если победителей несколько, то они делят призовой фонд поровну (с округлением вниз).
Помогите членам жюри определить наиболее точный прогноз и выяснить, сколько биткойнов получит его автор.
Первая строка содержит целые числа N, S, M и K (1 ≤ N ≤ 1000, 1 ≤ S ≤ 105, 1 ≤ M ≤ 1000, 1 ≤ K ≤ 1000) — соответственно количество членов жюри, размер ставки каждого из членов жюри, количество команд-участников олимпиады и количество задач.
Следующие N строк описывают прогнозы членов жюри. Каждая из них содержит последовательность Si, состоящую из строчных латинских букв и цифр, а также K целых чисел Pij (1 ≤ |Si| ≤ 20, 0 ≤ Pij ≤ M) — соответственно имя члена жюри и количество команд, которым, по его мнению, удастся решить 1-ю, 2-ю, ..., K-ю задачу. Все имена членов жюри различны.
Следующие M строк описывают результаты олимпиады. Каждая из них содержит последовательность Ti, состоящую из строчных латинских букв и цифр, а также K разделённых пробелами символов Rij (1 ≤ |Ti| ≤ 20, 
+, -
) — соответственно название команды и её результат по 1-й, 2-й, ..., K-й задаче. Символ + означает, что команда решила задачу, символ - означает, что команда не решила задачу. Все названия команд различны.
Выведите одно целое число — выигрыш автора наиболее точного прогноза.
2 10 3 2
rudolph 1 2
linsierra 3 1
team1 + -
team2 + -
team3 + +
20
4 3 3 4
rudolph 3 3 1 3
linsierra 2 2 1 3
zhrv 2 1 0 3
javarthur 1 1 1 3
welovegena + + - +
welovepetya + - - +
welovefood - - + +
4
Некоторое время назад Рудольф активно покупал книги по программированию и алгоритмам. Каждая из этих книг относилась к определённой коллекции — например, «Магический мир модулярной математики» или «Укконен (и его друзья) для самых маленьких».
К сожалению, Рудольфу не всегда удавалось приобрести все выходящие книги, поэтому сейчас у него скопилось N неполных книжных коллекций. Рудольф хочет оставить только полные коллекции, поэтому он решил, что с каждой из имеющихся коллекций он поступит одним из двух способов — либо докупит недостающие книги, либо продаст имеющиеся.
В интернет-магазинах Рудольфу удалось найти все интересующие книги, и теперь он знает, что i-ю из его коллекций можно сделать полной за Ai рублей либо продать за Bi рублей.
У Рудольфа есть M рублей, которые он может потратить на приобретение книг; кроме того, приобретать книги можно и на деньги, вырученные от продажи книг. Рудольф хочет собрать как можно больше полных коллекций. Помогите ему определить, какое максимальное количество коллекций он сможет получить, если будет покупать и продавать книги оптимальным образом.
Первая строка содержит целое число N (1 ≤ N ≤ 1000) — количество неполных книжных коллекций у Рудольфа.
Следующие N строк описывают книжные коллекции. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai, Bi ≤ 106) — соответственно стоимость покупки недостающих книг и стоимость продажи имеющихся книг.
Следующая строка содержит целое число M (0 ≤ M ≤ 106) — начальное количество денег у Рудольфа.
Выведите одно целое число — максимальное количество полных коллекций, которое может собрать Рудольф.
3
600 600
200 800
300 550
415
2
6
130 160
110 170
190 120
180 130
180 180
100 170
170
3
Прекрасным летним вечером, хорошо поработав лопатой в саду, вдохновлённый Рудольф решил создать лучшую компьютерную игру. В его памяти еще были свежи воспоминания о дурманящем запахе ромашек, растущих на грядках сада, и о вредителях, неутомимых упырях, постоянно пытающихся погрызть корни ромашек.
Рудольф решил посвятить свою игру извечной борьбе ромашек и упырей.
Перед началом сражения двое героев — Ромашка и Упырь — располагаются друг напротив друга. Каждый из героев изначально имеет по N единиц жизни, а также по K солдат в резерве. Солдаты необходимы для защиты героя и нанесения урона противнику; каждый из них характеризуется силой атаки Ai и запасом жизней Hi.
Сражение разделено на фазы, каждая из которых проходит следующим образом:
У каждого героя в любой момент сражения может быть не более одного защитника. Сами герои не могут атаковать.
Сражение завершается, если запас жизней одного из героев станет меньше либо равен нулю (тогда этот герой проигрывает), либо если у обоих героев погибают все солдаты (тогда объявляется ничья).
Рудольф попросил вас написать программу, которая определит, существует ли стратегия гарантированной победы Ромашек или гарантированной победы Упырей.
Первая строка содержит целые числа N и K (1 ≤ N ≤ 30, 1 ≤ K ≤ 5) — соответственно начальное количество единиц жизни у героев и начальное количество солдат в резерве героев.
Следующие K строк описывают солдат из резерва Ромашек. Каждая из них содержит целые числа Ai и Hi (1 ≤ Ai, Hi ≤ 8) — соответственно силу атаки и запас жизней солдата.
Следующие K строк описывают солдат из резерва Упырей в аналогичном формате.
Выведите FLOWER, если гарантированно победят Ромашки, GHOUL, если гарантированно победят Упыри, либо TIE в случае, если невозможно однозначно определить победителя.
10 3
1 2
2 3
3 4
2 5
1 1
3 2
FLOWER
1 4
1 6
7 3
8 1
2 7
5 1
1 1
6 1
4 7
TIE
13 3
4 2
2 5
6 1
8 4
4 8
5 4
GHOUL
В честь своего дня рождения Рудольф решил украсить собственный дом. В кладовке Рудольф нашёл несколько ленточек красного и синего цвета, и теперь он собирается связать их концы друг с другом так, чтобы получилась длинная красно-синяя лента-гирлянда.
Рудольф хочет, чтобы цвета ленточек в гирлянде постоянно чередовались, а сама лента имела как можно большую длину. Помогите ему выяснить, гирлянду какой длины он может получить.
Первая строка содержит целые числа N и M (1 ≤ N, M ≤ 1000) — соответственно количество красных и синих ленточек.
Вторая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 109) — длины каждой из красных ленточек.
Третья строка содержит M целых чисел Bi (1 ≤ Bi ≤ 109) — длины каждой из синих ленточек.
Выведите одно целое число — максимальную длину гирлянды, которую можно связать из ленточек чередующихся цветов.
3 2
50 100 25
5 60
240
3 3
8 5 12
4 7 18
54
Если вы уже участвовали в нашей олимпиаде, то, вероятно, помните, что в прошлом году Рудольф приобрёл N томов Сверхбольшой Энциклопедии Структур Данных, а его друзья Леонидас и Роберт помогли ему изготовить книжные шкафы.
Рудольфу пришлось потрудиться с заполнением шкафов, поскольку тома энциклопедии требовали расстановки в специальном правильном порядке. Так или иначе, в этом году вышло новое издание Энциклопедии, и количество томов в нём многократно возросло! Рудольф с ужасом размышляет о том, сколько работы по расстановке томов придётся проделать на этот раз, поэтому вновь просит вас о помощи.
Тома энциклопедии нумеруются различными целыми числами от 1 до N. Правильный порядок предполагает, что тома расставлены по возрастанию количества единичных бит в двоичном представлении их номеров, а если для нескольких томов это количество совпадает — по возрастанию номеров томов.
Тома ставятся в шкаф начиная с верхней полки, слева направо. Очередной том ставится в следующий шкаф только тогда, когда предыдущий шкаф полностью заполнен.
Помогите Рудольфу написать программу, которая подскажет, как расставить тома энциклопедии в конкретном шкафу.
Первая строка содержит целые числа N, L и K (1 ≤ N ≤ 1018, 1 ≤ L, K ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке.
Вторая строка содержит целое число M (1 ≤ M ≤ 1018) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф M будет заполнен полностью или частично.
Выведите одну или более строк, каждая из которых содержит номера томов энциклопедии, размещённых в шкафу M, в правильном порядке.
10 2 3
2
6
9
10
7
6 2 2
1
1
2
4
3
Рудольф увлёкся рисованием и купил себе краски P различных цветов. В процессе художественного творчества Рудольф обнаружил два интересных факта:
Чтобы проверить своё предположение, Рудольф составил карту смешивания цветов — для каждой пары цветов (C1, C2) он определил цвет C3, который получится при их перемешивании (при этом не важно, добавлялся ли цвет C2 к цвету C1 или цвет C1 к цвету C2).
Теперь он хочет узнать, существует ли такой набор цветов (не обязательно различных), смешивая которые в различном порядке, можно получить различные цвета. Помогите ему найти ответ на этот вопрос.
Первая строка содержит целое число P (1 ≤ P ≤ 100) — количество цветов в палитре.
Следующие 
строк описывают правила перемешивания цветов. Каждая из них содержит последовательности Ci1, Ci2 и Ci3 (1 ≤ |Ci1|, |Ci2|, |Ci3| ≤ 100), состоящие из строчных латинских букв, — соответственно названия двух смешиваемых цветов и название цвета, получаемого в результате смешивания.
Выведите YES, если хотя бы для одного набора цветов порядок смешивания влияет на результирующий цвет, либо NO, если результирующий цвет никогда не зависит от порядка смешивания.
2
blue green blue
blue blue green
green green green
NO
2
blue green green
blue blue green
green green blue
YES
Во втором примере можно рассмотреть набор цветов (blue, green, green).
Порядок смешивания ((blue + green) + green) даёт результирующий цвет blue.
Порядок смешивания (blue + (green + green)) даёт результирующий цвет green.
Рудольф решил создать специализированный форум математиков. Он хочет, чтобы на этом форуме сообщения составлялись в виде формул с помощью урезанного варианта системы 
— 
.
Система определяет сообщения форума как произвольную последовательность одного или более следующих элементов:
Более формально допустимые сообщения форума можно описать следующей БНФ-грамматикой:
Statement ::= Expression | Expression Statement Expression ::= Expression «+» Element | Expression «-» Element | Element Element ::= Identifier | Number | Command | Fraction | Function Identifier ::= Letter | Letter Identifier Number ::= Digit | Digit Number Command ::= «\» Identifier Fraction ::= «\frac» Symbol Symbol | . «\frac» Symbol «{» Statement «}» | . «\frac» «{» Statement «}» Symbol | . «\frac» «{» Statement «}» «{» Statement «}» Function ::= Identifier «{» Expression «}» Symbol ::= Letter | Digit Letter ::= «a» | «b» | «c» | ... | «z» Digit ::= «0» | «1» | «2» | ... | «9»
Иногда в тексте сообщения появляются «многоэтажные» дроби, и это портит внешний вид форума, так как сообщение не помещается в строке и «сползает» вниз. Поскольку Рудольф является ярым перфекционистом, он написал скрипт для выравнивания сообщения. Но для работы этого скрипта необходимо заранее знать высоту сообщения.
Высота сообщения зависит от используемого шрифта. Шрифт определяет размеры Hs — высоту отдельного символа и Hl — высоту горизонтальной дробной черты.
Ваша задача — помочь Рудольфу определить высоту сообщения по заданным параметрам шрифта и записи сообщения в формате .
Первая строка содержит целые числа Hs и Hl (1 ≤ Hs, Hl ≤ 104) — соответственно высоту букв шрифта и высоту дробной черты соответственно.
Вторая строка содержит описание сообщения на 'е, длина которого не превышает 1000 символов. Гарантируется, что сообщение соответствует приведенной в условии грамматике.
Выведите одно целое число — высоту сообщения.
10 2
\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}
34
10 2
no fractions here
10
10 2
\frac {alpha} {beta+sin{2+x}}
22
10 2
cos{\frac{alpha}b}
22
10 2
\frac a {sin{a}}
22
10 2
\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}
46
10 2
\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}
46
Если две дроби в сообщении принадлежат одному выражению или двум элементам одного уровня, то их дробные черты записываются на одном уровне, а если нет (например, относятся к числителям или знаменателям различных дробей), это свойство может и не выполняться. Например:
Рудольф является выдающимся специалистом по структурам данных, поэтому его пригласили прочесть лекцию для студентов университета. Чтобы сделать материал лекции более доступным для слушателей, Рудольф решил заранее приготовить и расположить на сцене множество наглядных пособий. Теперь ему осталось только проверить, что сцена достаточно хорошо освещена.
Сцена имеет ширину W и может быть представлена отрезком [0; W]. Над сценой закреплены N прожекторов.
Каждый прожектор характеризуется координатой X, мощностью A и рассеянием B. При включении прожектора освещённость сцены изменяется следующим образом:
Помогите Рудольфу определить, насколько хорошо будут освещены определённые точки сцены после включения всех прожекторов.
Первая строка содержит целое число W (1 ≤ W ≤ 106) — ширину сцены.
Вторая строка содержит целое число N (1 ≤ N ≤ 5·105) — количество прожекторов.
Следующие N строк описывают прожекторы. Каждая из них содержит целые числа Xi, Ai и Bi (0 ≤ Xi ≤ W, 1 ≤ Ai ≤ 106, 1 ≤ Bi ≤ Ai) — соответственно координату, мощность и рассеяние i-го прожектора.
Следующая строка содержит целое число M (1 ≤ M ≤ 5·105) — количество точек, для которых необходимо определить освещённость.
Следующая строка содержит M целых чисел Xj (0 ≤ Xj ≤ W) — координаты точек, для которых необходимо определить освещённость.
Выведите M целых чисел — освещённость каждой из искомых точек.
10
1
6 4 1
11
0 1 2 3 4 5 6 7 8 9 10
0 0 0 1 2 3 4 3 2 1 0
10
2
3 10 1
7 5 2
10
0 1 2 3 9 8 7 6 3 4
7 8 9 10 5 8 11 10 10 9
Рудольф наконец-то выкроил время и решил заняться написанием автобиографии. И в этот самый момент он подумал о том, как несправедлива жизнь — ведь числа, которые он так любит, наверняка тоже хотят иметь автобиографию. Рудольф решился это исправить, сформулировав такое свойство чисел, которое можно было бы назвать «автобиографией». И такое свойство действительно нашлось, правда, не все числа могут им похвастаться.
Назовём автобиографическим целое неотрицательное число N, записанное в десятичной системе счисления, в котором первая слева цифра совпадает с количеством нулей, вторая слева цифра — с количеством единиц, третья слева цифра — с количеством двоек и так далее. Более формально, автобиографическим называется число, в котором цифра, стоящая в позиции i (позиции нумеруются с нуля слева направо), равна количеству цифр i в данном числе. Например, число 1210 является автобиографическим.
Помогите Рудольфу определить, сколько автобиографических чисел находится в диапазоне от L до R включительно.
Ввод содержит целые числа L и R (0 ≤ L ≤ R ≤ 1018) — границы диапазона.
Выведите единственное целое число — количество автобиографических чисел в диапазоне от L до R.
1000 1300
1
0 10
0
Рудольф вновь разрабатывает компьютерную игру. На этот раз для победы в ней нужно защитить город, разделённый на квадратные клетки, от падения бомб.
Каждая бомба имеет параметры X и Y — координаты клетки, в которую она упадёт, а также параметр R — радиус поражения. Считается, что клетка с координатами (X1, Y1) находится в зоне поражения бомбы, упавшей в клетку с координатами (X, Y), если выполняется неравенство |X - X1| + |Y - Y1| ≤ R.
В настоящее время Рудольф пишет функцию, определяющую ущерб, нанесённый городу бомбами. Помогите Рудольфу определить суммарное количество клеток, которые оказались в зоне поражения хотя бы одной бомбы.
Первая строка содержит целое число N (1 ≤ N ≤ 2000) — количество бомб.
Следующие N строк описывают бомбы. Каждая из них содержит целые числа Xi, Yi и Ri ( - 109 ≤ Xi, Yi ≤ 109, 0 ≤ Ri ≤ 2000) — соответственно координаты падения и радиус взрыва i-й бомбы.
Выведите одно целое число — суммарное количество клеток, которые оказались в зоне поражения хотя бы одной бомбы.
1
0 0 3
25
2
0 0 1
1 0 1
8
Иллюстрация ко второму примеру:
