Страница: << 1 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 баллов.

Примеры

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

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

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

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

#112749

Вырубка леса

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

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

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут $X$ деревьев.

Дмитрий срубает по A деревьев в день, но каждый $K$-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в $K$-й, 2$K$-й, 3$K$-й день, и т.д.

Федор срубает по B деревьев в день, но каждый $M$-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в $M$-й, 2$M$-й, 3$M$-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают $A$ + $B$ деревьев, в дни, когда отдыхает только Федор — $A$ деревьев, а в дни, когда отдыхает только Дмитрий — $B$ деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам $A$, $K$, $B$, $M$ и $X$ определяет, за сколько дней все деревья в лесу будут вырублены.

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

Входной файл содержит пять целых чисел, разделенных пробелами: $A$, $K$, $B$, $M$ и $X$ (1 ≤ $A$, $B$ ≤ $10^9$ , 2 ≤ $K$, $M$ ≤ 10¹⁸, 1 ≤ $X$ ≤ 10¹⁸).

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

Выходной файл должен содержать одно целое число — искомое количество дней.

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

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:
* 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
* 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
* 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
* 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
* 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
* 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
* 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.
Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3

Система оценки и описание подзадач

Подзадача 1 (32 балла)
1 ≤ $X$ ≤ 1000, 1 ≤ $A$, $B$ ≤ 1000, 2 ≤ $K$, $M$ ≤ 1000
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (10 баллов)
1 ≤ $X$ ≤ 10¹⁸
$X$ < $K$
$X$ < $M$
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (10 баллов)
1 ≤ $X$ ≤ 10¹⁸
Дополнительно к приведенным ограничениям выполняется условие $K$ = $M$.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 4 (48 баллов)
1 ≤ $X$ ≤ 10¹⁸, 1 ≤ $A$, $B$ ≤ $10^9$, 2 ≤ $K$, $M$ ≤ 10¹⁸
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Примеры

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

2 4 3 3 25

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

#113097

Космическое поселение

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

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

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из $n$ одинаковых модулей, каждый из которых представляет собой прямоугольник.

Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером $a \times b$ метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна $d$ метрам, будет иметь форму прямоугольника размером $(a + 2d) \times (b + 2d)$ метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером $w \times h$ метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

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

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

Строка содержит пять разделенных пробелами целых чисел: $n$, $a$, $b$, $w$ и $h$ ($1 \le n, a, b, w, h \le 10^{18}$). Гарантируется, что без дополнительной защиты все модули можно разместить в поселении описанным образом.

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

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

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

В первом примере можно установить дополнительную защиту толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет размер $5 \times 5$ метров, а поле – размер $6 \times 6$ метров. Добавить дополнительную защиту к модулю нельзя.

Описание подзадач и системы оценивания

Подзадача 1 (26 баллов)

$1 \le n \le 1000, 1 \le a, b, w, h \le 1000$.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены

Подзадача 2 (23 балла)

$1 \le n \le 1000, 1 \le a, b, w, h \le 10^9$.

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

Подзадача 3 (до 24 баллов)

$1 \le n \le 10^9 , 1 \le a, b, w, h \le 10^{18}$.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (до 27 баллов)

$1 \le n \le 10^{18} , 1 \le a, b, w, h \le 10^{18}$.

В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Примеры

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

11 2 3 21 25

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

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

1 5 5 6 6

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

Страница: << 1 2 Отображать по:

Выбрано

Отменить

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