e-olymp 1225. Черный Ящик

Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

Транзакция $i$ Содержимое Черного Ящика после транзакции Ответ
1 ADD(3) 0 3
2 GET 1 3 3
3 ADD(1) 1 1, 3
4 GET 2 1, 3 3
5 ADD(-4) 2 -4, 1, 3
6 ADD(2) 2 -4, 1, 2, 3
7 ADD(8) 2 -4, 1, 2, 3, 8
8 ADD(-1000) 2 -1000, -4, 1, 2, 3, 8
9 GET 3 -1000, -4, 1, 2, 3, 8 1
10 GET 4 -1000, -4, 1, 2, 3, 8 2
11 ADD(2) 4 -1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

  1. $A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
  2. $u_1, \ u_2, \ldots , \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

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

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

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

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Тесты

Входные данные Выходные данные
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
3
3
1
2
8 3
5 8 3 7 3 5 7 0
2 3 3
5
5
8
10 4
6 3 7 3 8 4 7 4 6 15
4 6 8 9
3
3
4
4
5 5
1 2 3 4 5
1 2 3 4 5
1
2
3
4
5
11 5
4 6 8 9 5 3 6 8 10 12 13
6 7 8 9 10
3
4
5
6
6

Код программы

Решение задачи

Пусть nums — множество всех элементов последовательности $A_n$. blackBox — мультимножество, представляющее собой описанный в задаче Черный Ящик на $i$-ом запросе. Изначально blackBox содержит «бесконечность» для избежания выхода за пределы. it — итератор, указывающий на $i$-ый минимальный элемент blackBox. Изначально данный итератор указывает на первый элемент множества. На $i$-ом запросе в blackBox копируются элементы массива nums от $u_{i-1}-1$-го до $u_{i}-1$-го (примем, что $u_0$ = 0). Тогда при добавлении в blackBox элемента, меньшего, чем тот, на который в данный момент указывает итератор it — $min_i$, $i$-ым минимальным элементом, становится элемент, предшествующий $min_i$. После выполнения ответа на $i$-ый запрос итератор должен указывать на $i+1$-ый минимальный элемент, то есть на элемент, следующий за $min_i$.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 440. Подделка чека

Задача

Один из способов мошенничества, разработанных О. Бендером, заключался в следующем. Он вырезал полоску бумаги, содержащую несколько цифр из суммы чека (можно вырезать и крайние цифры), разрезал ее на две части, переставлял эти две части местами и аккуратно подклеивал обратно. Напишите программу, определяющую максимальное число, которое может быть получено в результате указанной манипуляции.

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

Во входном файле в первой строке содержится одно целое положительное число не более чем из $100$ цифр.

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

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

Тесты

Входные данные Выходные данные
$123321$ $332121$
$7888778888878888788878878777887$ $8888878888788878887778878777887$
$1091$ $9100$
$26364$ $64263$
$98765$ $98765$

Код программы

String

C-String

Решение задачи

Пусть заданы два числа: $a = \overline{a_1a_2 \ldots a_k},\ b = \overline{b_1b_2 \ldots b_k}$. Тогда $a > b \Leftrightarrow \exists i: \ \forall j < i \ a_j = b_j \ \wedge \ a_i = b_i$. Отсюда получаем необходимое условие получения максимального числа при перестановке в записи числа $a$ групп цифр $\overline{a_ia_{i+1} \ldots a_l}$ и $\overline{a_ja_{j+1} \ldots a_m} \ l<j$ местами: $i = \min_{1 < s < k} s: \ \exists t>s: \ a_t \gt a_s$. Если такое $i$ существует, то далее мы делаем перебор по всем возможным перестановкам, таким что первая группа чисел начинается с индекса $i$ и таким образом находим максимально возможное число. В противном случае данное число уже является максимальным.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp. String
Решение на e-olymp. C-String
Код решения на Ideone. String
Код решения на Ideone. C-String

e-olymp 88. Месть Ли Чака

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 480. Возведение в степень — 2

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

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

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

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

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\ \text{ при } B \equiv 1 \pmod 2\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 61. Уборка снега

Задача

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

  • Снегоход может очищать только одну проезжую полосу дороги за один проход.
  • Все дороги прямые с одной полосой движения в каждом направлении.
  • Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
  • Во время очистки снега снегоход двигается со скоростью $20$ км/час, и со скоростью $50$ км/час по уже очищенной дороге.
  • Возможность проехать все дороги всегда существует.

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

Первая строка содержит два числа $x$ и $y$ $(-30000 ≤ x, y ≤ 30000)$ — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

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

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

Тесты

