Темы --> Информатика --> Другое
    Разбор случаев(6 задач)
    Теория вероятностей(3 задач)
    Конструктив(21 задач)
    Формула(17 задач)
    Комбинаторика(9 задач)
---> 4 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: 1 Отображать по:
#601
Забор
  
Темы: [Формула]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить \(k\) досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

Изначально Том находится у цистерны. Соседние доски находятся на расстоянии 1 фута друг от друга, цистерна находится на расстоянии 1 фута от первой доски. По окончании работы Том должен положить кисточку и ведерко на свою исходную позицию рядом с цистерной.

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

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

Первая строка входного файла содержит количество досок в заборе \(n\) (1 ≤ \(n\) ≤ \(10^9\)) и вместимость ведерка \(k\) (1 ≤ \(k\) ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора \(m\) (1 ≤ \(m\) ≤ 50). Далее следуют \(m\) строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей \(l_i\) и правой границей \(r_i\) (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\)). Такое описание означает, что не покрашены \(l_i\)-я, (\(l_i\)+1)-я, …, (\(r_i\)–1)-я, \(r_i\)-я доски забора (доски нумеруются от 1 до \(n\)). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

Выведите одно число — минимальное расстояние в футах, которое необходимо пройти Тому для выполнения своего ответственного задания.

Примеры
Входные данные
5 2
2
1 2
5 5
Выходные данные
12
#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
#112831
Строки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.

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

Программа получает на вход три строки, состоящие из строчных букв латинского алфавита. Длина каждой строки не превышает 100 символов.

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

Если при помощи указанных операций возможно сделать все три строки равными, выведите такую строку S , что суммарное число операций, необходимых для преобразования всех трёх данных строк к строке S , будет минимальным. Если этого сделать нельзя, программа должна вывести одно слово IMPOSSIBLE (заглавными буквами).

Примечание

Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является слово IMPOSSIBLE, будет оцениваться в 0 баллов.

Примеры
Входные данные
aaaza
aazzaa
azzza
Выходные данные
aazza
Входные данные
xy
xxyy
yx
Выходные данные
IMPOSSIBLE
#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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест