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

#2969

Дракон

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2010, Задача C ]

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

Король Флатландии понял, что дальше так продолжаться не может, и нанял отважного Рыцаря, чтобы тот победил рептилию.

Рыцарь принял предложение Короля и начал готовиться к битве. Сам он участия в битве принимать не желал (не рыцарское это дело –– мечом махать), поэтому решил собрать войско из копейщиков. Но копейщикам надо платить, а у Рыцаря из-за кризиса осталось совсем немного сбережений. Помогите ему определить минимальное число копейщиков, необходимое для победы над Черным Драконом.

У копейщика и у дракона есть два параметра: количество очков здоровья и наносимый противнику урон.

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

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

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

Вводятся четыре натуральных числа через пробел: H_d, D_d, h_p, d_p –– количество очков здоровья дракона, урон, наносимый драконом, количество очков здоровья одного копейщика и урон, наносимый одним копейщиком. Все числа положительные и не превосходят 10⁹.

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

Выведите на экран одно целое число –– минимальное число копейщиков, необходимое для победы над драконом.

Примеры

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

500 50 10 10

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

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

500 28 10 10

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

#3398

Велогонка

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

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

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на $x_1$, $x_2$, ..., $x_n$ метров ($n$ – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью $v_1$, $v_2$, ..., $v_n$ метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов $n$, заданным начальным положениям велосипедистов $x_1$, $x_2$, ..., $x_n$ и их скоростям $v_1$, $v_2$, ..., $v_n$, вычислит момент времени $t$, в который расстояние $l$ между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число $n$ – количество велосипедистов.

В последующих n строках указаны по два целых числа: $x_i$ – расстояние от старта до $i$-го велосипедиста в начальный момент времени ($0 \leq x_i \leq 10^7$) и $v_i$ – его скорость ($0 \leq v_i \leq 10^7$).

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

В выходной файл необходимо вывести два вещественных числа: $t$ – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, $l$ – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более $10^{–6}$, что означает следующее. Пусть выведенное число равно $x$, а в правильном ответе оно равно $y$. Ответ будет считаться правильным, если значение выражения $|x – y| / max(1, |y|)$ не превышает $10^{–6}$.

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

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

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

$2 \leq n \leq 50$, $0 \leq x_i \leq 1000$, $0 \leq v_i \leq 1000$. Гарантируется, что существует ответ, в котором $t$ – целое число, не превышающее 1000.

Подзадача 2 (20 баллов)

$2 \leq n \leq 200$.

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

$2 \leq n \leq 2000$

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

$2 \leq n \leq 10^5$

Примеры

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

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

1 30

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

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

0.5 5.000000000000

#3870

Космический кегельбан

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

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

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. В последнем n-м ряду стоит n кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке (0, 0). Центры кеглей во втором ряду находятся в точках (–1, 1) и (1, 1). Таким образом, центры кеглей в i-м ряду находятся в точках с координатами (–(i – 1), i – 1), (–( i – 3), i – 1), …, (i – 1, i – 1).

Игра происходит следующим образом. Используется шар с радиусом q метров. Игрок выбирает начальное положение центра шара (x_c, y_c) и вектор направления движения шара (v_x, v_y). После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора (v_x, v_y). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.

На рисунке приведен пример расположения кеглей для r = 500, n = 4 и шара для q = 1000, x_c = –2, y_c = –2, v_x = 1, v_y = 1.

Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению ( x_c, y_c) и вектору направления движения (v_x, v_y) определяет количество кеглей, сбитых шаром.

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

Первая строка входного файла содержит два целых числа: r и n, разделенных ровно одним пробелом (1 ≤ r ≤ 700, 1 ≤ n ≤ 200 000).

Вторая строка входного файла содержит целое число q (1 ≤ q ≤ 10⁹).

Третья строка входного файла содержит два целых числа x_c и y_c, разделенных ровно одним пробелом (–10⁶≤ x_c ≤ 10⁶, –10 ⁶≤ y_c, 1000 ×y_c < –(r + q) ).

Четвертая строка входного файла содержит два целых числа v_x и v_y, разделенных ровно одним пробелом (–10⁶≤ v_x ≤ 10⁶, 0 < v_y ≤ 10⁶).

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

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

Примечание

Рисунок ниже показывает, какие кегли будут сбиты (такие кегли обозначены «х»).

Система оценки

Потестовая.

Примеры

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

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

#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

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

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

Выбрано

Отменить

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