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

#112744

Выбор зала

Темы: [Формула]

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

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом. Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от \(A\) до \(B\) квадратных метров, включительно.

Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от \(C\) до \(D\) метров, включительно. Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами \(Y\) × \(Z\) и \(Z\) × \(Y\) считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным \(A\), \(B\), \(C\) и \(D\) определяет количество различных залов, площадь которых находится в пределах от \(A\) до \(B\), а периметр — от \(C\) до \(D\), включительно.

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

Входной файл содержит четыре разделенных пробелами целых числа: \(A\), \(B\), \(C\) и \(D\) (1 ≤ \(A\) ≤ \(B\) ≤ \(10^9\) , 4 ≤ \(C\) ≤ \(D\) ≤ \(10^9\) )

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

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

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

В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

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

Подзадача 1 (50 баллов)
1 ≤ \(A\) ≤ \(B\) ≤ 1000, 4 ≤ \(C\) ≤ \(D\) ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (50 баллов)
1 ≤ \(A\) ≤ \(B\) ≤ \(10^9\),
4 ≤ \(C\) ≤ \(D\) ≤ \(10^9\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Примеры

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

2 10 4 8

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

#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 Отображать по:

Выбрано

Отменить

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