Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 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 сек | |
Входной файл: | data.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | data.out | |||
Максимальный балл: | 101 |
Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.
Множество серверов A называется отказоустойчивым, если при недоступности любого канала связи выполнено следующее условие. Для любого не входящего в это множество сервера X существует способ передать данные по остальным каналам на сервер X хотя бы от одного сервера из множества A.
На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.
Рис. 1. Пример сети и отказоустойчивого множества серверов.
В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число 109 + 7.
Требуется написать программу, которая по заданному описанию сети определяет следующие числа: k — минимальное количество серверов в отказоустойчивом множестве серверов, c — остаток от деления количества способов выбора отказоустойчивого множества из k серверов на число 109 + 7
Первая строка входного файла содержит целые числа n и m — количество серверов и количество каналов связи соответственно.
Следующие m строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.
Гарантируется, что любые два сервера соединены напрямую не более чем одним каналом связи, никакой канал не соединяет сервер сам с собой, и для любой пары серверов существует способ передачи данных с одного из них на другой, возможно с использованием одного или нескольких промежуточных серверов.
Выведите два целых числа, разделенных пробелом: k — минимальное число серверов в отказоустойчивом множестве серверов, c — количество способов выбора отказоустойчивого множества из k серверов, взятое по модулю 109 + 7
2 ≤ n ≤ 200000, 1 ≤ m ≤ 200000
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | |
---|---|---|---|---|
n | m | |||
1 | 25 | 2 ≤ n ≤ 10 | 1 ≤ m ≤ 45 | |
2 | 27 | 2 ≤ n ≤ 200000 | m = n − 1 | |
3 | 28 | 2 ≤ n ≤ 1000 | 1 ≤ m ≤ 5000 | 1 |
4 | 21 | 2 ≤ n ≤ 200000 | 1 ≤ m ≤ 200000 | 1, 2, 3 |
По запросу сообщается результат окончательной проверки на каждом тесте.
В приведённом примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.
№ | Входной файл (data.in ) |
Выходной файл (data.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | mining.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | mining.out | |||
Максимальный балл: | 100 |
Ведется проект по освоению планеты соседней звездной системы. Для добычи полезных ископаемых планируется направить на планету несколько партий роботов.
Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером w на h, клетки участка имеют координаты от (1, 1) до (w, h). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено s баз, и i-я база находится в клетке с координатами (xi, yi).
Каждая партия роботов характеризуется тремя параметрами: j-я партия доставляется на базу bj, содержит nj роботов и каждый робот партии обладает мобильностью mj.
Когда партия роботов доставляется на соответствующую базу, каждый робот этой партии перемещается по поверхности планеты от базы до некоторой клетки. Если мобильность робота равна m, он может не более m раз переместиться на одну из восьми соседних клеток, как показано на рис. 1.
Рис. 1. Возможные перемещения робота в восьми направлениях.
После того как роботы из всех доставленных партий размещаются на участке, они активируются и начинают добычу полезных ископаемых. В процессе перемещения в одной клетке может одновременно находиться произвольное количество роботов. Однако после активации в каждой клетке должно находиться не более q роботов.
Руководством проекта получена информация о t партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше q роботов. Поэтому руководство должно выбрать k первых партий роботов, где 0 ≤ k ≤ t, которые будут полностью доставлены на соответствующие базы. После этого, если k < t, следует дополнительно принять z из nk + 1 роботов следующей, (k + 1)-й партии, 0 ≤ z < nk + 1.
Все полученные таким образом роботы должны с учетом ограничения на мобильность разместиться на участке таким образом, чтобы в каждой клетке было не более q роботов. После этого они будут активированы и начнут добычу полезных ископаемых. Разумеется, руководство проекта старается максимизировать количество роботов, которые будут доставлены на планету, поэтому, с учетом описанных ограничений, требуется максимизировать k, а затем максимизировать z.
Требуется написать программу, которая по размерам участка, числу q, описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число k — количество партий роботов, и затем – максимальное число z – дополнительное количество роботов из (k + 1)-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более q роботов.
Первая строка входного файла содержит числа w, h, s и q. Последующие s строк содержат по два целых числа xi, yi и описывают базы специалистов (1 ≤ xi ≤ w, 1 ≤ yi ≤ h).
Следующая строка содержит число t — количество партий роботов. Последующие t строк описывают партии роботов и содержат по 3 целых числа: bj, nj и mj (1 ≤ bj ≤ s, 1 ≤ nj ≤ w × h × q, 0 ≤ mj < max(w, h)).
Требуется вывести два числа: k и z, 0 ≤ k ≤ t. Если k = t, то z должно быть равно 0, иначе должно выполняться условие 0 ≤ z < nk + 1.
1 ≤ w, h ≤ 105, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,
В приведенном примере описания входных данных следует полностью принять первую партию роботов и дополнительно принять 7 роботов из второй партии. На рис. 2 показано, как можно разместить этих роботов на участке, чтобы в каждой клетке было не более одного робота. Базы специалистов показаны кружками. Клетки, в которых окажутся роботы с базы 1, показаны вертикальной штриховкой, а клетки, в которых окажутся роботы с базы 2, показаны серым цветом.
Рис. 2. Возможное размещение роботов на участке в данном примере.
Баллы за каждую из подзадач 1–5 начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Тесты для подзадачи 6 запускаются только в случае, если все тесты подзадач 1–5 успешно пройдены. Каждый тест в подзадаче 6 оценивается независимо в 1 балл.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | ||
---|---|---|---|---|---|
w, h | s | q | |||
1 | 18 | 1 ≤ w, h ≤ 20 | s = 1 | q = 1 | |
2 | 12 | 1 ≤ w, h ≤ 20 | 1 ≤ s ≤ 2 | q = 1 | 1 |
3 | 9 | 1 ≤ w, h ≤ 20 | 1 ≤ s ≤ 3 | q = 1 | 1, 2 |
4 | 10 | 1 ≤ w, h ≤ 20 | 1 ≤ s ≤ 3 | 1 ≤ q ≤ 100 | 1, 2, 3 |
5 | 15 | 1 ≤ w, h ≤ 105 | s = 1 | 1 ≤ q ≤ 100 | 1 |
6 | 36 | 1 ≤ w, h ≤ 105 | 1 ≤ s ≤ 4 | 1 ≤ q ≤ 100 | 1, 2, 3, 4, 5 |
По запросу сообщаются баллы за каждую подзадачу.
№ | Входной файл (mining.in ) |
Выходной файл (mining.out ) |
---|---|---|
1 |
|
|