Задача A. Муха

Из двух городов, находящихся на расстоянии $D$, в момент времени $0$ навстречу друг другу выехали два велосипедиста со скоростью $V_1$ и $V_2$ соответственно. Одновременно с первым велосипедистом из первого города навстречу второму вылетела муха со скоростью $W$ ($W \ge max(V_1, V_2)$). Когда муха долетает до второго велосипедиста, она мгновенно разворачивается и летит обратно. Долетев до первого велосипедиста, она опять разворачивается и так далее. Определите, сколько раз развернется муха строго до момента времени $T$. Входной файл содержит $5$ неотрицательных целых чисел: $D$, $V_1$, $V_2$, $W$, $T$ ($T \cdot (V_1 + V_2) < D$). Никакое из чисел не превышает $10^7$. Выходной файл должен содержать одно целое число — ответ к задаче. Вход

10 0 0 10 10

Ответ

9

Вход

20 1 2 3 4

Ответ

0

Задача B. Фокус

Помните про фокус с мухами, который изобрел Баха? Жома решил посоревноваться с ним и придумал свой фокус! У Жомы есть ящик. Он может запускать туда муху или выпускать. Также, он как хороший дрессировщик знает возраст каждой мухи в минутах с момента ее рождения. А фокус заключается вот в чем: в любой момент он может назвать возраст $K$-й по старшинству мухи, которая находится в ящике среди мух с возрастом от $A$ до $B$ включительно. Попробуйте и вы сделать этот фокус! Первая строка входного файла содержит число $N$ — общее количество событий ($1 \le N \le 2 \cdot 10^5$). Далее следует $N$ строк, каждая из которых описывает одно из событий:

• $+ X$ — в ящик впустили муху с возрастом $X$;
• $- X$ — из ящика выпустили муху с возрастом $X$;
• $? K A B$ — у фокусника спросили возраст $K$-й по старшинству мухи в ящике среди мух с возрастом от $A$ до $B$ включительно ($1 \le K \le 10^5$, $A \le B$);

Возраст мухи ($X$, $A$, $B$) — целое число от $1$ до $10^9$. Выходной файл должен содержать такое же количество строк, сколько запросов возраста было во входном файле. Для каждого такого запроса нужно вывести строку, содержащую соответствующее число — ответ на запрос. При этом, если при количество мух с возрастом от $A$ до $B$ в ящике меньше $K$, то нужно вывести $0$. Вход

8
+ 2
+ 3
+ 2
? 2 2 3
- 2
? 2 2 3
- 2
? 2 2 3

Ответ

2
3
0

Задача C. Пароль

Жома любит использовать длинные и сложные пароли. И, как это обычно бывает, он забыл... Забыл пароль от домашнего компьютера и теперь не может поиграть в новую NFS! Он очень расстроен и даже пару раз попытался вспомнить свой пароль. Но, увы, ничего не получилось. Однако он уверен, что при первой попытке он не ошибся ровно в $A$ символах, а при второй — ровно в $B$, но он не знает, какие именно символы были введены без ошибок. И тут его заинтересовало, сколько же паролей удовлетворяют заданным условиям? Первая строка содержит первую попытку ввода пароля, вторая строка — вторую. Длины обеих строк одинаковы и равны $N$ ($1 \le N \le 10^5$). Каждая строка состоит только из строчных букв английского алфавита ('$a$'...'$z$'). Третья строка содержит число $A$, четвертая — $B$, $0 \le A, B \le N$. Выходной файл должен содержать ответ к задаче — остаток от деления количества возможных паролей на $10^9 + 7$. Вход

ab
ac
1
1

Ответ

24

Возможные пароли в примере: $aa$, $ad$, $ae$, ... $az$.

Задача D. Путь в дереве

Бесконечным троичным деревом назовем дерево, каждая вершина которого имеет ровно $3$ потомка. В вершинах дерева написаны числа по следующему правилу:

• в корне дерева написано $1$;
• пусть в некоторой вершине написано $X$, тогда в левом сыне этой вершины будет написано $X \cdot 3$, в среднем — $X \cdot 3 + 1$, в правом — $X \cdot 3 + 2$.

\includegraphics[width=150mm,height=40mm,trim=-130mm 200mm 0 0,clip]{images/ternary.eps} Шаблоном пути назовем строку длины $N$, состоящую из символов $L$, $C$, $R$, $S$, $*$. Первой вершиной пути является корень дерева. Каждый символ строки показывает, куда следует идти на очередном шаге:

