Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | building.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | building.out | |||
Максимальный балл: | 100 |
Новое здание кампуса Университета Байтбурга имеет 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 |
Для организации расселения студентов администрация кампуса должна по номеру комнаты оперативно определять этаж, на котором она находится.
Требуется написать программу, которая по заданным числам 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 |
|
|
Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | calc.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | calc.out | |||
Максимальный балл: | 100 |
В качестве домашнего задания по информатике ученикам предложено разработать специальный калькулятор, который устроен следующим образом.
Сначала пользователь вводит целое положительное число n, которое выводится на экран. Затем пользователь может нажимать на три кнопки: A, B и C.
При нажатии на кнопку A число, которое выведено на экран, делится на 2. Если число на экране нечетное, то остаток отбрасывается. Например, результат этой операции для числа 80 равен 40, а для числа 239 равен 119.
При нажатии на кнопку B к числу, которое выведено на экран, прибавляется 1, и результат делится на 2. Остаток от деления отбрасывается. Например, результат операции для числа 80 равен 40, а для числа 239 равен 120.
При нажатии на кнопку C происходит следующее. Если число, которое выведено на экран, положительное, то из него вычитается 1 и результат делится на 2, остаток отбрасывается. Если же перед нажатием на кнопку C на экран было выведено число 0, то оно остается неизменным. Например, результат операции для числа 80 равен 39, а для числа 239 равен 119.
Пользователь ввел число n и собирается нажать на кнопки операций в некотором порядке. В частности, он планирует нажать на кнопку A суммарно a раз, на кнопку B — b раз и на кнопку C — c раз. Его заинтересовал вопрос, какое минимальное число может получиться в результате выполнения описанных операций.
Требуется написать программу, которая по введенному числу n и числам a, b и c, показывающим количество произведенных на калькуляторе операций разного типа, определяет минимальное число, которое может получиться в результате работы калькулятора.
Входной файл содержит четыре целых числа: n, a, b и c. Числа заданы на одной строке, соседние числа разделены одним пробелом.
Требуется вывести одно число — минимальное число, которое может получиться у пользователя в результате работы калькулятора.
1 ≤ n ≤ 1018, 0 ≤ a, b, c ≤ 60
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | |
---|---|---|---|---|
n | Дополнительные ограничения на a, b, c | |||
1 | 26 | 1 ≤ n ≤ 109 | 0 ≤ (a + b + c) ≤ 7 | |
2 | 23 | 1 ≤ n ≤ 1018 | c = 0 | |
3 | 24 | 1 ≤ n ≤ 1018 | b = 0 | |
4 | 27 | 1 ≤ n ≤ 1018 | 1, 2, 3 |
По запросу сообщается результат окончательной проверки на каждом тесте.
В примере пользователю необходимо оптимально действовать следующим образом: нажать на кнопку B и получить число 36, затем нажать на кнопку A и получить число 18, затем нажать на кнопку C и получить число 8, затем второй раз нажать на кнопку A и получить число 4.
№ | Входной файл (calc.in ) |
Выходной файл (calc.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | delivery.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | delivery.out | |||
Максимальный балл: | 100 |
Группа программистов регионального сортировочного центра работает над автоматизацией управления доставкой почты.
Посылки принимаются в клиентских почтовых пунктах. Почтовый пункт принимает посылки, вес каждой из которых составляет целое число килограммов. Минимальный вес посылки равен 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 кг.
№ | Входной файл (delivery.in ) |
Выходной файл (delivery.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 3 сек | |
Входной файл: | linear.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | linear.out | |||
Максимальный балл: | 100 |
Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.
В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e−, либо положительно заряженную частицу — позитрон e+. В эксперименте i-я частица исходно размещается в точке с координатой xi. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e− частицы перемещаются по направлению уменьшения координаты, а e+ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.
Если в процессе перемещения частицы e− и e+ оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.
Ученые выбрали m различных моментов времени t1, t2, ..., tm, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени tj, не должны учитываться при подсчете количества частиц для этого момента времени.
Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.
Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (x1 < x2 < x3 < ... < xn). Частица e− описывается значением vi = −1, а частица e+ описывается значением vi = 1.
Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t1,t2,...,tm.
Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.
1 ≤ n, m ≤ 200000
−109 ≤ xi, m ≤ 109
0 ≤ ti ≤ 109
vi равно −1 или 1
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | |||
---|---|---|---|---|---|---|
n | xi | m | ti | |||
1 | 35 | 1 ≤ n ≤ 100 | −100 ≤ xi ≤ 100 | m = 1 | 0 ≤ ti ≤ 100 | |
2 | 12 | 1 ≤ n ≤ 100 | −109 ≤ xi ≤ 109 | m = 1 | 0 ≤ ti ≤ 109 | 1 |
3 | 12 | 1 ≤ n ≤ 200 000 | −109 ≤ xi ≤ 109 | m = 1 | 0 ≤ ti ≤ 109 | 1, 2 |
4 | 41 | 1 ≤ n ≤ 200 000 | −109 ≤ xi ≤ 109 | 1 ≤ m ≤ 200 000 | 0 ≤ ti ≤ 109 | 1, 2, 3 |
По запросу сообщается результат окончательной проверки на каждом тесте.
В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e+ в точке −1, частица e− в точке 0, частица e+ в точке 1 и частица e− в точке 5.
В момент времени 0.5 первая частица e+ и первая частица e− сталкиваются в точке с координатой −0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.
№ | Входной файл (linear.in ) |
Выходной файл (linear.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 1 сек | |
Входной файл: | division.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | division.out | |||
Максимальный балл: | 100 |
Во владениях короля Флатландии находится прямая дорога длиной N километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.
У короля три сына: младший, средний и старший. Король решил, что в заповедник не войдут участки лесного массива, которые он оставит сыновьям в наследство. При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:
Требуется написать программу, которая по заданной длине дороги определяет размеры участков, которые следует выделить сыновьям короля.
Входной файл содержит одно целое число N.
Выходной файл должен содержать три целых положительных числа, разделенных пробелами: A, B и C — длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.
6 ≤ N ≤ 109
В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.
N ≤ 50
N ≤ 2000
N ≤ 40 000
N ≤ 109
По запросу сообщается результат окончательной проверки на каждом тесте.
№ | Входной файл (division.in ) |
Выходной файл (division.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 1 сек | |
Входной файл: | game.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | game.out | |||
Максимальный балл: | 100 |
Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал A баллов, второй — B, а третий C, то говорят, что игра закончилась со счетом A:B:C.
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в K раз.
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из N карточек, на которых написаны числа x1, x2, …, xN. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу K и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.
Первая строка входного файла содержит два целых числа: N и K. Вторая строка входного файла содержит N целых чисел x1, x2, …, xN.
Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.
3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109
В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в k = 2 раза.
В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.
Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только каких-либо из подзадач 1 и 3.
3 ≤ N ≤ 100 000; K = 1; 1 ≤ xi ≤ 100 000
3 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ xi ≤ 100
3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109; все xi различны
3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109
По запросу сообщается результат окончательной проверки на каждом тесте.
№ | Входной файл (game.in ) |
Выходной файл (game.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты успешно пройдены.
N ≤ 100
N ≤ 5000
N ≤ 100 000
По запросу сообщается результат окончательной проверки на каждом тесте.
№ | Входной файл (prizes.in ) |
Выходной файл (prizes.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 1 сек | |
Входной файл: | space.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | space.out | |||
Максимальный балл: | 100 |
Для освоения Марса требуется построить исследовательскую базу. База должна состоять из N одинаковых модулей.
Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером A × B метров.
Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля дополнительный защитный слой. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину защитного слоя.
Модуль с защитным слоем, толщина которой равна D метрам, будет иметь в основании форму прямоугольника размером (A + 2 D) × (B + 2 D) метров.
Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером W × H метров.
При этом они должны быть организованы в виде регулярной сетки, их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.
Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину дополнительного защитного слоя, который можно добавить к каждому модулю.
В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.
Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле — размер 6 × 6 метров.
Добавить дополнительный защитный слой к модулю нельзя.
Входной файл содержит пять разделенных пробелами целых чисел: N, A, B, W, H.
Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.
Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя.
Если дополнительный защитный слой установить не удастся, требуется вывести число 0.
1 ≤ N, A, B, W, H ≤ 1018
1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 109.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
1 ≤ N ≤ 109; 1 ≤ A, B, W, H ≤ 1018.
В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
1 ≤ N ≤ 1018; 1 ≤ A, B, W, H ≤ 1018.
В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
№ | Входной файл (space.in ) |
Выходной файл (space.out ) |
---|---|---|
1 |
|
|
2 |
|
|