Темы --> Информатика --> Другое
    Разбор случаев(6 задач)
    Теория вероятностей(3 задач)
    Конструктив(21 задач)
    Формула(17 задач)
    Комбинаторика(9 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап
    2009(8 задач)
    2010(8 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(8 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
    Московская областная олимпиада(13 задач)
    Кировская открытая областная олимпиада(21 задач)
    Санкт-Петербург(3 задач)
Страница: 1 Отображать по:
#112744
Выбор зала
  
Темы: [Формула]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом. Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от \(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
Выходные данные
3
#113100
Три сына
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Во владениях короля Флатландии находится прямая дорога длиной \(n\) километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

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

  • каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры \(a \times a, b \times b\) и \(c \times c\);
  • стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна \(n\);
  • участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство \(a < b < c\);
  • суммарная площадь участков \(a^2 + b^2+ c^2\) должна быть минимальна.
Требуется написать программу, которая по заданной длине дороги определяет размеры участков, которые следует выделить сыновьям короля.

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

Входной файл содержит одно целое число \(n\) (\(6 \le n \le 10^9\) ).

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

Выходной файл должен содержать три целых положительных числа, разделенных пробелами: \(a\), \(b\) и \(c\) – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

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

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

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

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

\(n \le 50\)

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

\(n \le 2000\)

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

\(n \le 40000\)

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

\(n \le 10^9\)

Примеры
Входные данные
6
Выходные данные
1 2 3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест