Страница: << 3 4 5 6 7 8 9 >> Отображать по:

#111225

Мозаика

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача E ]

Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.

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

В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа A_i и B_i , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ A_i, B_i ≤ 10⁹, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N₁ и N₂ – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ $N_1$ < $N_2$ ≤ N).

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

Выходной файл должен содержать K строк, каждая из которых содержит два разделённых пробелом числа – номера элементов мозаики, образующих негармоничную пару в соответствующем наборе. Если решений несколько, можно вывести любое из них. Если в наборе негармоничная пара отсутствует, требуется вывести в соответствующей строке 0 0.

Примечание

Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.

(оценивается в 20 баллов) Количество элементов мозаики N ≤ 100, число наборов K ≤ 100.
(оценивается в 30 баллов) Количество элементов мозаики N ≤ 1000, число наборов K ≤ 1000.
(оценивается в 20 баллов) Количество элементов мозаики N ≤ 5000, число наборов K ≤ 5000.
(оценивается в 30 баллов) Количество элементов мозаики N ≤ 100 000, число наборов K ≤ 100 000.

Примеры

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

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

0 0
4 2

#111491

Березовая аллея

Темы: [Бинарный поиск по ответу] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача D ]

На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной $W$ метров. Вдоль левой стороны аллеи растет $N$ берез, а вдоль правой — $M$ берез, при этом $i$-я береза с левой стороны аллеи находится на расстоянии $a_i$ метров от начала аллеи, а $j$-я береза с правой стороны — на расстоянии $b_j$ метров от начала аллеи.

$\text{[math]}$

Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы. Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой (зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию. К сожалению, в его распоряжении оказалась только лента длиной $L$ метров, которую, к тому же, нельзя было разрезать. Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез. При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.

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

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

Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты $L$ и ширину аллеи $W$ ($1 \leq L \leq 2 \times 10^5$, $1 \leq W \leq 10^4$).

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число $N$ — количество берез ($1 \leq N \leq 2000$), а третья строка содержит $N$ различных целых чисел $a_1$, $a_2$, …, $a_N$ ($0 \leq a_i \leq 10^5$), заданных по возрастанию.

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число $M$ — количество берез ($1 \leq M \leq 2000$), а пятая строка содержит $M$ различных целых чисел $b_1$, $b_2$, …, $b_M$ ($0 \leq b_i ≤ 10^5$), заданных по возрастанию.

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

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

Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + $10^{-5}$).

Система оценивания

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 50, будут оцениваться из 30 баллов.

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 500, будут оцениваться из 60 баллов.

Примеры

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

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

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

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

#111636

Древние династии

Темы: [Динамическое программирование] [Дерево отрезков, RSQ, RMQ] [Очередь]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2013, 1 день, Задача D ]

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KL_i лет, но не более KR_i лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее ML_i лет, но не более MR_i лет.

Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X₁, X₂, ..., X_N (1 ≤ X₁ ≤ X₂ ≤ ... ≤ X_N ≤ 10⁹) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KL_i, KR_i, ML_i, MR_i (1 ≤ KL_i ≤ KR_i ≤ 10⁹), (1 ≤ ML_i ≤ MR_i ≤ 10⁹).

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

Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.

Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

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

Примечание

Данная задача содержит шесть подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Тесты из условия. Подзадача оценивается в 0 баллов.
2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры

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

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

1 1
211

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

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

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

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

2 0
21212

#111878

Взвешивание камней

Темы: [Алгоритмы сортировки] [Жадный алгоритм] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Жаутыковские олимпиады, 2011, Задача D ]

Джек нашел $N$ камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий 2 и так далее, самый тяжелый получил номер $N$.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

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

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

Первая строка содержит целое число $N$ (1 $\le$ $N$ $\le$ 100000).

Каждая из следующих $N$ строк содержит по два целых числа: $R$ (1 $\le$ $R$ $\le$ $N$) и $S$ (1 $\le$ $S$ $\le$ 2). $R$ номер камня, который будет положен на чашу $S$. Все $R$ будут различны.

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

Выведите $N$ строк по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

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

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

<
>
>
?
>

#111881

Коллайдер

Темы: [Декартово дерево] [Задачи на моделирование]

Источники: [ Личные олимпиады, Жаутыковские олимпиады, 2011, Задача G ]

Физики проводят эксперимент для исследования частиц трёх типов: $x$, $y$ и $z$. Они запускают в коллайдер пронумерованный ряд из $n$ частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с $i$-ого места ряда и моментально появляется на месте $j$. После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте $k$. Напишите программу, которая поможет физикам.

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

В первой строке файла два целых числа: $n$ – количество частиц и m — общее количество воздействий и вопросов (1 $\le$ $n$ $\le$ 1000000, 1 $\le$ $m$ $\le$ 15000). Во второй строке — последовательность из символов $x$, $y$ и $z$ длиной $n$. На каждой из следующих $m$ строк (1 $\le$ $ m$ $\le$ 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом $a$ и после пробела дается два целых числа из интервала [1; $n$]. Первое из них показывает начальное, а второе конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом $q$ и после пробела дается одно целое число из интервала [1; $n$]. Оно указывает позицию, которая интересует физиков.

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

Выведите столько строк, сколько вопросов во входном файле. В строке номер $i$ надо записать ответ на вопрос $i$ — название соответствующей частицы $x$, $y$ или $z$.

Пояснения к примеру

Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,

Примеры

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

15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q 2

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

y
z
y

Страница: << 3 4 5 6 7 8 9 >> Отображать по:

Выбрано

Отменить

Добавить в контест