Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
dices.in
Ограничение памяти:
256 Мб
Выходной файл:
dices.out
Максимальный балл:
100
Условие
Юный математик Матвей интересуется теорией вероятностей, и по этой причине у него всегда есть с собой несколько
стандартных шестигранных игральных кубиков. Стандартный шестигранный кубик имеет три противолежащих пары граней, которые
размечены таким образом, что напротив грани с числом 1 находится грань с числом 6, напротив грани с числом 2 — грань с
числом 5 и напротив грани с числом 3 — грань с числом 4.
Анализируя различные игры с шестигранными кубиками, Матвей придумал новую игру. В эту игру играют два игрока, и проходит
она следующим образом: первый игрок бросает один или несколько стандартных кубиков (количество кубиков он определяет сам).
После этого первому игроку начисляется количество очков, равное сумме чисел, оказавшихся на верхних гранях всех кубиков,
а второму игроку — сумма чисел, оказавшихся на нижних гранях этих кубиков. Побеждает тот, кто набрал больше очков.
Например, если был брошен один кубик, и на верхней его грани выпало число два, то первый игрок получает два очка, а
второй — пять. В свою очередь, если было брошено два кубика и на их верхних гранях выпало по единице, то первый игрок
получает также два очка, а второй игрок — двенадцать очков, так как на нижних гранях этих кубиков оказались шестерки.
Матвей рассказал об этой игре своему другу, юному информатику Фоме, и они начали играть в неё через Интернет. Поскольку
Фома не видит результат броска и не знает, сколько кубиков бросает Матвей как первый игрок, то о набранных каждым игроком
очках он узнает только от Матвея. Чтобы проверить достоверность этой информации, Фома решил узнать, какое минимальное и
максимальное количество очков мог получить он, как второй игрок, если известно, сколько очков набрал Матвей.
Требуется написать программу, которая по количеству очков, набранных первым игроком после броска, определяет наименьшее и наибольшее количество очков, которые может получить второй игрок за этот бросок.
Система оценивания
Правильные решения для тестов, в которых 1 ≤ n ≤ 1000, будут оцениваться из 50 баллов.
Формат входного файла
Первая строка входного файла содержит одно целое положительное число n — количество очков, которые получил первый игрок.
Формат выходного файла
Выходной файл должен содержать два разделенных пробелом целых числа: минимальное и максимальное количество очков
соответственно, которые мог набрать второй игрок при таком броске кубиков.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
cities.in
Ограничение памяти:
256 Мб
Выходной файл:
cities.out
Максимальный балл:
100
Условие
Юный программист решил придумать собственную игру. Игра происходит на поле размером N×N клеток, в некоторых клетках которого расположены города
(каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города).
Всего должно быть чётное количество городов.
Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет.
Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.
Граница между государствами должна проходить по границам клеток таким образом,
чтобы из любой клетки каждого государства существовал путь по клеткам этого же государства в любую другую его клетку
(из клетки можно перейти в соседнюю, если они имеют общую сторону). Каждая клетка игрового поля должна принадлежать
только одному из двух государств, при этом государства не обязаны состоять из одинакового количества клеток.
Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.
Система оценивания
Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.
Формат входного файла
Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля.
Последующие N строк содержат по N заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля:
'C' обозначает клетку, занятую городом, 'D' — пустую клетку.
Гарантируется, что на поле есть хотя бы два города и всего их четное число.
Формат выходного файла
Выходной файл должен содержать N строк по N цифр (без пробелов) в каждой, кодирующих соответствующие клетки.
Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 — данная клетка принадлежит второму государству.
Если решений несколько, необходимо вывести любое из них.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
casting.in
Ограничение памяти:
256 Мб
Выходной файл:
casting.out
Максимальный балл:
100
Условие
В театре работает n актеров. Известно, что среди них a — высоких, b — голубоглазых и c — блондинов.
Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин.
Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать,
какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.
Требуется написать программу, которая по заданным числам n, a, b и c определяет
минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.
Пояснения к примерам
В первом примере, поскольку высоких актеров всего трое, то на главную роль не может подойти больше трех человек.
Во втором примере все актеры — блондины и все, кроме одного, — голубоглазые.
Тогда среди трех высоких актеров найдутся хотя бы два голубоглазых (и, естественно, они будут блондинами).
Следовательно, минимум два актера точно подойдут на главную роль в новом спектакле.
Система оценивания
Правильные решения для тестов, в которых требуется найти минимальное количество актеров, будут оцениваться из 50 баллов.
Правильные решения для тестов, в которых требуется найти максимальное количество актеров, будут оцениваться из 50 баллов.
Формат входного файла
Первая строка входного файла содержит одно число, которое задает, минимальное или максимальное количество актеров необходимо найти в данном тесте.
Это число может принимать следующие значения:
1, если в данном тесте требуется определить минимальное количество актеров
2, если в данном тесте требуется определить максимальное количество актеров
Вторая строка входного файла содержит разделенные пробелами четыре целых числа: nabc.
Формат выходного файла
Выходной файл должен содержать одно число — минимальное или максимальное (в зависимости от входных данных) количество актеров,
которые могут претендовать на главную роль в новом спектакле.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
pobeda.in
Ограничение памяти:
256 Мб
Выходной файл:
pobeda.out
Максимальный балл:
100
Условие
Как известно, современные видеокарты умеют формировать изображения с использованием только треугольников.
Видеокарта POBEDA-2014 не отстает от современных тенденций.
Известно, что она умеет отображать только прямоугольные равнобедренные треугольники четырех типов ориентации,
представленные на рисунках ниже. Изменять ориентацию этих треугольников видеокарта не может.
Длина катета каждого из представленных выше треугольников равна одному сантиметру.
За один такт видеокарта не может отобразить более чем ai треугольников i-того типа.
Необходимо определить максимально возможную длину стороны квадрата,
который может быть изображен видеокартой на экране монитора за один такт.
При этом квадрат должен быть расположен так, чтобы его стороны были параллельны краям монитора.
Требуется написать программу, которая решает поставленную задачу.
Пояснения к примерам
Далее приведен рисунок для первого примера.
Система оценивания
Частичные правильные решения для тестов, в которых a1, a2, a3, a4 ≤ 100000,
будут оцениваться из 50 баллов.
Формат входного файла
Первая строка входного файла содержит разделенные пробелами четыре целых числа: a1, a2, a3, a4.
Входные данные могут превышать максимальные значения для 32 битного типа данных.
Формат выходного файла
Выходной файл должен содержать одно число -– максимально возможную длину стороны квадрата.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
lights.in
Ограничение памяти:
256 Мб
Выходной файл:
lights.out
Максимальный балл:
100
Условие
По территории компьютерного лагеря проложен маршрут для поездок на электрокарах.
Поскольку на электрокаре можно добраться до ИКТ-центра, то школьник Пахом решил воспользоваться им.
Следуя по маршруту, электрокар проехал с постоянной скоростью один за другим два светофора с зеленым светом.
Пахому известно, что оба светофора находятся на расстоянии x метров друг от друга и
переключаются абсолютно синхронно: зеленый свет горит a минут,
потом включается красный свет и горит в течение b минут, после чего
светофор переключается опять на зеленый свет и он горит также в течение a минут, и так далее.
Переключений на желтый свет у светофоров нет.
Скорость движения электрокара по маршруту не превышает 1000 м/мин.
Электрокар может проехать на светофоре в тот момент, когда светофор горит зелёным светом или
переключается с одного света на другой.
Приехав в ИКТ-центр, Пахом заинтересовался, с какой максимальной постоянной скоростью
он мог ехать на электрокаре между двумя светофорами.
Требуется написать программу, которая позволит Пахому выяснить это.
Система оценивания
Правильные решения для тестов, в которых ответ является целочисленным, будут оцениваться из 50 баллов.
Несмотря на выделение отдельной группы тестов для целочисленных ответов, на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов из условия задачи.
Формат входного файла
Первая строка входного файла содержит три целых числа: a, b и x.
Формат выходного файла
Выходной файл должен содержать одно число — максимальную возможную скорость электрокара между двумя светофорами. Ответ должен отличаться от правильного не более чем на 10 − 9.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
hall.in
Ограничение памяти:
256 Мб
Выходной файл:
hall.out
Максимальный балл:
100
Условие
Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала.
Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом.
Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым,
площадь зала должна находиться в пределах от A до B квадратных метров, включительно.
Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах,
но при этом не создать ощущения, что успехов слишком мало,
периметр зала должен находиться в пределах от C до D метров, включительно.
Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера.
Залы с размерами Y × Z и Z × Y считаются одинаковыми.
Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом,
сколько различных залов удовлетворяют приведенным выше ограничениям.
Требуется написать программу, которая по заданным A, B, C и D определяет количество различных залов,
площадь которых находится в пределах от A до B, а периметр — от C до D, включительно.
Пояснения к примеру
В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2.
Система оценки и описание подзадач
Подзадача 1 (50 баллов)
1 ≤ A ≤ B ≤ 1000, 4 ≤ C ≤ D ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (50 баллов)
1 ≤ A ≤ B ≤ 109, 4 ≤ C ≤ D ≤ 109.
В этой подзадаче 25 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Формат входного файла
Входной файл содержит четыре разделенных пробелами целых числа: A, B, C и D.
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество залов.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
circle.in
Ограничение памяти:
256 Мб
Выходной файл:
circle.out
Максимальный балл:
100
Условие
В городе, в котором живут друзья Андрей и Борис, метро состоит из единственной кольцевой линии,
вдоль которой на равном расстоянии друг от друга расположены n станций,
пронумерованных от 1 до n. Участок линии метро между двумя соседними станциями
называется перегоном.
Поезда по кольцевой линии двигаются как по часовой стрелке, так и против часовой стрелки,
поэтому чтобы добраться от одной станции до другой, пассажир может выбрать то направление,
в котором требуется проехать меньше перегонов. Минимальное число перегонов,
которое необходимо проехать, чтобы добраться от одной станции до другой,
назовем расстоянием между станциями.
Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X
и выписать для нее два числа: Da — расстояние от станции, на которой живет Андрей,
до станции X и Db — расстояние от станции, на которой живет Борис, до станции X,
то полученная пара чисел [Da, Db] будет однозначно задавать станцию X.
Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2,
то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1]
и станция 4 — парой [1, 2].
Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут
Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует
вариантов пар станций A, B, таких что если Андрей живет на станции A,
а Борис — на станции B, то выполняется описанное выше условие.
Требуется написать программу, которая по числу станций n на кольцевой линии
определяет искомое количество вариантов.
Пояснения к примерам
В первом примере подходят следующие варианты:
Андрей живет на станции 1, а Борис на станции 2;
Андрей живет на станции 1, а Борис на станции 4;
Андрей живет на станции 2, а Борис на станции 1;
Андрей живет на станции 2, а Борис на станции 3;
Андрей живет на станции 3, а Борис на станции 2;
Андрей живет на станции 3, а Борис на станции 4;
Андрей живет на станции 4, а Борис на станции 1;
Андрей живет на станции 4, а Борис на станции 3.
Система оценки и описание подзадач
В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае,
если все тесты для данной подзадачи успешно пройдены.
Подзадача 1 (25 баллов)
3 ≤ n ≤ 50;
Подзадача 2 (25 баллов)
3 ≤ n ≤ 500;
Подзадача 3 (50 баллов)
3 ≤ n ≤ 40000;
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Формат входного файла
Первая строка входного файла содержит одно целое число n.
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество вариантов.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
prizes.in
Ограничение памяти:
256 Мб
Выходной файл:
prizes.out
Максимальный балл:
100
Условие
Петр участвует в конкурсе, в котором разыгрывается N призов.
Призы пронумерованы от 1 до N.
По итогам конкурса участник может набрать от 2 до N баллов.
Если участник наберет K баллов, то он получит один из призов с номером от 1 до K.
Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов с номером от 1 до K.
Затем участник может выбрать любой приз из оставшихся K − 1.
Список призов стал известен Петру. Он определил для каждого приза его ценность,
для i-го приза она задается целым числом ai.
Требуется написать программу, которая по заданным ценностям призов
определяет для каждого K от 2 до N, приз с какой максимальной ценностью
гарантированно достанется Петру, если он наберет в конкурсе K баллов.
Формат входного файла
Первая строка входного файла содержит число N.
Вторая строка этого файла содержит N целых чисел: a1, a2, …, aN.
Формат выходного файла
Выходной файл должен содержать одну строку, содержащую N − 1 целых чисел:
для каждого K от 2 до N должна быть выведена ценность приза,
который достанется Петру, если он наберет K баллов.
Ограничения
2 ≤ N ≤ 100000; 1 ≤ ai ≤ 109
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 1 (24 балла)
N ≤ 100
Подзадача 2 (24 балла)
N ≤ 5000
Подзадача 3 (52 балла)
N ≤ 100000
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
division.in
Ограничение памяти:
256 Мб
Выходной файл:
division.out
Максимальный балл:
100
Условие
Во владениях короля Флатландии находится прямая дорога длиной N километров,
по одну сторону от которой расположен огромный лесной массив.
Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник.
Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.
У короля три сына: младший, средний и старший.
Король решил, что в заповедник не войдут участки лесного массива,
которые он оставит сыновьям в наследство.
При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:
каждый участок должен иметь форму квадрата,
длина стороны которого выражается целым положительным числом.
Одна из сторон каждого квадрата должна лежать на дороге.
Пусть участки имеют размеры A × A, B × B и C × C;
стороны квадратов должны полностью покрывать дорогу: величина A + B + C должна быть равна N;
участок младшего сына должен быть строго меньше участка среднего сына,
а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына,
то есть должно выполняться неравенство A < B < C;
суммарная площадь участков A2 + B2 + C2 должна быть минимальна.
Требуется написать программу, которая по заданной длине дороги определяет размеры участков,
которые следует выделить сыновьям короля.
Формат входного файла
Входной файл содержит одно целое число N.
Формат выходного файла
Выходной файл должен содержать три целых положительных числа,
разделенных пробелами: A, B и C — длины сторон участков, которые следует выделить
младшему, среднему и старшему сыну, соответственно.
Если оптимальных решений несколько, разрешается вывести любое.
Ограничения
6 ≤ N ≤ 109
Пояснение к примеру
Описание подзадач и системы оценивания
В этой задаче четыре подзадачи.
Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.
Подзадача 1 (25 баллов)
N ≤ 50
Подзадача 2 (25 баллов)
N ≤ 2000
Подзадача 3 (25 баллов)
N ≤ 40000
Подзадача 4 (25 баллов)
N ≤ 109
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Новое здание кампуса Университета Байтбурга имеет n этажей, пронумерованных снизу вверх от 1 до n. Комнаты студентов расположены в нескольких подъездах.
В каждом подъезде на этажах, номер которых кратен числу k, расположено по x комнат, а на остальных этажах расположено по y комнат.
Комнаты внутри каждого подъезда пронумерованы последовательными натуральными числами. Номера комнат на первом этаже имеют наименьшие значения в этом подъезде, затем следуют номера комнат на втором этаже, и так далее. Комнаты в первом подъезде пронумерованы, начиная с 1, в каждом следующем подъезде нумерация комнат начинается с числа, следующего после максимального номера комнаты в предыдущем подъезде.
На рис.1 показаны номера комнат в здании с n = 7 этажами, 3 подъездами, и параметрами k = 3, x = 2, y = 3.
Подъезд 1
Подъезд 2
Подъезд 3
7 этаж
17, 18, 19
36, 37, 38
55, 56, 57
6 этаж
15, 16
34, 35
53, 54
5 этаж
12, 13, 14
31, 32, 33
50, 51, 52
4 этаж
9, 10, 11
28, 29, 30
47, 48, 49
3 этаж
7, 8
26, 27
45, 46
2 этаж
4, 5, 6
23, 24, 25
42, 43, 44
1 этаж
1, 2, 3
20, 21, 22
39, 40, 41
Рис. 1. Пример нумерации комнат в здании.
Для организации расселения студентов администрация кампуса должна по номеру комнаты оперативно определять этаж, на котором она находится.
Требуется написать программу, которая по заданным числам n, k, x и y, а также по номерам комнат, определяет для каждой комнаты, на каком этаже она находится.
Формат входного файла
Первая строка входного файла содержит натуральные числа n, k, x и y. Соседние числа разделены ровно одним пробелом.
Вторая строка входного файла содержит натуральное число q — количество номеров комнат, для которых требуется определить этаж.
Третья строка содержит q целых чисел a1, a2, ..., aq — номера комнат. Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.
Формат выходного файла
Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.
Ограничения
1 ≤ n ≤ 109, 1 ≤ x, y ≤ 109, 1 ≤ q ≤ 1000, 1 ≤ ai ≤ 1018
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
n, x, y
q, ai
1
31
1 ≤ n ≤ 10, 1 ≤ x, y ≤ 10
q = 1, 1 ≤ ai ≤ 100
2
19
1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109
q = 1, 1 ≤ ai ≤ 107
1
3
16
1 ≤ n ≤ 109, 1 ≤ x, y ≤ 109, x = y
1 ≤ q ≤ 1000, 1 ≤ ai ≤ 1018
4
34
1 ≤ n ≤ 109, 1 ≤ x, y ≤ 109
1 ≤ q ≤ 1000, 1 ≤ ai ≤ 1018
1,2,3
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Примеры тестов
№
Входной файл (building.in)
Выходной файл (building.out)
1
7 3 2 3
4
1 19 20 50
1
7
1
5
Задача K. Автоматизированное управление доставкой
≡
Группа программистов регионального сортировочного центра работает над автоматизацией управления доставкой почты.
Посылки принимаются в клиентских почтовых пунктах.
Почтовый пункт принимает посылки, вес каждой из которых составляет целое число килограммов.
Минимальный вес посылки равен 1 кг, а максимальный вес — k кг. Принятые посылки помещаются в специальный пакет.
Если после приема очередной посылки суммарный вес посылок в пакете больше или равен x кг,
то пакет доставляется в муниципальный почтовый центр, где пакет с посылками перемещается в специальный контейнер.
Если после доставки очередного пакета суммарный вес посылок в контейнере больше или равен y кг,
то контейнер перевозится в региональный сортировочный центр, откуда посылки уже доставляются получателям.
Суммарный вес посылок в контейнере при его перевозке может различаться в зависимости от массы принятых посылок.
Необходимо выяснить, каким может быть минимальный суммарный вес посылок в контейнере
при перевозке его из муниципального почтового центра в региональный сортировочный центр.
Требуется написать программу, которая по заданным значениям k — максимального веса посылки,
x — необходимого веса пакета для его отправки в муниципальный почтовый центр,
и y — необходимого веса контейнера для его отправки в региональный сортировочный центр,
определяет минимальный вес контейнера при его перевозке.
Формат входного файла
Входной файл содержит три целых положительных числа, по одному на строке.
Первая строка содержит число k. Вторая строка содержит число x.
Третья строка содержит число y.
Формат выходного файла
Требуется вывести одно целое число — минимальный возможный вес контейнера при перевозке.
Ограничения
1 ≤ k, x, y ≤ 109
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Ограничения
Необходимые подзадачи
k
x, y
1
21
k = 1
1 ≤ x, y ≤ 100
2
18
k = 2
1 ≤ x, y ≤ 100
3
21
1 ≤ k ≤ 100
1 ≤ x, y ≤ 100
1, 2
4
17
1 ≤ k ≤ 40000
1 ≤ x, y ≤ 40000
1, 2, 3
5
23
1 ≤ k ≤ 109
1 ≤ x, y ≤ 109
1, 2, 3, 4
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Пояснение к примеру
В приведенном примере принимаются посылки весом 1 и 2 кг. При накоплении посылок с суммарным весом хотя бы в 7 кг
пакет доставляется из клиентского почтового пункта в муниципальный почтовый центр.
При накоплении посылок с суммарным весом хотя бы в 20 кг контейнер перевозится из муниципального почтового центра
в региональный сортировочный центр.
Минимальный возможный вес контейнера в данном примере составляет 21 кг и достигается, например, следующим образом:
в муниципальный почтовый центр последовательно доставляется 3 пакета по 7 кг каждый.
Пакет весом 7 кг может получиться, например, после приема семи посылок по 1 кг.
В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.
Примеры округления оценок приведены в таблице.
Оценки на уроках
Среднее арифметическое
Итоговая оценка
2, 3, 5
2 + 3 + 53 = 313
3
3, 3, 4, 4
3 + 3 + 4 + 44 = 312
4
5, 5, 5, 3, 5
5 + 5 + 5 + 3 + 55 = 435
5
Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок. Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.
Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.
Формат входных данных
Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c.
Примечание
Следует обратить внимание, что входные данные в этой и других задачах не помещаются в стандартный 32-битный тип данных. Необходимо использовать 64-битный тип данных (long long в С++, int64 в Паскале, long в Java).
Формат выходных данных
Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.
Ограничения
0 ≤ a, b, c ≤ 1015
a + b + c ≥ 1
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
Информация о проверке
1
13
1 ≤ a ≤ 100, b = 0, c = 0 (Ученик получал только двойки)
полная
2
14
a = 0, 1 ≤ b ≤ 100, c = 0 (Ученик получал только тройки)
В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.
Выполняется один или несколько шагов по удалению чисел в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.
Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса.
Например, пусть n = 13, k = 2.
На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.
Таким образом, число 13 будет удалено на третьем шаге.
Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.
Формат входных данных
Первая строка входных данных содержит целое число n.
Вторая строка входных данных содержит целое число k.
Формат выходных данных
Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.
Ограничения
3 ≤ n ≤ 1018
2 ≤ k ≤ 100, k < n
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Ученые планируют провести важный эксперимент с использованием исследовательского модуля на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное. Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после начала работы исследовательского модуля.
Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот вокруг своей оси за a часов.
Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство l ≤ i ≤ j ≤ r, а величина (j − i) должна быть кратна~a.
Теперь учёным необходимо понять, сколько существует различных способов провести измерения.
Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести измерения: количество пар целых чисел i и j, таких что l ≤ i ≤ j ≤ r, и величина (j − i) кратна a.
Формат входных данных
Входные данные содержат три целых числа, по одному на строке: l, r и a.
Формат выходных данных
Выведите одно целое число: количество способов провести измерения.
Ограничения
1 ≤ l ≤ r ≤ 109, 1 ≤ a ≤ 109
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
Информация о проверке
1
30
1 ≤ l ≤ r ≤ 100, 1 ≤ a ≤ 100
полная
2
30
1 ≤ l ≤ r ≤ 105, 1 ≤ a ≤ 105
1
полная
3
40
1 ≤ l ≤ r ≤ 109, 1 ≤ a ≤ 109
1, 2
полная
Пояснения к примерам
В первом примере можно провести измерения в следующие пары часов: (1, 3), (1, 5), (2, 4), (3, 5).
Во втором примере продолжительности работы канала связи недостаточно, чтобы провести два измерения.
Марсоход, осуществляющий международную миссию на Марсе, неисправен. Для восстановления его работоспособности необходимо повысить мощность его батареи.
Мощность батареи марсохода задаётся целым положительным числом. Текущая мощность батареи равна a, для восстановления работоспособности марсохода необходимо повысить её мощность до значения b. Для изменения мощности батареи на марсоход с Земли можно передавать специальные сигналы двух типов: X и Y. Сигнал типа X увеличивает текущую мощность батареи на 1, а сигнал типа Y увеличивает текущую мощность батареи на 2.
Организаторы миссии хотели бы изменить мощность батареи до необходимой, передав минимальное количество сигналов. К сожалению, из-за особенности устройства марсохода, если мощность батареи оказывается кратна целому числу c, он окончательно выходит из строя и перестаёт реагировать на сигналы.
Требуется написать программу, которая по заданным начальной мощности батареи a, необходимой мощности батареи b и целому числу c определяет минимальное количество сигналов, которое необходимо передать на марсоход, чтобы восстановить его работоспособность.
Формат входных данных
Входные данные содержит три целых числа: a, b и c, по одному на строке.
Формат выходных данных
Требуется вывести одно целое число: минимальное количество сигналов, которые необходимо передать на марсоход.
Ограничения
1 ≤ a < b ≤ 109, 2 ≤ c ≤ 109, a не кратно c, b не кратно c
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
Информация о проверке
1
25
1 ≤ a < b ≤ 15, 2 ≤ c ≤ 15
полная
2
25
1 ≤ a < b ≤ 105, 2 ≤ c ≤ 105
1
полная
3
25
1 ≤ a < b ≤ 109, c = 2
полная
4
25
1 ≤ a < b ≤ 109, 2 ≤ c ≤ 109
1, 2, 3
полная
Пояснения к примерам
В первом примере можно действовать следующим образом: отправить на марсоход сигналы Y, X, Y. Мощность батареи меняется следующим образом: 2 ↦ 4 ↦ 5 ↦ 7.
Во втором примере можно действовать следующим образом: отправить на марсоход сигналы X, Y, X, Y. Мощность батареи меняется следующим образом: 4 ↦ 5 ↦ 7 ↦ 8 ↦ 10.
