Школьный этап всероссийской олимпиады по информатике для 78 классов
 Скачать 276.98 Kb.
|
|
Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 1. Ракета на старт Сергей собирает многоступенчатые ракеты. Для большей точности измерений параметров полета на каждой ступени ракеты он написал её мощность. Но он совершенно забыл, что мощности ступеней любой ракеты должны строго возрастать. К примеру, мощности ступеней ракеты могут принимать значения 1 4 7, а 3 2 4 — не могут. Собирать новую ракету Серёжа не хочет, однако он может вытащить некоторые ступени, не меняя порядка оставшихся. К примеру, из ракеты с мощностями ступеней 1 8 3 4 можно получить ракету 1 3 4 (вытащив ступень с мощностью 8), а ракеты 1 4 3 (порядок ступеней с мощностями 4 и 3 был изменен) и 1 8 3 (мощности ступеней не возрастают) получить нельзя. Помогите Сергею вытащить минимальное количество ступеней так, чтобы мощность остальных ступеней строго возрастала. У Сергея есть четыре ракеты. В таблице ниже для каждой ракеты приведена последовательность мощностей её ступеней. Номер ракеты Последовательность мощностей 1 5 3 4 2 3 2 1 6 3 2 5 8 3 4 6 7 5 6 7 1 2 8 4 2 5 3 5 3 4 7 3 8 4 9 6 7 Ответом на данную задачу являются четыре последовательности целых чисел: каждая из них — это последовательность мощностей оставшихся ступеней соответствующей ракеты. Каждую после- довательность записывайте в соответствующей ей строке. Числа в последовательности должны быть разделены пробелом. Каждая последовательность должна строго возрастать, а также иметь как можно большую длину. Если существует несколько вариантов ответа, можно вывести любой из них. Если вы не можете дать ответ для какой-то из ракет, запишите в качестве ответа для данной ракеты число 0. Замечание Рассмотрим пример. Допустим, у какой-то ракеты последовательность ступеней равна 1 4 5 2 3. Для этой ракеты возможно два варианта ответа. Последовательность чисел в ответе может быть такой: 1 2 3. Или последовательность чисел может быть такой: 1 4 5. Страница 1 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 В ответе нужно указать одну, любую из этих последовательностей. Страница 2 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 2. Межпланетные грузовые перевозки В последнем обновлении компьютерной игры «Totally Space!» появилась возможность заказы- вать космические корабли. Каждый корабль характеризуется своей грузоподъемностью. Терминал заказа показывает два числа: количество уже заказанных космических кораблей x и начальную грузоподъемность кораблей y. Также у вас есть k очков опыта, которые вы можете израсходовать следующим образом: • Заказать новый корабль с грузоподъемностью y. Стоимость операции: 1 очко опыта. • Увеличить на 1 грузоподъемность всех кораблей, уже заказанных на данный момент времени. Стоимость операции: 1 очко опыта. Вы захотели потратить все k очков опыта, и вам стало интересно, какова же максимальная масса груза, которую можно перевезти, используя все заказанные корабли. Кроме того, вы, как частый посетитель игры «Totally Space!», еще не раз столкнётесь с данной задачей, поэтому вам предлагается решить её для четырёх разных ситуаций. Номер ситуации x y k 1 1 1 2 2 3 4 4 3 6 6 7 4 2 8 8 Ответом на данную задачу являются четыре целых числа, перечисленных через пробел: макси- мальная масса перевозимого груза в первой, второй, третьей и четвертой ситуациях соответственно. Если вы не можете дать ответ для какой-то ситуации, запишите в качестве ответа для данной ситуации любое число. Замечание Рассмотрим пример. Пусть количество уже заказанных кораблей равно 2, и их грузоподъ- емность равна 1, вам доступно 2 очка опыта. Тогда один из оптимальных вариантов следующий: увеличить количество заказанных кораблей на 1 и потратить одно очко опыта, а затем увеличить грузоподъемность всех заказанных кораблей на 1, потратив еще одно очко опыта. Таким образом, максимальная масса груза, перевозимая данными кораблями, будет равна 6 условных единиц. Страница 3 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 3. Яблочный пирог Михаил узнал, что его мама хочет испечь яблочный пирог. Для этого мама приготовила пря- моугольную форму размером n × m. Также она взяла специальный круглый нож, чтобы вырезать из яблок заготовки одинаковой формы и размера k. Будучи хорошим математиком, Михаил смог сразу сказать маме, сколько заготовок поместится в один слой в подготовленную форму. После того, как заготовки из яблок поместили в форму, мама Михаила решила поэксперименти- ровать и добавить к яблокам слив. Все имеющиеся у них сливы имели одинаковый размер, и каждая из них могла идеально поместиться между четырьмя яблочными заготовками (см. рисунок). Мама попросила Михаила посчитать, сколько же в таком случае потребуется слив, и он сразу ответил на этот вопрос. Подумайте, какими формулами воспользовался Михаил для подсчета количества заготовок яблок и слив в форме для пирога. Ответом на данную задачу являются две строки, в каждой из которых записано одно выраже- ние. Первое выражение — это формула подсчета количества заготовок яблок, второе — формула подсчета количества заготовок слив. Выражения могут содержать целые числа, переменные n, m и k (записываемые английскими буквами), операции сложения (обозначаются +), вычитания (обозна- чаются -), умножения (обозначаются *), деления (обозначаются /) и круглые скобки. Запись вида 2n для обозначения произведения числа 2 и переменной n некорректна, нужно писать 2 ∗ n. Если вы не знаете какой-то формулы, вместо неё следует написать число «0» (без кавычек). Пример правильной формы записи ответа: (n + m − 1) ∗ k + n (n ∗ 21) − (m + k) Гарантируется, что n, m, k — натуральные числа, n и m делятся на k. Вот так выглядит форма, заполненная двенадцатью заготовками из яблок и шестью сливами. Страница 4 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 4. Петя, Ваня и Леон В известной игре Stawl Brars Пете выпал новый персонаж, которого зовут Леон. У Пети и его друга Вани один аккаунт на двоих, поэтому они решили сыграть в игру и решить, кто первый будет играть за этого персонажа. Игра проходит на клетчатом поле размера 7 × 7 (см. рисунок ниже). Игроки ходят по очереди, начинает Петя. За один ход можно сдвинуть Леона либо на одну клетку вверх, либо на одну клетку влево, либо на одну клетку по диагонали вверх-влево. Например, если персонаж находится в клетке B6, то его можно передвинуть либо в клетку A6, либо в клетку B5, либо в A5. Выигрывает тот, кто первый поставит Леона в клетку A1. Ребята договорились, что изначально персонаж должен стоять в любой клетке нижней строки. Теперь Петя задумался, сколько существует таких клеток, что если Леон будет стоять в одной из них, то Петя сможет выиграть независимо от действий Вани. Для этого ему нужна ваша помощь: перечислите все клетки на нижней строке, начиная от которых, Петя сможет выиграть независимо от действий противника. В качестве ответа запишите все выигрышные клетки на нижней горизонтали через пробел. Клетки на нижней строке именуются согласно соответствующим им столбцам. Например, клетка A7 будет записана буквой A, а клетка G7 — буквой G. Вот так выглядит доска, на которой играют ребята: Страница 5 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 5. Поезд Ограничение по времени: 1 секунда Два друга-биолога Василий и Петр едут в Африку на поезде. Билеты они покупали в разное время и не смогли получить места в одном вагоне. Василий купил билет на место с номером X, а Петр — на место с номером Y . Все поезда в структуре РЖД комплектуются вагонами с одинаковым числом посадочных мест, равным K. Нумерация мест сквозная: в первом вагоне расположены места с номерами от 1 до K, во втором вагоне — места с номерами от K + 1 до 2K, и так далее. Помогите Василию посчитать, сколько раз он должен перейти из одного вагона в соседний для встречи с Петром. Формат входных данных В первой строке входных данных записано целое число K (1 6 K 6 10 9 ) — число посадочных мест в каждом вагоне. Во второй строке записано целое число X — номер места Василия. В третьей строке записано целое число Y (1 6 X < Y 6 10 9 ) — номер места Петра. Формат выходных данных Выведите одно целое число — количество переходов Василия из одного вагона в соседний. Система оценки Решения, работающие при K = 1, будут набирать не менее 12 баллов. Решения, работающие при K 6 2, будут набирать не менее 28 баллов. Решения, работающие, когда все числа не превосходят 100, будут набирать не менее 24 баллов. Пример стандартный ввод стандартный вывод 3 3 7 2 Замечание В примере из условия каждый вагон укомплектован тремя посадочными местами: в первом вагоне расположены места с номерами 1, 2, 3, во втором — с номерами 4, 5, 6, в третьем — с номерами 7, 8, 9. Номер места Василия равен 3, значит он находится в первом вагоне. Петр купил билет на место с номером 7, значит он в третьем вагоне. Чтобы встретиться, Василий должен перейти из первого вагона во второй, затем из второго в третий, после чего друзья окажутся в одном вагоне. Таким образом, Василию необходимо совершить два перехода между соседними вагонами. Страница 6 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 6. Странное устройство Ограничение по времени: 1 секунда По приезде Василий с Петром обнаружили в своем номере в гостинице странный прибор. Он был оснащен дисплеем, на котором показывалось число 0, и двумя кнопками. Василий сразу понял, что первая кнопка увеличивает число на дисплее на 1, а вторая умножает его на K. В этот момент Петр обнаружил на своей кровати листок бумаги, на котором было написано единственное число N . Теперь друзья хотят воспроизвести число N на дисплее найденного ими устройства, и, поскольку их ждет еще множество дел, им интересно минимальное число нажатий на кнопки устройства для получения числа N . Формат входных данных В первой строке входных данных записано целое неотрицательное число N (1 6 N 6 10 9 ). Во второй строке входных данных записано целое положительное число K (2 6 K 6 10 9 ). Формат выходных данных Выведите единственное число — минимальное количество нажатий на кнопки устройства для получения на его дисплее числа N . Система оценки Решения, работающие при K = 2, будут набирать не менее 20 баллов. Решения, работающие при N 6 20, будут набирать не менее 15 баллов. Решения, работающие при N 6 10 5 , будут набирать не менее 35 баллов. Пример стандартный ввод стандартный вывод 4 2 3 Замечание В примере из условия Василий и Петр хотят воспроизвести число 4. Кнопка умножает на 2 число, которое показывается на дисплее. Первой операцией друзья увеличивают текущее число на 1, нажимая первую кнопку, после чего оно становится равно 1. Затем они умножают его на 2, нажимая вторую кнопку. Текущее число становится равно 2. После чего, для получения на дисплее числа 4 достаточно один раз нажать вторую кнопку и умножить текущее число (то есть 2) на 2. Несложно показать, что меньше, чем за три операции, получить число 4 невозможно. Таким образом, минимальное число действий равняется трем. Страница 7 из 8 Школьный этап всероссийской олимпиады по информатике для 7–8 классов Москва, 27 октября 2021 Задача 7. Удаление данных Ограничение по времени: 1 секунда Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера. На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N . У каждого из файлов есть размер в байтах: a 1 , a 2 , . . . , a N . Все данные на компьютере Сергея хорошо зашиф- рованы. Шпион определил, что для удаления файла с номером i понадобится минимум из a i−1 и a i+1 секунд (для удаления первого файла потребуется a 2 секунд, а для удаления последнего — a N −1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно. У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы. Сергей может удалять файлы последовательно в любом порядке. Формат входных данных В первой строке выходных данных записано одно целое число N (1 6 N 6 10 5 ) — количество файлов на компьютере шпиона. В каждой из следующих N строк записано по одному целому числу a i (1 6 a i 6 10 4 ) — размер файла с номером i на компьютере Сергея. Формат выходных данных В единственной строке выведите одно число — минимальное время, которое понадобится Сергею для удаления всех файлов. Система оценки Решения, правильно работающие только для случаев, когда N не превосходит 10, будут оцени- ваться в 20 баллов. Решения, правильно работающие только для случаев, когда N не превосходит 1 000, будут оце- ниваться в 60 баллов. Примеры стандартный ввод стандартный вывод 5 1 2 3 1 100 4 1 1 0 Замечание В первом примере у Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже: 1. Удалим последний файл. Это займет одну секунду. 2. Затем удалим файл размера 2 за одну секунду. 3. Далее удалим файл размера 3 за одну секунду. 4. Теперь удалим любой из оставшихся двух файлов за одну секунду. 5. Последний файл моментально удалится сам. Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды. Во втором примере у Сергея изначально есть всего один файл, который сразу же удалится. Страница 8 из 8 |