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

#3386

Йою Ньерк

Темы: [Обход в глубину] [Бинарный поиск по ответу] [Обход в ширину] [Способы задания графа]

#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⁶).

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

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

Примечание

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

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

Потестовая.

Примеры

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

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

#111402

Веревочки

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

С утра шел дождь, и ничего не предвещало беды. Но к обеду выглянуло солнце, и в лагерь заглянула СЭС. Пройдя по всем домикам и корпусам, СЭС вынесла следующий вердикт: бельевые веревки в жилых домиках не удовлетворяют нормам СЭС. Как выяснилось, в каждом домике должно быть ровно по одной бельевой веревке, и все веревки должны иметь одинаковую длину. В лагере имеется $N$ бельевых веревок и $K$ домиков. Чтобы лагерь не закрыли, требуется так нарезать данные веревки, чтобы среди получившихся веревочек было $K$ одинаковой длины. Размер штрафа обратно пропорционален длине бельевых веревок, которые будут развешены в домиках. Поэтому начальство лагеря стремиться максимизировать длину этих веревочек.

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

В первой строке заданы два числа — $N$ ($1 \le N \le 10001$) и $K$ ($1 \le K \le 10001$). Далее в каждой из последующих $N$ строк записано по одному числу — длине очередной бельевой веревки. Длина веревки задана в сантиметрах. Все длины лежат в интервале от $1$ сантиметра до $100$ километров включительно.

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

В выходной файл следует вывести одно целое число — максимальную длину веревочек, удовлетворяющую условию, в сантиметрах. В случае, если лагерь закроют, выведите $0$.

Примеры

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

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

#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 баллов.

Примеры

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

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

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

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

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

Выбрано

Отменить

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