• $L$ — в левого сына
• $C$ — в среднего сына
• $R$ — в правого сына
• $S$ — стоять на месте
• $*$ — означает любой из предыдущих символов ($L$, $C$, $R$, $S$)

Стоимостью пути назовем сумму чисел в вершинах пути (каждая вершина считается ровно один раз). От вас требуется вычислить суммарную стоимость всех путей, по которым можно пройти, если следовать заданному шаблону. Входной файл содержит строку длиной от $1$ до $2000$ символов — шаблон пути. В выходной файл выведите одно число без ведущих нулей — ответ к задаче. Вход

*LS

Ответ

55

Гарантируется, что в некотором подмножестве тестов, суммарно не превышающих $50$ баллов $N \le 14$.

Задача E. Физкультура

В список предметных олимпиад школьников решили, наконец, внести и физкультуру, в частности, спортивную ходьбу, бег без препятствий, бег с препятствиями, бег в мешках и так далее. Оргкомитет должен подготовить по одному маршруту для каждого вида соревнований. Для проведения соревнований была выделена прямоугольная территория, которую для удобства разделили на квадраты так, что получилась сетка $N \times M$. Для каждого квадрата была определена стоимость его подготовки к соревнованиям. Также были определены квадраты, в которых могут начинаться и оканчиваться маршруты участников. Маршрутом будем считать такую последовательность квадратов, что каждые два соседних квадрата в этой последовательности имеют общую сторону. Так как все виды соревнований будут проводиться параллельно, никакие два маршрута не должны пересекаться по квадратам, иначе участники будут мешать друг другу. Ваша задача — помочь оргкомитету выбрать маршруты так, чтобы суммарная стоимость подготовки их к соревнованиям была минимально возможной. Первая строка входного файла содержит три целых числа: $N$, $M$ и $K$ ($1 \le N, M, K \le 30$), где $N$, $M$ — размеры территории, а $K$ — количество видов соревнований. Каждая из следующих $N$ строк содержит по $M$ целых чисел в пределах от $1$ до $100$ — стоимость подготовки соответствующего квадрата к соревнованиям. Следующие $K$ строк содержат по $2$ целых числа — номер строки и столбца для квадрата, в котором может начинаться какой-нибудь маршрут. Последние $K$ строк содержат также по $2$ целых числа — номер строки и столбца для квадрата, в котором может заканчиваться какой-нибудь маршрут. Никакой квадрат не перечислен во входном файле дважды. Числа в строках разделены пробелами. В выходной файл нужно вывести ``$No solution$'', если невозможно выбрать $K$ маршрутов, удовлетворяющих условию. В противном случае на первой строке выведите наименьшую суммарную стоимость подготовки, а на следующих строках — карту маршрутов. Карта маршрутов — это таблица размера $N \times M$, в $j$-м столбце $i$-й строки которой расположен $0$, если через соответствующих квадрат не проходит ни один маршрут, и целое положительное число $X$ ($1 \le X \le K)$, если через него проходит маршрут для соревнования $X$. Если оптимальных ответов несколько, то выведите любой. Числа в строках разделяйте пробелом. Вход

3 3 2
1 1 1
1 1 1
10 1 1
1 1
1 3
3 2
3 3

Ответ

7
2 0 1
2 2 1
0 2 1

Гарантируется, что в некотором подмножестве тестов, суммарно не превышающем $50$ баллов, $K = 1$.

Задача F. Магазины

Город представляет собой выпуклый многоугольник. В городе имеется несколько магазинов. Каждый житель города ходит только в ближайший к нему магазин. Если ближайших магазинов несколько, то житель никуда не ходит. Для каждого магазина посчитайте, площадь территории, жители которой ходят в этот магазин. Первая строка содержит целое число $N$ — количество вершин многоугольника, представляющего город ($3 \le N \le 50$). Каждая из следующих $N$ строк содержит по $2$ целых числа — координаты вершин в порядке обхода против часовой стрелки. Следующая строка содержит целое число $M$ — количество магазинов в городе ($1 \le M \le 50$). Каждая из следующих $M$ строк содержит по $2$ целых числа — координаты магазинов ($i$-я строка - координаты $i$-го магазина). Все точки различны. Координаты точек не превышают по абсолютному значению $10000$. Числа в строках разделены пробелами. Выведите $M$ вещественных чисел через пробел: $i$-е число — площадь, обслуживаемая $i$-м магазином округленная до двух цифр после десятичной точки. Вход

4
0 0
4 0
4 4
0 4
2
1 2
3 2

Ответ

8.00
8.00

Гарантируется, что в некотором подмножестве тестов, суммарно не превышающем $50$ баллов, $M \le 2$.