Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск по ответу
---> 56 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
#112749
Вырубка леса
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут \(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\) ≤ 1018, 1 ≤ \(X\) ≤ 1018).

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

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

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

В приведенном примере лесорубы вырубают 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\) ≤ 1018
\(X\) < \(K\)
\(X\) < \(M\)
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (10 баллов)
1 ≤ \(X\) ≤ 1018
Дополнительно к приведенным ограничениям выполняется условие \(K\) = \(M\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 4 (48 баллов)
1 ≤ \(X\) ≤ 1018, 1 ≤ \(A\), \(B\) ≤ \(10^9\), 2 ≤ \(K\), \(M\) ≤ 1018
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Примеры
Входные данные
2 4 3 3 25
Выходные данные
7
#113097
Космическое поселение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из \(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
Выходные данные
2
Входные данные
1 5 5 6 6
Выходные данные
0
#113169
Дождик
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В НИИ метеорологии решили изучить процесс образования водоемов на различных рельефах местности во время дождя. Ввиду сложности реальной задачи была создана двумерная модель, в которой местность имеет только два измерения — высоту и длину. В этой модели рельеф местности можно представить как N-звенную ломаную c вершинами \((x_0, y_0), ..., (x_N, y_N)\), где \(x_0 < x_1 < ... < x_N\) и \(y_i \neq y_j\), для любых \(i \neq j\). Слева в точке \(x_0\) и справа в точке \(x_N\) рельеф ограничен вертикальными горами огромной высоты.

Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины H. Но поскольку рельеф — это ломаная, то вода стекает и скапливается в углублениях, образуя водоемы.

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

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

В первой строке расположены натуральное число \(N (1 \le N \le 100)\) и \(H\) — действительное число, заданное с тремя цифрами после десятичной точки \((0 \le H \le 10^9)\). В последующих \(N + 1\) строках — по два целых числа \(x_i, y_i: -10000 \le x_i, y_i \le 10000 (0 \le i \le N)\).

Числа в строках разделены пробелами.

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

Ответ должен содержать единственное число — искомую глубину с точностью до 4-х знаков после десятичной точки.

Пояснение к примеру:
Примеры
Входные данные
7 7.000
-5 10
-3 4
-1 6
1 -4
4 17
5 3
9 5
12 15
Выходные данные
15.8446
#113557
Держава
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Держава ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В далекой стране есть N городов. Был избран новый премьер-министр. В настоящее время в этой стране нет ни одной дороги, поэтому премьер-министр решил модернизировать страну, соединив некоторые города с двусторонними автострадами в транспортные сети. Два города будут расположены в одной и той же сети, если можно добраться до одного города от другого, используя недавно построенные дороги. Каждый город будет расположен в какой-то сети. Каждая сеть состоит из одного или нескольких городов.

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

В настоящее время страна переживает экономический спад, поэтому премьер-министр решил, что из-за отсутствия бюджета они не будут строить дороги длиннее, чем D километров. Кроме того, премьер-министр радуется мелочам, поэтому он будет счастлив, если по крайней мере в одной сети будет существовать непустое подмножество городов (оно может включать все города в сети), где общая сумма жителей делится на К . Например, если K = 4 и есть сеть с городами, в которых есть 3 , 5 , 7 жителей соответственно, премьер-министр будет счастлив, потому что сумма жителей в первых двух городах равна 8 .

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

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

Первая строка ввода содержит целые числа N и K (1 ≤ N ≤ 50000, 1 ≤ K ≤ 30) . Каждая из следующих N строк содержит три целых числа x i ; y i ; k i (0 ≤ x i , y i , k i ≤ 100000000) , которые представляют координату x города, координату y и количество жителей в этом городе, соответственно. На входных данных не будет двух городов с одинаковыми координатами. Кроме того, не будет ни одного города, в котором число жителей делится на К .

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

Первая и единственная строка вывода должна содержать минимальную D с точностью до 3 -х знаков после запятой, такую, что можно строить дороги с условием, что премьер-министр будет счастлив. Входные данные будут такими, чтобы всегда было решение.

Примечание

Объяснение первого примера: единственный способ удержать премьер-министра в счастливом настроение - все города должны находятся в одном округе. Минимальный D , для которого это возможно, равен 1.414 .

Объяснение второго примера: премьер-министр будет рад, если первые 5 городов находятся в одном округе. Если D = 5.657 , премьер-министр может соединить города 1, 2, 3, 5 с городом 4 . В этом случае сумма жителей в городах 1, 2, 3, 4, 5 составит 11 , что делится на 11 , Поэтому премьер-министр будет счастлив.

Примеры
Входные данные
3 3
0 4 4
1 5 1
2 6 1
Выходные данные
1.414
Входные данные
6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10
Выходные данные
5.657
Входные данные
6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3
Выходные данные
2.000
#113574
Чубакка и дерево
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Чубакка и дерево ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.

Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .

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

Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y ≤ N , x ≠ y ) - запросы, описанные в условии.

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

Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.

Примечание

Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.

Примеры
Входные данные
7 2 3
1 2
2 1
4 7
Выходные данные
1
1
4
Входные данные
9 3 3
8 9
5 7
8 4
Выходные данные
2
2
3
Страница: << 6 7 8 9 10 11 12 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест