--->
24 задач
<---
Источники
Современные компьютеры зацикливаются в десятки раз эффективнее человека
Рекламный проспект OS Vista-N
Перед возвращением в штаб-квартиру корпорации Аазу и Скиву пришлось заполнить на местной таможне декларацию о доходах за время визита. Получилась довольно внушительная последовательность чисел. Обработка этой последовательности заняла весьма долгое время.
— Своппер кривой, — со знанием дела сказал таможенник.
— А что такое своппер? — спросил любопытный Скив.
Ааз объяснил, что своппер — это структура данных, которая умеет делать следующее.
Учитывая, что обсчёт может затянуться надолго, корпорация «МИФ» попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.
Во входном файле заданы один или несколько тестов.
В первой строке каждого теста
записаны число \(N\) — длина последовательности и число \(M\) — число
операций (\(1 \le N, \, M \le 100\,000\)).
Во второй строке теста содержится \(N\) целых чисел,
не превосходящих \(10^6\) по модулю — сама последовательность.
Далее следуют \(M\) строк — запросы в формате 1 \(x_i\) \(y_i\) — запрос
первого типа, и 2 \(a_i\) \(b_i\) — запрос второго типа.
Сумма всех \(N\) и \(M\) по всему файлу не превосходит \(200\,000\).
Файл завершается строкой из двух нулей. Гарантируется, что \(x_i \le y_i\), а
\(a_i \le b_i\).
Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.
5 5 1 2 3 4 5 1 2 5 2 2 4 1 1 4 2 1 3 2 4 4 5 5 1 2 3 4 5 1 2 5 2 2 4 1 1 4 2 1 3 2 4 4 0 0
Swapper 1: 10 9 2 Swapper 2: 10 9 2
Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.
Вам нужно создать структуру данных, которая представляет из себя массив целых чисел. Изначально массив пуст. Вам нужно поддерживать две операции:
? i j» — возвращает минимальный
элемент между \(i\)-ым и \(j\)-м, включительно;
+ i x» — добавить элемент \(x\) после \(i\)-го
элемента списка. Если \(i = 0\), то элемент добавляется в начало
массива.
Конечно, эта структура должна быть достаточно хорошей.
Первая строка входного файла содержит единственное целое число \(n\) — число операций над массивом (\(1 \le n \le 200\,000\)). Следующие \(n\) строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят \(10^9\).
Для каждой операции в отдельной строке выведите её результат.
Комментарий к примеру тестов.
Нижеследующая таблица показывает процесс изменения массива из примера.
| Операция | Массив после её выполнения |
| изначально | пуст |
+ 0 5 | 5 |
+ 1 3 | 5, 3 |
+ 1 4 | 5, 4, 3 |
+ 0 2 | 2, 5, 4, 3 |
+ 4 1 | 2, 5, 4, 3, 1 |
8 + 0 5 + 1 3 + 1 4 ? 1 2 + 0 2 ? 2 4 + 4 1 ? 3 5
4 3 1
Капрал Питуца любит командовать своим отрядом. Его любимый приказ «в начало строя». Он выстраивает свой отряд в шеренгу и оглашает последовательность приказов. Каждая приказ имеет вид «Солдаты с \(l_i\) по \(r_i\) — в начало строя!»
Пронумеруем солдат в начальном положении с 1 до \(n\), слева направо. Приказ «Солдаты с \(l_i\) по \(r_i\) — в начало строя!» означает, что солдаты, стоящие с \(l_i\) по \(r_i\) включительно, перемещаются в начало строя, сохраняя относительный порядок.
Например, если в некоторый момент солдаты стоят в порядке \(2, 3, 6, 1, 5, 4\), после приказа: «Солдаты с \(2\) по \(4\) — в начало строя!» порядок будет \(3, 6, 1, 2, 5, 4\).
По данной последовательности приказов найти конечный порядок солдат в строю.
В первой строке два целых числа \(n\) and \(m\) (\(2 \le n \le 100\,000\), \(1 \le m \le 100\,000\)) — количество солдат и количество приказов. Следующие \(m\) строк содержат по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)).
Выведите \(n\) целых чисел — порядок солдат в конечном положении после выполнения всех приказов.
6 3 2 4 3 5 2 2
1 4 5 2 3 6
Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.
Мелодия состоит из \(M\) нот \(b_1, b_2, \dots, b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.
В первой строке входного файла содержатся три целых числа \(N\), \(M\), \(L\) - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены \(N\) чисел \(a_i\) (\(i = 1, 2, \dots N\)) - количество мл в \(i\)-ой бутылке. В третьей строке - \(M\) чисел \(b_i\) (\(i = 1, 2, \dots M\)) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.
Выведите единственное число - максимальное количество начальных нот мелодии, которые можно сыграть, оптимально заполнив бутылки.
Тесты состоят из четырёх групп.
6 8 179 4 9 23 15 43 7 3 10 14 7 3 8 7 3
0
5 8 5 5 3 8 14 1 10 7 3 7 12 3 3 6
4
2 2 4 6 13 8 10
1
Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить» и «найти» (по значению). Программа должна обрабатывать запросы трёх видов:
ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».
SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.
PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.
В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.
Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
template<class T> void print_tree(Node<T> *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i<level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Изначальный вызов этой функции — print_tree(root,0).)
ADD 2 ADD 3 ADD 2 SEARCH 2 ADD 5 PRINTTREE SEARCH 7
DONE DONE ALREADY YES DONE 2 .3 ..5 NO