Олимпиада по информатике 7–8 классы — муниципальный этап ВсОШ 2023/2024: задания и ответы
Официальный комплект муниципального этапа Всероссийской олимпиады школьников по информатике для 7–8 классов (2023/2024 учебный год). Задания и решения с критериями оценивания — скачайте PDF или прорешайте онлайн по тексту ниже.
Задания — текст для прорешивания
Текст извлечён из официального PDF автоматически: формулы, таблицы и рисунки могут отображаться неточно — сверяйтесь с документом выше.
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023
Задача 1. Ферзь Ограничение по времени:
0.5 секунд
Пётр любит шахматы и математику. Он знает, что самая мощная фигура в шахматах — это ферзь, потому что он ходит и как ладья, на все клетки на одной с ним вертикали или горизонтали, и как слон, на все клетки по диагоналям. Ферзя можно поставить на доску 8 × 8 так, чтобы он контролировал (то есть мог переместиться в эти клетки за один ход) целых 27 клеток доски! Петра заинтересовало, какое максимальное количество клеток может контролировать ферзь на прямоугольных досках самых разных размеров. Помогите ему в решении этой задачи.
Формат входных данных Первая строка входных данных содержит целое число n (1 ⩽ n ⩽ 109 ) — размер доски по вертикали. Вторая строка входных данных содержит целое число m (1 ⩽ m ⩽ 109 ) — размер доски по горизонтали.
Формат выходных данных Программа должна вывести одно целое число — максимальное количество клеток, которое может контролировать ферзь на доске n × m. Обратите внимание на то, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).
Система оценки Решения, правильно работающие, когда n и m не превоcходят 10, будут оцениваться в 40 баллов. Решения, правильно работающие, когда n и m не превоcходят 500, будут оцениваться в 80 баллов.
Примеры стандартный ввод
стандартный вывод
8 8
27
3 4
Замечание Второй пример из условия приведён на рисунке. Крестиками обозначены клетки, которые контролирует ферзь.
Страница 1 из 7
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023
Задача 2. Рамка для рисунка Ограничение по времени:
1 секунда
У Алексея есть набор, который состоит из n палочек длины 1 и m палочек длины 2. Палочки можно соединять между собой, либо выстраивая их в линию, либо под прямым углом. Алексей хочет собрать из имеющихся палочек рамку прямоугольной формы, чтобы потом вставить в эту рамку лист бумаги и нарисовать красивый пейзаж для мамы на Новый год. При этом Алексей считает, что чем больше будет площадь прямоугольника, тем значимей будет его подарок. Поэтому ему важно определить максимальную площадь прямоугольника, границу которого можно собрать из имеющихся палочек.
Формат входных данных Первая строка входных данных содержит целое число n — количество палочек длины 1, 0 ⩽ n ⩽ 109 . Вторая строка входных данных содержит целое число m — количество палочек длины 2, 0 ⩽ m ⩽ 109 .
Формат выходных данных В единственной строке выведите единственное целое число — максимальную площадь прямоугольника, который можно сложить из имеющихся палочек. Если из имеющихся палочек невозможно сложить никакой прямоугольник, то выведите число 0. Обратите внимание на то, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).
Система оценки Решения, правильно работающие, когда n и m не превосходят 20, будут оцениваться в 20 баллов. Решения, правильно работающие, когда n и m не превосходят 1000, будут оцениваться в 40 баллов. Решения, правильно работающие, когда n и m не превосходят 5 · 105 , будут оцениваться в 60 баллов.
Примеры стандартный ввод
стандартный вывод
5 0
4 3
3 0
Замечание В первом примере есть 5 палочек длины 1. Из них можно сложить квадрат со стороной 1, его площадь равна 1, при этом одна палочка останется. Во втором примере есть 4 палочки длины 1 и 3 палочки длины 2. Из них можно сложить прямоугольник размера 2 × 3. В третьем примере есть 3 палочки длины 1, из них невозможно сложить прямоугольник.
Страница 2 из 7
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023
Задача 3. Телефонный справочник Ограничение по времени:
1 секунда
Саша недавно начала регистровать компанию по разработке чат-ботов и уже подала необходимые документы. Но добрые люди рассказали Саше, что в телефонном справочнике компании располагаются в лексикографически возрастающем порядке их названий. Что такое телефонный справочник, Саша не знает, но решила учесть рекомендации и поменять название своей компании, чтобы оно было как можно раньше в телефонном справочнике. Поскольку Саша уже подала документы, она не может полностью поменять название компании, но может сказать, что допустила опечатку, и поменять любые две буквы в названии местами. Помогите Саше выбрать новое название компании или оставить текущее.
Формат входных данных В единственной строке содержится одно слово, состоящее из строчных латинских букв (от «a» до «z») длиной n (2 ⩽ n ⩽ 106 ).
Формат выходных данных Выведите одно слово — новое название компании. Если название не изменилось, выведите изначальное название.
Система оценки Решения, верно работающие при n ⩽ 10, будут оцениваться в 20 баллов. Решения, верно работающие при n ⩽ 100, будут оцениваться в 40 баллов. Решения, верно работающие при n ⩽ 3 000, будут оцениваться в 60 баллов. Решения, верно работающие при n ⩽ 50 000, будут оцениваться в 80 баллов.
Примеры стандартный ввод
стандартный вывод
aefbz
abfez
abc
abc
Страница 3 из 7
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023
Задача 4. Задачи на печать! Ограничение по времени:
1 секунда
Олимпиады бывают не только личные, но и командные. В командной олимпиаде по программированию обычно принимают участие команды из трёх человек, которым предоставляется один компьютер и один комплект условий задач, причём задач обычно существенно больше, чем в личных олимпиадах. Условие каждой из задач помещается на одной, двух или трёх страницах. При этом условие может быть напечатано на двух сторонах одного листа, но для удобства команд на одном листе может располагаться условие только одной из задач. Для экономии бумаги, если условие задачи занимает две страницы, оно должно быть напечатано на двух сторонах одного листа, а если из трёх страниц — на двух сторонах одного листа и на одной стороне другого листа, вторая сторона которого останется чистой. При этом можно напечатать первую страницу такой задачи отдельно на чистом листе, а оставшиеся две страницы — на одном листе или, наоборот, первые две страницы распечатать на одном листе, а третью — на чистом листе. Задачи и все их страницы печатаются последовательно. Условия всех задач распечатываются на принтере в виде нескольких последовательных заданий. Для каждого задания необходимо задать диапазон печати: номера первой и последней страниц, которые будут напечатаны в этом задании (будут напечатаны все страницы в этом диапазоне), а также тип печати — односторонняя или двусторонняя. Вам необходимо минимизировать количество заданий для печати условий.
Формат входных данных Первая строка входных данных содержит целое число n (1 ⩽ n ⩽ 105 ) — количество задач в олимпиаде. Следующие n строк содержат по одному целому числу xi (1 ⩽ xi ⩽ 3) — количество страниц в i-й задаче.
Формат выходных данных Выведите единственное число — минимальное количество последовательных диапазонов, каждый из которых можно напечатать одной командой односторонней или двусторонней печати так, что условия всех задач будут напечатаны в удобном для командной олимпиады виде.
Система оценки Решения, верно работающие, когда все значения xi отличны от 1, будут оцениваться не менее чем в 30 баллов. Решения, верно работающие, когда все значения xi отличны от 2, будут оцениваться не менее чем в 30 баллов. Решения, верно работающие, когда все значения xi отличны от 3, будут оцениваться не менее чем в 30 баллов. Решения, верно работающие, когда n ⩽ 10, будут оцениваться не менее чем в 50 баллов. Решения, верно работающие, когда n ⩽ 1000, будут оцениваться не менее чем в 80 баллов.
Примеры стандартный ввод
стандартный вывод
4 1 3 2 1
2 3 3
Страница 4 из 7
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023
Замечание В первом примере на олимпиаду предложены 4 задачи, условия которых состоят из 1, 3, 2 и 1 страниц соответственно. Всего необходимо распечатать 7 страниц. Их можно распечатать за два задания: cтраницы 1–2 — односторонней печатью (это единственная страница первой задачи и первая из трёх страниц второй задачи), оставшиеся страницы 3–7 — двусторонней. Во втором примере на олимпиаду предложены 2 задачи, условия которых состоят из 3 страниц каждая. Всего необходимо распечатать 6 страниц. Их можно распечатать за два задания: cтраницы 1–1 — односторонней печатью (это первая из трёх страниц первой задачи), оставшиеся страницы 2–6 — двусторонней. При этом в первой задаче первая страница будет напечатана на одной стороне, потому что она напечатана односторонней печатью, а во второй задаче последняя страница будет напечатана на одной стороне, потому что в этом задании нечётное число страниц печатается на двух сторонах, поэтому вторая сторона этого листа будет пустой.
Страница 5 из 7
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023
Задача 5. Вечер кёрлинга Ограничение по времени:
1 секунда
Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени li и заканчивается в момент времени ri . Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени ri , то она может после него посмотреть любой матч j, который начинается не раньше момента времени ri , то есть lj ⩾ ri (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию lj − ri ⩾ t. Перерыв не может быть до или после всех просмотренных игр. Помогите Василисе составить набор, содержащий максимальное количество матчей, которые она сможет просмотреть полностью и при этом сделать перерыв продолжительностью не менее t между какими-то матчами, или определите, что такого набора не существует.
Формат входных данных Первая строка входных данных содержит число n (2 ⩽ n ⩽ 100 000) — количество показываемых матчей. Вторая строка входных данных содержит число t (1 ⩽ t ⩽ 109 ) — минимальная длина перерыва, который должна сделать Василиса. В следующих n строках содержится по два числа li и ri (1 ⩽ li < ri ⩽ 109 ) — начало и конец i-го матча.
Формат выходных данных Программа должна вывести число m — максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел — номера матчей, которые должна посмотреть Василиса, в порядке просмотра. Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какимито двумя матчами был перерыв хотя бы t, то выведите число −1.
Система оценки Решения, верно работающие при n ⩽ 15, будут оцениваться в 20 баллов. Решения, верно работающие при n ⩽ 1000, будут оцениваться в 40 баллов. Решения, верно работающие при ri ⩽ 105 , будут оцениваться в 30 баллов.
Примеры стандартный ввод
стандартный вывод
6 3 8 13 1 5 4 6 4 7 10 12 2 4
3 6 3 5
2 5 1 5 9 13
-1
Замечание В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6, который заканчивается в момент времени 4, потом переключится на матч 3, который Страница 6 из 7
Муниципальный этап всероссийской олимпиады школьников по информатике, 9–11 классы Москва, 10 декабря 2023 продолжается с 4 до 6. Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3. Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t = 5, нельзя.
Страница 7 из 7
Ответы и решения — показать
Официальные ответы и критерии оценивания жюри. Сначала решите задания самостоятельно.
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023
Задача 1. Абстрактный плакат
Можно заметить, что картинка совпадает с собой при повороте на 90◦ , поэтому количество прямоугольников в ответе будет делиться на 4. Для начала нарисуем выступающий единичный квадрат, сделаем этот прямоугольник, чтобы нарисовать всю верхнюю горизонтальную сторону (без выступающего сверху квадрата).
Нарисуем ещё три прямоугольника, полученные из данного поворотами.
Страница 1 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023
Оставшиеся линии можно нарисовать при помощи четырёх прямоугольников. Всего достаточно 8 прямоугольников. Пример такого ответа: 1 7 8 8 7 9 8 2 2 2 9 3 2 1 3 8 3 3 4 8 3 6 8 7 6 2 7 7 2 3 7 4
Задача 2. Максимальный поток
В терминах теории графов узлы будем называть вершинами, трубы — рёбрами, пропускную способность ребра — его весом. А такая задача известна, как задача нахождения максимального потока в графе. Сумма весов рёбер исходящих из истока A и входящих в сток I равна 18, поэтому поток не может быть больше 18. Но посмотрим жёлтую линию («разрез»), отделяющий вершины B и D от вершин C, E, G. Сумма весов рёбер, которые пересекает этот разрез, равна 16, поэтому величина потока не может быть больше 16.
Страница 2 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023
Чтобы получить максимальный результат нужно «насытить» эти рёбра, то есть пустить по ним максимальный объём воды. Получим такую часть ответа. B C 8 B E 4 D E 2 D G 2
Объём вытекающей из B воды равен 12, поэтому необходимо сделать сумму весов входящих в B рёбер тоже равным 12, для этого нужно будет подать из D в B объём 3 и насытить ребро AB. По ребру AD нужно будет подать 7, из которых 3 пойдёт в вершину B и по 2 — в вершины E и G. A B 9 A D 7 D B 3
Страница 3 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023
Теперь посмотрим на второй жёлтый разрез, отделяющий вершины C, E, G от вершин F и H.
Сумма весов рёбер, пересекающих разрез, равно 17, значит, нужно насытить все рёбра, кроме одного. Например, пустим через ребро EH объём 6. C F 3 E F 2 E H 6 G H 5
Страница 4 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 Теперь направим воду из C в E и из E в G так, чтобы обеспечить нужный объём входящей воды в E и G: C E 5 E G 3
Наконец, распределим воду по последним рёбрам. Поскольку в H втекло 11, а вытечь может не более 9, то нужно направить 2 единицы воды из H в F . H F 2 H I 9 F I 7
Задача 3. Телефонный справочник
Давайте рассматривать символы по одному, начиная с первого. Чтобы получить как можно меньшую строку, мы должны найти самый первый символ, который можно заменить на меньший, то есть правее которого есть меньший. Рассмотрим первое задание “cfwvfu”. Для символов “c” и “f” правее нет меньшего символа, а для символа “w” — есть, это предпоследний символ “f”. Получим ответ “cffvwu”. Рассмотрим второе задание “tbzttbetcb”. Здесь самый первый символ “t” можно заменить на меньший. Но чтобы строка была лексикографически наименьшей, мы должны выбрать справа наименьший из возможных символов для замены, это символ “b”. Но и символов “b” в строке несколько, поскольку выбранный символ “b” мы заменим на больший, то нужно использовать для перестановки последний символ “b”. Получим ответ “bbzttbetct”. Страница 5 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 В третьем задании дана строка “aefhfifjfkflzhz”. Здесь самый первый символ, правее которого есть меньший — это “h”. Поменяем его с последним вхождением символа “f”, получим ответ “aefffifjfkhlzhz”. В четвёртом задании “abcdfjhklmnqrtuvwzyx” можно заменить символ “j” на меньший символ ”h”, стоящий правее него. Получим “abcdfhjklmnqrtuvwzyx”.
Задача 4. Большая команда
В первом задании школ мало и ответ можно найти просто изучив входные данные, он равен 14. Во втором задании школ уже довольно много, поэтому понадобится провести некоторые вычисления. Например, запишем в ячейку D1 количество участников в команде. В ячейку D2 запишем формулу для вычисления количества команд из школы в строке 2: =INT($A2/D$1) — нужно поделить количество учащихся в школе на размер команды и взять целую часть. Теперь скопируем эту формулу на весь столбец D. Посчитаем сумму чисел в столбце D, то есть количество получившихся команд. Для этого можно использовать формулу типа =SUM(C2:C1001). Будем менять значение в ячейке D1, пока эта сумма не станет больше или равна необходимого количества команд. Это произойдёт при размере команды, равном 22. Аналогично можно решить и оставшиеся задания, только сложность будет с перебором значения размера команды. В задании 3 можно заполнить ячейки в строке 1 возможными значениями команды: 1, 2, 3, и т.д. А в столбце ниже него посчитать количество команд, которое получится при данном размере. Максимальный размер команды, при котором наберётся нужное количество команд, будет равен 379. В четвёртом задании числа столь большие, что такой подход потребует слишком много вычислений. Можно подобрать нужный размер, например, сначала увеличивая размер команды с шагом 1000. Затем определив диапазон для ответа из 1000 чисел, заполнить строку с размером команды с шагом 1. Или можно интерактивно менять значение в ячейке, увеличивая или уменьшая его, сокращая диапазон поиска. Например, сначала определить, что ответ находится от 200 000 до 300 000. Потом подобрать вторую цифру ответа, ответ будет находиться от 210 000 до 220 000. Затем подобрать третью цифру и т.д. Ответ на четвертое задание — 218 976.
Задача 5. Ферзь
Чтобы набрать 40 баллов достаточно написать решение, перебирающее все клетки, на которые можно поставить ферзя. Затем нужно посчитать количество клеток, которые бьёт этот ферзь. Для этого также переберём все оставшиеся клетки доски, и проверим, находятся ли они в одной горизонтали, вертикали или диагонали с выбранной клеткой. Запомним наибольшее количество клеток, которое может бить ферзь. Сложность такого решения будет O(n2 m2 ). В примере такого решения строки и столбцы доски нумеруются для удобства с нуля. n = int ( input ( ) ) m = int ( input ( ) ) ans = 0 f o r x in range ( n ) : fo r y in range (m) : count = 0 fo r xx in range ( n ) : f o r yy in range (m) : i f x==xx or y==yy or x−xx==y−yy or x−xx==yy−y : count += 1 ans = max( ans , count − 1 ) print ( ans ) Чтобы набрать 80 баллов, нужно уменьшить сложность решения до O(nm). Для этого можно находить количество клеток, которые бьёт ферзь, без цикла, то есть за O(1). Или, наоборот, заметить, что ферзя нужно поставить в центр доски, и найти циклами количество клеток, которые он бьёт. Пример второго решения, где ферзь ставится в клетку с координатами (bn/2c, bm/2c). n = int ( input ( ) ) Страница 6 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 m = int ( input ( ) ) x = n // 2 y = m // 2 count = 0 f o r xx in range ( n ) : fo r yy in range (m) : i f x==xx or y==yy or x−xx==y−yy or x−xx==yy−y : count += 1 print ( count − 1 ) Полное решение имеет сложность O(1). Здесь нужно заметить, что ферзь контролирует наибольшее количество клеток, находясь в центре доски, и посчитать их количество, без использования циклов. Пусть n ⩽ m, то есть доска “вытянута” по горизонтали, иначе поменяем значения n и m. Тогда в одной горизонтали с ферзём находятся m−1 клетка, а в одной вертикали — n−1 клетка. Диагонали, проходящие через ферзя, также могут содержать не более n клеток (поэтому в каждой из них не более n − 1 клетки, за вычетом клетки, в которой стоит ферзь), поэтому ответ будет равен (m − 1) + 3 · (n − 1). Но есть одно исключение: на квадратной доске, сторона которой имеет чётную длину, одна из диагоналей будет короче на одну клетку. Это, например, случай доски 8 × 8 (первый пример из условия), для которой ответ равен 27, а не 28. Почему так происходит, можно видеть на рисунке.
В этом случае просто вычтем 1 из ответа. Пример такого решения. n = int ( input ( ) ) m = int ( input ( ) ) i f n > m: n , m = m, n ans = 3 ∗ n + m − 4 i f n % 2 == 0 and m == n : ans −= 1 print ( ans )
Задача 6. Рамка для рисунка
Начнём с переборных решений, набирающих частичные баллы. Пусть n1 и n2 — количество палочек длины 1 и 2 соответственно.
Страница 7 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 40 баллов можно набрать, если перебирать две стороны прямоугольника a и b. Проверим, можно ли сложить из имеющихся палочек прямоугольник a × b. Должны выполняться два условия: общая длина всех палочек n1 + 2n2 должна быть не меньше периметра прямоугольника, равного 2a + 2b, и каждая сторона нечётной длины должна содержать хотя бы одну палочку длины 1, поэтому значение n1 должно быть не меньше количества нечётных чисел среди сторон a, b, a, b. Пример такого решения. n1 = int ( input ( ) ) n2 = int ( input ( ) ) max_side = ( n1 + 2 ∗ n2 ) // 2 ans = 0 f o r a in range ( 1 , max_side + 1 ) : fo r b in range ( 1 , max_side + 1 ) : i f n1 + 2 ∗ n2 >= 2 ∗ a + 2 ∗ b and n1 >= 2 ∗ ( a % 2 + b % 2 ) : ans = max( ans , a ∗ b ) print ( ans ) Чтобы набрать 60 баллов нужно перебирать только одну сторону, а не две. Пусть это сторона a. 2 Максимальное значение одной стороны, как и в предыдущем решении, равно b n1 +2n c (целочислен2 ное частное от деления суммы длин всех палочек на 2). Тогда у нас будет две стороны длины a. Проверим условие, что n1 не меньше, чем 2(a mod 2), то есть если a — нечётное, то найдётся хотя бы две палочки длины 1. Теперь определим наибольшее подходящее значение b для данного значения a. Для этого посчитаем длину оставшихся палочек n1 + 2n2 − 2a и поделим её на 2. При этом могло оказаться, что n1 < 2(a mod 2 + b mod 2), то есть значение n1 оказалось меньше, чем число нечётных чисел среди значений a, b, a, b, то нам не хватит палочек длины 1 для того, чтобы собрать нечётные отрезки длины a, b, a, b. Но ранее мы проверили, что нам хватает палочек длины 1 для того, чтобы собрать только отрезки a и a, поэтому это возможно только в случае нечётного b. В этом случае уменьшим значение b на 1. Так мы определяем наибольшее значение второй стороны b для ранее выбранной стороны a. Запомним наибольшее из значений площадей прямоугольников a × b. n1 = int ( input ( ) ) n2 = int ( input ( ) ) max_side = ( n1 + 2 ∗ n2 ) // 2 ans = 0 f o r a in range ( 1 , max_side + 1 ) : i f n1 < 2 ∗ ( a % 2 ) : continue b = ( n1 + 2 ∗ n2 − 2 ∗ a ) // 2 i f n1 < 2 ∗ ( a % 2 + b % 2 ) : b −= 1 ans = max( ans , a ∗ b ) print ( ans ) Чтобы написать полное решение, нужно избавится и от перебора всех возможных значений одной стороны. Нужно заметить, что среди всех прямоугольников с одинаковым периметром максимальная площадь будет у квадрата или у прямоугольника, стороны которого различаются на 1. Действительно, пусть прямоугольник имеет стороны a × b, при этом a + 1 < b. Рассмотрим прямоугольник (a + 1) × (b − 1) с таким же периметром. Его площадь будет равна ab + b − a − 1, то есть больше площади ab. Поэтому для максимизации периметра в качестве значения одной из сторон нужно выбрать 14 от максимально возможного периметра. Для этого в качестве значения минимальной стороны a возь2 мём значение b n1 +2n c, а значение b подберём наибольшее подходящее значение, как в предыдущем 4 Страница 8 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 решении. Но если значение a оказалось нечётным, то для формирования сторон длины a понадобится минимум 2 палочки длины 1, и, возможно, нам не хватит палочек длины 1 для достижения максимально возможного значения b. Поэтому необходимо рассмотреть как чётное, так и нечётное 2 2 значение a, то есть нужно взять не только a = b n1 +2n c, но и значение на 1 меньше — a = b n1 +2n c, 4 4 так как одно из них будет чётным. Для каждого из этих значений a выберем подходящее b и найдём наибольшее значение a × b. Пример такого решения. n1 = int ( input ( ) ) n2 = int ( input ( ) ) ans = 0 s i d e = ( n1 + 2 ∗ n2 ) // 4 f o r a in range ( s i d e − 1 , s i d e + 1 ) : i f n1 < 2 ∗ ( a % 2 ) : continue b = ( n1 + 2 ∗ n2 − 2 ∗ a ) // 2 i f n1 < 2 ∗ ( a % 2 + b % 2 ) : b −= 1 ans = max( ans , a ∗ b ) print ( ans ) Есть и другие способы решения задачи. Например, можно попробовать конструктивно построить решение так, чтобы две стороны прямоугольника a×b оказались максимально большими и при этом близки друг к другу. Для этого сначала разложим палочки длины 2 поровну на все стороны. У нас останется 0, 1, 2 или 3 палочки длины 2. Если осталось хотя бы две палочки длины 2, то увеличим на 2 длины двух сторон a. Если после этого осталась хотя бы одна палочка длины 2 и ещё одна палочка длины 2 или две палочки длины 1, то также можно сторону b увеличить на 2. Иначе попробуем используя палочки длины 1 выровнять длины сторон. После выравнивания длин сторон все оставшиеся палочки длины 1 разложим поровну по всем сторонам. После этого останется не более трёх палочек длины 1, если их две или три — то можно длины двух сторон увеличить на 1. Сложность реализации такого решения в том, что нужно аккуратно рассмотреть все случаи, не пропустив ни одного. n1 = int ( input ( ) ) n2 = int ( input ( ) ) a = 2 ∗ ( n2 // 4 ) b = 2 ∗ ( n2 // 4 ) n2 %= 4 i f n2 >= 2 : n2 −= 2 a += 2 i f n2 == 1 and n1 >= 2 : b += 2 n2 = 0 n1 −= 2 while a < b and n1 >= 2 : a += 1 n1 −= 2 while a > b and n1 >= 2 : b += 1 n1 −= 2 a += n1 // 4 b += n1 // 4 Страница 9 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 n1 %= 4 i f n1 >= 2 : a += 1 print ( a ∗ b )
Задача 7. Задачи на печать!
Будем рассматривать задачи последовательно, определяя, в каком режиме должна быть напечатана очередная задача. Например, если в задаче 2 страницы, то её условие должно быть напечатана только в двустороннем режиме. А если в задаче 1 страница, то всё зависит от того, в каком режиме была напечатана предыдущая страница. Если это был односторонний режим, то мы расширим предыдущий диапазон печати на новую задачу, а если двусторонний — то эту одну страницу можно напечатать в двустороннем режиме, однако, следующая страница обязательно должна стать началом нового диапазона печати, который может быть как односторонним, так и двусторонним. Заведём переменную mode, в которой будет храниться текущий режим печати — 1 для односторонней печати и 2 для двусторонней. Значение 0 означает, что очередная страница должна стать началом нового диапазона печати, который может быть любым. В переменной ans хранится общее число диапазонов печати. В переменной p хранится количество страниц в текущей задаче. Далее нужно аккуратно разобрать все случаи. Если p = 2 то мы обязательно переходим в режим 2, при этом если ранее режим был другим, то к ответу прибавляем 1. Если p = 1, то в режиме 1 не нужно делать ничего, в режиме 2 эта страница печатается в двустороннем режиме, но нужно перейти в режим 0 для начала нового диапазона со следующей страницы (потому что на обороте этой страницы ничего нельзя печатать), а в режиме 0 нужно перейти в режим 1, начав новый диапазон, то есть добавив к ответу 1. Наконец, разберём случай p = 3. Если до этого был режим 1, то мы печатаем одну страницу односторонней печатью, а ещё две страницы — двусторонней, поэтому нужно перейти в режим 2. Если мы были в режиме 2, то все три страницы можно напечатать в двустороннем режиме, потом нужно перейти в режим 0, потому что придётся начать новый диапазон. Аналогично поступим, когда режим был равен 0 — начнём новый двусторонний режим, напечатаем три страницы, а затем придётся начать новый диапазон, то есть в этом случае нужно просто увеличить значение ans на 1, сохранив значение mode равным 0. Пример такого решения. ans = 0 mode = 0 n = int ( input ( ) ) f o r i in range ( n ) : p = int ( input ( ) ) i f p == 1 : i f mode == 2 : mode = 0 e l i f mode == 0 : mode = 1 ans += 1 i f p == 2 : i f mode != 2 : ans += 1 mode = 2 i f p == 3 : i f mode == 1 : mode = 2 ans += 1 e l i f mode == 2 : mode = 0 Страница 10 из 11
Муниципальный этап всероссийской олимпиады школьников по информатике, 7–8 классы Москва, 10 декабря 2023 else : ans += 1 print ( ans ) Частичные решения можно получить используя полный перебор вариантов. Задачу можно решить и динамическим программированием, в котором целевой функцией f (i) будет количество диапазонов, необходимое для печати первых i задач. При этом придется ввести и второй параметр, аналогичный по смыслу переменной mode.
Страница 11 из 11