Входные данные Выходные данные
$0$ $0$
$0$ $0$ $-1000$ $2000$
$0$ $0$ $1000$ $2000$
$0:27$
$0$ $1000$
$0$ $0$ $0$ $3000$
$0$ $0$ $1000$ $1000$
$0$ $0$ $3000$ $0$
$3000$ $0$ $3000$ $3000$
$3000$ $3000$ $0$ $3000$
$0$ $3000$ $1000$ $2000$
$3000$ $0$ $2000$ $1000$
$3000$ $3000$ $2000$ $2000$
$1:46$
$-500$ $0$
$-1000$ $0$ $0$ $0$
$0$ $0$ $1000$ $0$
$-1000$ $1000$ $0$ $0$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1000$ $1000$ $0$ $1000$
$0$ $1000$ $0$ $0$
$0:49$
$1000$ $500$
$-1000$ $0$ $1000$ $0$
$-1000$ $1000$ $1000$ $1000$
$-1000$ $0$ $-1000$ $1000$
$1000$ $0$ $1000$ $1000$
$-1000$ $0$ $1000$ $1000$
$1000$ $0$ $-1000$ $1000$
$-1000$ $1000$ $0$ $2000$
$0$ $2000$ $1000$ $1000$
$1:20$
$500$ $-500$
$0$ $0$ $1000$ $-1000$
$1000$ $-1000$ $2000$ $0$
$2000$ $0$ $3000$ $-1000$
$3000$ $-1000$ $4000$ $0$
$4000$ $0$ $5000$ $-1000$
$5000$ $-1000$ $6000$ $0$
$0$ $0$ $8000$ $0$
$1:39$

Код программы

Решение задачи

Начало пути всегда находится на одной из данных дорог. Составим оптимальный алгоритм движения снегохода. По каждой из дорог необходимо проехать в одну и другую сторону. Снегоход может начинать движение в любую сторону. Во время движения ему необходимо двигаться прямо, не разворачиваясь, настолько долго, насколько это возможно. В случае, если на пути следования снегоходу встречается поворот, ему необходимо повернуть и далее работать по тому же алгоритму, принимая за начальную точку точку поворота. После возвращения из поворота снегоход должен продолжить движение по алгоритму. Когда снегоход попадает в тупик, возвращается на перекресток, на котором был совершен поворот или попадает в начальную точку, ему необходимо развернуться и двигаться обратно по той же траектории. По возвращении в начальную точку снегоход должен, в случае необходимости, двигаться во все оставшиеся стороны по такому же алгоритму. Таким образом, при движении по такому алгоритму, снегоход будет проезжать по каждой дороге по одному разу в каждую сторону, то есть не будет нигде проезжать «лишние» километры, следовательно время, за которое снегоход может объехать все дороги по одному разу в каждую сторону и есть искомым. Таким образом нам необходимо посчитать сумму длин всех дорог $L$, координаты начала и конца которых даны во входном потоке. Снегоход всегда двигается со скоростью $V = 20 км/час = \frac{1000}{3}м/мин$. По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах:
$t = \frac{2L}{V} = \frac{3L}{500}$.
Округлив полученное значение $t$ до целых минут и представив это время в виде часов и минут, получаем ответ.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 7107. Без лифта

Задача

Три друга – Андрей, Борис и Владимир живут соответственно на $a$, $b$ и $v$ этажах многоэтажного дома. Они занимаются спортом, поэтому никогда не пользуются лифтом. Однажды им потребовалось срочно встретиться у кого-то из них дома.

Составьте программу, которая определяла бы номер этажа, на котором они встретятся, при чем время до встречи было бы минимальным. Учтите, что скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема.

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

Программа получает на вход три натуральных числа – номера этажей, на которых живут друзья ($1 \leq a, b, v \leq 28$).

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

Программа выводит номер этажа, на котором они встречаются.

Тесты

Входные данные Выходные данные
$1$ $5$ $8$ $5$
$1$ $1$ $2$ $1$
$4$ $11$ $14$ $4$
$6$ $3$ $2$ $3$
$2$ $9$ $1$ $2$

Код программы

Решение задачи

По условию скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема. Назовем эту величину коэффициентом подъема.
Примем, что человек спускается на один этаж за единицу времени. Тогда он поднимается на один этаж за единицу времени, умноженную на коэффициент подъема.
Вначале необходимо установить, какой из этажей является максимальным, какой — минимальным, какой — промежуточным.
Очевидно, что друг, живущий на промежуточном этаже доберется до максимального этажа быстрее, чем тот, кто живет на минимальном, а также доберется до минимального этажа быстрее, чем тот, кто живет на максимальном. Кроме того, друг, живущий на максимальном этаже, быстрее спустится на минимальный этаж, чем живущий на минимальном поднимется на максимальный. Отсюда получаем, что если друзья будут подниматься на максимальный этаж, то потраченное время не будет наименьшим возможным. То есть друзья могут встретиться либо на минимальном, либо на промежуточном этаже. Время, потраченное на спуск на минимальный этаж, численно равно разнице между максимальным и минимальным этажом. Время, потраченное на путь к промежуточному этажу, численно равно максимуму между разницей между минимальным и промежуточным этажами, умноженной на коэффициент подъема и разницей между максимальным и промежуточным этажами. Так как разница между максимальным и промежуточным этажами всегда не превышает разницы между максимальным и минимальным этажами, то для определения искомого этажа нам достаточно сравнивать разницу между максимальным и минимальным этажами и разницу между минимальным и промежуточным этажами, умноженной на коэффициент подъема.
В случае, если первая величина будет меньше второй, то друзья должны встретиться на минимальном этаже, в противном случае — на промежуточном.

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

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone