Задача 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^5$. Выходной файл должен содержать такое же количество строк, сколько запросов возраста было во входном файле. Для каждого такого запроса нужно вывести строку, содержащую соответствующее число — ответ на запрос. При этом, если при количество мух с возрастом от $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$). Каждая строка состоит только из строчных букв английского алфавита ('$a$'...'$z$'). Третья строка содержит число $A$, четвертая — $B$, $0 \le A, B \le N$. Выходной файл должен содержать ответ к задаче — количество возможных паролей. Вход

ab
ac
1
1

Ответ

24

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

Задача D. Делители

Вам дано несколько чисел. Для каждого из чисел посчитайте количество делителей. Первая строка входного файла содержит число $N$ — количество чисел, для которых нужно посчитать количество делителей ($1 \le N \le 50$). Каждая из следующих $N$ строк содержит одно целое число в пределах от $1$ до $10^{14}$. В выходной файл выведите $N$ строк — по одной строке для каждого числа из входного файла. Каждая строка должна содержать одно число — количество делителей соответствующего числа. Вход

2
1
6

Ответ

1
4

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

Бесконечным троичным деревом назовем дерево, каждая вершина которого имеет ровно $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$ до $16$ символов — шаблон пути. В выходной файл выведите одно число — ответ к задаче. Вход

*LS

Ответ

55

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

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

3 3
1 1 1
1 1 1
10 1 1
1 1
3 3

Ответ

5
1 0 0
1 1 0
0 1 1