#1307

Конвейер

Темы: [Стек] [Быстрая сортировка] [Вещественные числа]

Источники: [ Личные олимпиады, Украинские олимпиады, 1999, 1 день, Задача A ]

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

Для транспортирования материалов из цеха А в цех В используется конвейер. Материалы упаковываются в одинаковые контейнеры и размещаются на ленте один за одним в порядке изготовления в цехе А. Каждый контейнер имеет степень срочности обработки в цехе В. Для упорядочивания контейнеров по степени срочности используют накопитель, который находится в конце конвейера перед входом в цех В. Накопитель работает пошагово, на каждом шаге возможны следующие действия:

накопитель перемещает первый контейнер из ленты в цех В;

накопитель перемещает первый контейнер из строки в склад (в складе каждый следующий контейнер помещается на предыдущий);

накопитель перемещает верхний контейнер из склада в цех В.

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

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

Входной файл в первой строке содержит количество тестов N. Далее следует N строк, каждый из которых описывает отдельный тест и содержит целое число K (1 ≤ K ≤ 10000) — количество контейнеров в последовательности и K действительных чисел — степеней срочности контейнеров в порядке их поступления из цеха А (меньшим числам соответствует большая степень срочности).

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

Каждая строка выходного файла должна содержать ответ для одного теста. Необходимо вывести 1, если необходимое упорядочивание возможно, или 0 в противном случае.

Примеры

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

2
2 2.9 2.1
3 5.6 9.0 2.0

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

1
0

#1396

Эволюция

Темы: ["Длинная" арифметика] [Деревья]

Источники: [ Личные олимпиады, Украинские олимпиады, 2009, Задача D ]

>Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:

Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

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

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

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

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

Единственная строка выходного файла должна содержать натуральное число – номер ближайшего предка для двух видов.

Примеры

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

4
15
12

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

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

18
233016
233008

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

#1638

Скалы

Темы: [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Украинские олимпиады, 2005, Задача E ]

Ограничение по времени: 0.2 секунды

На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x \(L\) метров, на котором введены координаты, как показано на рисунке.

Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой \(H\) поставить в точку с \(X\)-координатой \(p\), то в каждой точке \(q\) отрезка [\(p\)–\(H\);\(p\)] на оси \(X\) рельеф поднимается на \(q\)–\(p\)+\(H\) метров по всей его ширине (то есть для произвольного \(Z\) от 0 до 1), а в каждой точке \(q\) отрезка [\(p\);\(p\)+\(H\)] рельеф поднимается на \(H\)+\(p\)–\(q\) метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).

Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.

Напишите программу, которая поможет рабочим в их расчётах.

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

В первой строке входного файла содержатся два целых числа: N – количество операций, которые будут выполнять рабочие (1≤\(N\)≤100000), и \(L\) – длина прямоугольника (1≤\(L\)≤100000).

В следующих \(N\) строках содержатся описания операций: первое число строки – номер операции, где „1” означает, что рабочие собираются поставить магический импульсатор, „2” – рабочие хотят узнать некоторый объём. Если операция имеет код „1”, то далее идут два целых числа \(p\) и \(H\) (0≤\(p\)≤\(L\); 1≤\(H\)≤\(L\)), то есть импульсатор силой \(H\) ставят в позицию p (на оси \(X\)). Если операция имеет код „2”, то далее идут два целых числа \(A\) и \(B\) (0≤\(A\)<\(B\)≤\(L\)); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\).

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

Создайте выходной файл, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.

Если операция есть „1”, то выведите число „-1” без кавычек. Если операция есть „2”, то выведите число округленное вниз до ближайшего целого, равное объёму части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\), как показано на рисунке.

Примеры

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

2 13
1 7 5
2 5 9

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

-1
16

#113251

Подчисло

Темы: [Декартово дерево]

Источники: [ Личные олимпиады, Украинские олимпиады, 2016, Подчисло ]

Петрик и Василько — настоящие друзья, поэтому они постоянно задают друг другу всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил придумать по-настоящему сложную задачу. И вот что у него получилось. Будем называть число b подчислом числа a , если из числа a можно вычеркнуть некоторые цифры так, что цифры, которые остались, образуют число b . Задано n -цифровое число x . Обозначим как x _k наибольшее k -цифровое подчисло числа x . Необходимо ответить на m запросов. Каждый запрос состоит из двух цифр - k и l . Ответом на запрос является l -я цифра числа x _k . На этот раз задача действительно заставила Василько задуматься. А сможете ли вы решить ее быстрее его?

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

В первой строке входного файла содержится целое число x длины n ( 1 ≤ n ≤ 100 000 ). Во второй строке содержится число m ( 1 ≤ m ≤ 50 000 ). В следующих m строках содержится по два числа k _i , l _i ( 1 ≤ k _i ≤ n , 1 ≤ l _i ≤ k _i ) — параметры i -го запроса.

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

Выходной файл должен содержать одну строку длины m , i -й символ которого является ответом на i -й запрос.

Примечание

n = 20, m = 10 000 .( 15 баллов)
n · m ≤ 500 000 .( 25 баллов)
n ≤ 100 000, m ≤ 50 000 .( 60 баллов)

Примеры

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

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