Задача Починка блюдца
 Скачать 220.89 Kb.
|
|
Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 Задача 1. Починка блюдца Ограничение по времени: 1 секунда Придя домой, уставший Константин захотел выпить свой любимый чай. Для этого ему нужно было достать с высокой полки самое красивое блюдце, которое представляет собой клетчатое поле N × N . Но, так как Константин не очень аккуратен, он блюдце разбил. В спешке Костя начал думать, как же починить столь ценную вещь. И тогда он заметил, что блюдце распалось ровно на клетчатые квадраты K × K! Более того он обнаружил, что N делится на K без остатка. Восстановив исходное блюдце из кусочков, Костя понял, что ему также нужно купить клей, чтобы склеить все соприкасающиеся кусочки в исходное клетчатое поле N × N . Он тут же посчи- тал, что, для того чтобы проклеить границу между двумя соприкасающимися клетками длины 1, необходима ровно одна банка клея. Помогите Косте посчитать, сколько банок клея ему нужно купить, чтобы склеить его любимое блюдце. Формат входных данных В первой строке входных данных записано одно целое число N (1 6 N 6 10 4 ) — размер квад- ратного блюдца. Во второй строке записано одно целое число K (1 6 K 6 N , N делится на K без остатка) — размер квадратного осколка блюдца. Формат выходных данных В единственной строке выведите одно число — количество банок клея, которые Косте понадо- бится купить, чтобы починить блюдце. Если на самом деле блюдце не разбилось, и Костя зря паниковал, выведите число 0. Система оценки Решения, правильно работающие только для случаев, когда N и K не превосходят 20, будут оцениваться в 25 баллов. Решения, правильно работающие только для случаев, когда K = 1, будут оцениваться в 30 баллов. Примеры стандартный ввод стандартный вывод 2 1 4 3 3 0 Замечание Рисунок ниже иллюстрирует первый пример: Различными цветами обозначены различные части блюдца, изначально имевшего размер 2 × 2. Между частями белым цветом обозначен клей, который Костя купил и намазал, чтобы починить блюдце. Каждая часть блюдца имеет размер 1 × 1. Во втором тестовом примере Костя зря паниковал, и на самом деле он не разбил блюдце! Страница 1 из 7 Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 Задача 2. Ну все, я попрыгал! Ограничение по времени: 1 секунда Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из N ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков. Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее X, а длинный — на произвольное число, не большее Y (X < Y ). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков. Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех N ступенек. Формат входных данных В первой строке входных данных записано целое число X — максимальная длина короткого прыжка. Во второй строке записано целое число Y (1 6 X < Y 6 10 18 ) — максимальная длина длинного прыжка. В третьей строке записано целое число N (1 6 N 6 10 18 ) — количество ступенек в спуске. Формат выходных данных В единственной строке выведите целое число — минимальное число прыжков, необходимое Ма- рио для спуска. Система оценки Решения, правильно работающие только для случаев, когда X, Y и N не превосходят 10 5 , будут оцениваться в 35 баллов. Решения, правильно работающие только для случаев, когда X, Y и N не превосходят 10 9 , будут оцениваться в 50 баллов. Примеры стандартный ввод стандартный вывод 2 3 5 2 1 2 4 3 1 100 1000000000000000000 19801980198019801 Замечание На изображениях ниже приведены возможные способы решения первых двух тестов из условия: Страница 2 из 7 Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 Обратите внимание, что входные данные, а также ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal. Страница 3 из 7 Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 Задача 3. Андрей и порталы Ограничение по времени: 1 секунда Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы. Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели по- строить N порталов. Портал с номером i расположен в точке с координатой x i . Если в текущий момент времени вы находитесь в одной точке с каким-нибудь порталом, то можете всего за одну секунду телепортироваться в любой другой портал вне зависимости от расстояния между ними. А время, требуемое для преодоления расстояния между точками с координатами p и q без использова- ния порталов равно |p − q| секунд. Андрей является влиятельным гражданином, поэтому он может использовать систему порталов любое количество раз. Изначально Андрей находится в точке s, а точка проведения олимпиады имеет координату e. Помогите Андрею понять, как быстро он может попасть на олимпиаду, ведь каждая секунда на счету. Формат входных данных В первой строке входных данных записано одно целое число s — начальное положение Андрея. Во второй строке записано одно целое число e — место проведения олимпиады. В третьей строке записано количество порталов N (2 6 N 6 2 · 10 5 ). В каждой из N следующих строк записано целое число x i — координата портала с номером i. Все числа s, e, x i по модулю не превосходят 10 8 Формат выходных данных Выведите одно число — минимальное количество секунд, которое потребуется Андрею для того, чтобы добраться до места проведения олимпиады. Система оценки Решения, правильно работающие только для случаев, когда N не превосходит 10, будут оцени- ваться в 20 баллов. Решения, правильно работающие только для случаев, когда N не превосходит 1 000, будут оце- ниваться в 60 баллов. Пример стандартный ввод стандартный вывод 0 4 3 1 3 5 3 Замечание Рассмотрим пример из условия. Если бы Андрей не мог пользоваться порталами, он бы смог добраться до точки проведения олимпиады за |0 − 4| = 4 секунды. Однако, можно действовать так: 1. Дойти до портала с номером 1 за |0 − 1| = 1 секунду. 2. Телепортироваться в портал с номером 2 за одну секунду. 3. Дойти от портала с номером 2 до точки проведения олимпиады за |3 − 4| = 1 секунду. Суммарно получаем 1 + 1 + 1 = 3 секунды. Страница 4 из 7 Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 Задача 4. Путешествие по джунглям Ограничение по времени: 1 секунда Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан. Всего в джунглях есть N лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от 1 до N . Расстояние между соседними лианами составляет D метров. Находясь на i-й лиане, Коко может совершить прыжок с нее не более, чем на a i метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать. В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо. Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться. Формат входных данных Первая стока входных данных содержит целое число N (2 6 N 6 10 5 ) — количество лиан. Во второй строке записано целое число D (1 6 D 6 10 9 ) — расстояние между соседними лианами. В каждой из следующих N строк записано целое число a i (1 6 a i 6 10 9 ) — на сколько метров вправо может прыгнуть Коко, находясь на i-й лиане. Формат выходных данных Выведите единственное целое число — максимальный номер лианы, до которой сможет добраться Коко. Система оценки Решения, работающие при N 6 15, будут набирать не менее 16 баллов. Решения, работаюшие при D = 1, будут набирать не менее 12 баллов. Решения, работающие при N 6 2000, будут набирать не менее 56 баллов. Пример стандартный ввод стандартный вывод 5 3 7 8 2 2 6 4 Замечание В примере из условия дано 5 лиан, а расстояние между лианами равно 3 метрам. Находясь на первой лиане, Коко может прыгнуть не более, чем на 7 метров, то есть она сможет допрыгнуть до второй и третьей лианы. Ей нужно остановиться на второй лиане, потому что со второй лианы длина прыжка равна 8 метрам, и это позволит ей допрыгнуть до четвёртой лианы. С четвёртой лианы длина прыжка равна 2 и это меньше, чем расстояние до следующей лианы, поэтому Коко остановится на четвёртой лиане. Страница 5 из 7 Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 Задача 5. Финансовая реформа Ограничение по времени: 1 секунда Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон. Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил про- извести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами 1, 10, 100 и 1 000 бурлей. Мише данная система показалась крайне банальной, поэтому он решил придумать что-то свое. Мальчик выбрал два целых числа x и y (x 6 y) и заявил, что теперь в Берляндии будут ис- пользоваться только банкноты с номиналами x, x + 1, x + 2, . . . , y бурлей. Вскоре реформа была принята и вступила в силу, однако населению страны это совсем не понравилось. Недовольства на- чались из-за того, что теперь, используя новые банкноты, можно было набрать далеко не любую сумму. Например, если Мишей были выбраны числа x = 5 и y = 7, то невозможно набрать суммы 1, 2, 3 и 4 бурлей. Также не получится набрать суммы 8 и 9 бурлей. Если же выбрать числа x = y = 2, то невозможно будет набрать любую нечетную сумму. Миша, находясь на грани увольнения, решил успокоить население Берляндии и предъявить такое минимальное число N , что при помощи новых банкнот возможно набрать любую сумму, начиная с N . Таким образом, должно быть возможно набрать суммы N бурлей, N + 1 бурлей, N + 2 бурлей, и так далее. Помогите Мише найти искомое число N и избежать увольнения. Формат входных данных В первой строке входных данных записано целое число x — минимальный номинал новых банк- нот. Во второй строке записано целое число y (1 6 x 6 y 6 2 · 10 9 ) — максимальный номинал новых банкнот. Формат выходных данных Выведите одно натуральное число N — минимальное число, такое, что при помощи банкнот с номиналами x, x + 1, x + 2, . . . , y можно набрать любую сумму, начиная с N бурлей. Если такого числа не существует, в качестве ответа выведите −1. Система оценки Решения, правильно работающие только для случаев, когда x и y не превосходят 10 4 , будут оцениваться в 40 баллов. Примеры стандартный ввод стандартный вывод 5 7 10 2 2 -1 1900000000 2000000000 36100000000 Замечание В первом примере имеются банкноты трех номиналов: 5, 6 и 7 бурлей. Ниже перечислены суммы, которые можно набрать при помощи данных банкнот: • 5 = 5, • 6 = 6, • 7 = 7, Страница 6 из 7 Школьный этап всеросcийской олимпиады по информатике для 9–11 классов Москва, 27 октября 2021 • 10 = 5 + 5, • 11 = 5 + 6, • 12 = 5 + 7, • 13 = 6 + 7, • . . . Можно показать, что при помощи банкнот данных номиналов возможно набрать любую сумму, начиная с 10 бурлей. Во втором примере есть банкноты всего одного номинала: 2 бурля. При помощи данных банкнот можно набрать только любую чётную сумму: 2, 4, 6, .... Таким образом, искомого числа N не существует. Обратите внимание, что ответ может получиться достаточно большим, поэтому следует ис- пользовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal. Страница 7 из 7 |