олимпиада ВСОШ школьный этап 2023-2024
ВСОШ

24-27 октября 2023 Олимпиада Сириус задания и ответы по информатике 5-11 класс школьный этап

Автор

Официальные задания, ответы и решения для школьного этапа 2023-2024 всероссийской олимпиады школьников ВСОШ по информатике для 5, 6, 7, 8, 9, 10, 11 класса, которая проходила на официальном сайте Сириус курсы 24-27 октября 2023 года для каждого региона России.

Задания и ответы для 1 группы регионов:

Задания и ответы для 2 группы регионов:

Задания и ответы для 3 группы регионов:

Задания и ответы для 4 группы регионов:

Требования к проведению школьного этапа ВсОШ по информатике. При выполнении заданий олимпиады для 7−8 класса необходимо использование компьютера или ноутбука с установленным редактором электронных таблиц. Если участник будет решать задания на программирование, то необходимо установить среду разработки. Для 9−11 классов все задачи предполагают наличие установленного языка программирования.

Видео разбор заданий 5-6 класс олимпиада по информатике

Видео разбор заданий 7-8 класс олимпиада по информатике

Видео разбор заданий 9-11 класс олимпиада по информатике

Форма и количество заданий на школьном этапе всероссийской олимпиады школьников на платформе «Сириус.Курсы» по информатике в 2023/24 учебном году

Задания бывают двух видов — задания с вводом ответа и задания по программированию. Каждое задание оценивается в 100 баллов.

В заданиях с вводом ответа необходимо ввести ответ в виде числа, строки, нескольких чисел, нескольких строк, сопоставить или ранжировать элементы, сделать выбор на картинке. Форма представления ответа указана в условии задачи. Проверка заданий производится автоматически, поэтому ответ должен быть дан точно в таком виде, который требуется в условии. В этих задачах оценивается последнее решение, которое было сдано в тестирующую систему, оценка производится после окончания олимпиады. Баллы по этим задачам не будут известны во время олимпиады.

В заданиях по программированию решением является программа на одном из языков программирования. Решение проверяется на наборе тестов сразу после сдачи, баллы становятся известны во время олимпиады. В этих задачах оценивается решение, которое набрало наибольшее число баллов во время олимпиады.

В варианте для 5–6 классов предлагается 5 заданий с вводом ответа.

В варианте для 7–8 классов предлагается 4 задания с вводом ответа (для выполнения одного из заданий понадобятся электронные таблицы) и 3 задания по программированию. Оценивается только 5 заданий из 7, по которым был получен максимальный результат.

В варианте для 9–11 классов предлагается 5 заданий по программированию. Максимальный возможный балл в каждом классе равен 500.

Список языков программирования и требования к программам на школьном этапе всероссийской олимпиады школьников по информатике на платформе «Сириус.Курсы» в 2023/24 учебном году

В задачах по программированию на проверку необходимо сдать текстовый файл, подготовленный в какой-либо среде разработки на компьютере. Файл должен содержать только текст программы и никакой служебной информации, например, XML-разметки Jupyter Notebook и т.д. Не рекомендуется использовать мобильные устройства (телефоны, планшеты) и онлайн-среды разработки (в том числе Jupyter Notebook). На школьном этапе всероссийской олимпиады по информатике тестирующая система будет поддерживать следующие языки программирования:

  • Python 3
  • C и C++
  • Pascal
  • Java
  • C#
  • Kotlin
  • Go
  • PHP
  • Кумир
  • Rust

Сохраните решение в простом текстовом файле (например, файл с расширением cpp для программы на C++, с расширением py для программы на Python и т.д.). Решение должно в точности соответствовать условию задачи. В частности, программа должна считывать и выводить данные в том виде, в котором это описано в условии.

Обратите внимание на следующее: 1. Во входных данных каждое число задано в отдельной строке, и вводить числа нужно по одному, нажимая «Enter» после каждого ввода. 2. Программа не должна выводить никаких иных сообщений, кроме того, что описано в условии задачи. В частности, нельзя выводить сообщения вида «Введите число», «Ответ» и т. д. Нельзя осуществлять какой-либо дополнительный отладочный вывод. 3. Целые числа во входных и выходных данных записываются только цифрами, то есть недопустимо использование записи 1000000.0 или 1e6 вместо числа 1000000.

Задания для 5-6 классов

Задача 1. Забег Алёша, Боря, Саша, Дима и Егор участвовали в соревновании по бегу. После окончания соревнования каждый сделал два утверждения о его результатах: • Алёша сказал, что он прибежал последним, а Дима — либо вторым, либо третьим. • Боря сказал, что он прибежал вторым, а Егор — либо последним, либо предпоследним. • Саша сказал, что он прибежал вторым, а Боря — либо третьим, либо четвёртым. • Дима сказал, что он прибежал первым, а Алеша — либо вторым, либо третьим. • Егор сказал, что он прибежал четвёртым, а Саша — либо первым, либо вторым.

Понятно, что некоторые мальчики ошиблись в указании своего места или места кого-то из своих друзей. Расположите результаты участников забегов в порядке, при котором наибольшее количество из десяти высказанных утверждений было бы верным. В ответе напишите первые буквы имён мальчиков в том порядке, в котором они финишировали.

Задача 2. Выражение

Есть девять карточек. На шести из них написаны цифры 1, 2, 3, 4, 5, 6, на двух — знаки сложения «+», ещё на одной — знак умножения «×». Составьте из этих карточек правильное математическое выражение, значение которого было бы как можно больше. В ответе запишите строку, содержащую по одной цифре 1, 2, 3, 4, 5, 6, два знака «+» и один знак «∗», который обозначает операцию умножения. Необходимо использовать все карточки, выражение должно начинаться и заканчиваться цифрой. Чем больше будет результат вашего выражения, тем больше баллов вы получите.

Задача 3. Подушки для жирафов

В гостинице для жирафов администрация хочет запастись подушками так, чтобы можно было удовлетворить потребности любого своего возможного постояльца. Известно, что жирафам в зависимости от длины их шеи нужно сложить стопку из одной или нескольких подушек толщиной от 1 до 50 дециметров. Однажды горничная сообщила, что у неё осталось только шесть свободных подушек толщиной 1, 2, 5, 10, 13, 19 дециметров. Несложно заметить, что в сумме они дают 50 дециметров. В гостиницу должен заехать один очень важный жираф, но, к сожалению, длина его шеи администрации не была известна. Администрация решила заранее определить возможную длину шеи гостя, при которой ему не смогут подобрать набор подушек нужной толщины. Определите все возможные длины шеи жирафа (от 1 до 50), для которых нельзя подобрать набор подушек среди имеющихся нужной толщины. Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. Ответы выражайте в дециметрах, записывая только числа в ответе, без указания единицы измерения.

Задача 4. Гоночная трасса

Гоночная трасса имеет форму, изображённую на рисунке. Гоночный автомобиль выезжает из левого верхнего угла трассы и за первую минуту перемещается на 1 клетку вправо. Далее за каждую последующую минуту автомобиль перемещается на целое число клеток по прямой в одном направлении. Каждую минуту автомобиль может изменять скорость не более чем на 1, то есть за каждую минуту автомобиль проезжает столько же клеток, сколько за предыдущую минуту, или на одну клетку больше или на одну клетку меньше.

Поскольку каждое перемещение выполняется по прямой, в тех клетках, в которых происходит поворот трассы, должно закончиться очередное перемещение автомобиля. Постройте алгоритм прохождения автомобилем трассы за минимальное время. Автомобилю необходимо завершить свой маршрут также в левом верхнем углу трассы, при этом последнее перемещение требуется осуществить на 1 клетку, чтобы автомобиль остановился в конечной клетке трассы. В ответе запишите последовательность чисел, соответствующую перемещению автомобиля каждую минуту.

Каждые два соседних числа в последовательности должны отличаться не более, чем на 1, первое и последнее число должны быть равны 1. Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. Чем меньше чисел будет в вашем ответе, тем больше баллов вы получите (при условии, что последовательность перемещений будет удовлетворять всем необходимым условиям). Например, если трасса имела бы такой вид, как на рисунке справа, то в ответе необходимо записать числа 1, 2, 2, 2, 1, 1, 1. На рисунке эти числа записаны в конечных клетках соответствующего перемещения.

Задача 5. Бег по пересечённой местности

Участникам соревнования по бегу по пересечённой местности необходимо преодолеть маршрут из левого верхнего угла в правый нижний угол участка, состоящего из 8×8 клеток. Участник может перемещаться из клетки в одну из четырёх клеток, имеющих общую сторону с клеткой, где он находится в данный момент, не выходя при этом за границу квадрата.

На рисунке изображён вид участка и один из возможных маршрутов бегуна. Участники всегда выбирают кратчайший маршрут. Организаторы соревнований хотят удлинить маршрут спортсменов, для этого они планируют перекрыть некоторые клетки препятствиями, чтобы они стали недоступны для участников. Организаторы хотят разместить препятствия так, чтобы кратчайший маршрут от старта до финиша стал как можно длиннее.

Также они хотят использовать минимально возможное число препятствий. В ответе запишите 8 строк по 8 символов «.» и «#», где символ «.» означает пустую клетку, а символ «#» — клетку с препятствием. Левый верхний и правый нижний углы вашего ответа должны быть свободными, также должен существовать маршрут из левого верхнего в правый нижний угол.

Чем длиннее будет кратчайший путь от старта до финиша в вашем ответе, тем больше баллов вы получите. При одинаковой длине кратчайшего пути больше баллов получит ответ, содержащий меньшее число препятствий. При этом, независимо от количества препятствий, решение с большей длиной пути получит больше баллов, чем с меньшей.

Задания для 7-8 классов

Задача 1. Защитный экран В радиологической лаборатории во время экспериментов используются защитные свинцовые экраны. В зависимости от расстояния, на которое излучение может проникнуть в материал (проникающей способности), подбирается экран из одной или нескольких свинцовых пластин толщиной от 1 до 100 сантиметров. В лаборатории есть семь пластин толщиной 32, 3, 37, 8, 2, 17, 1 сантиметров.

В сумме они дают ровно 100 сантиметров. Сотрудники планируют провести эксперимент с новым видом излучения, проникающая способность которого неизвестна, то есть им необходимо собрать из имеющихся пластин экран некоторой толщины от 1 до 100 сантиметров. Определите все возможные значения проникающей способности излучения, для которых не удастся собрать защитный экран нужной толщины, используя имеющиеся в лаборатории пластины. Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. В ответе укажите несколько чисел (единицу измерения указывать не нужно), добавляя поля ввода по мере необходимости.

Задача 2. Гоночная трасса

Гоночная трасса имеет форму, изображённую на рисунке. Гоночный автомобиль выезжает из левого верхнего угла трассы и за первую минуту перемещается на 1 клетку вправо. Далее за каждую последующую минуту автомобиль перемещается на целое число клеток по прямой в одном направлении. Каждую минуту автомобиль может изменять скорость не более чем на 1, то есть за каждую минуту автомобиль проезжает столько же клеток, сколько за предыдущую минуту, или на одну клетку больше или на одну клетку меньше. Поскольку каждое перемещение выполняется по прямой, в тех клетках, в которых происходит поворот трассы, должно закончиться очередное перемещение автомобиля.

Постройте алгоритм прохождения автомобилем трассы за минимальное время. Автомобилю необходимо завершить свой маршрут также в левом верхнем углу трассы, при этом последнее перемещение требуется осуществить на 1 клетку, чтобы автомобиль остановился в конечной клетке трассы. В ответе запишите последовательность чисел, соответствующую перемещению автомобиля каждую минуту. Каждые два соседних числа в последовательности должны отличаться не более, чем на 1, первое и последнее число должны быть равны 1.

Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. Чем меньше чисел будет в вашем ответе, тем больше баллов вы получите (при условии, что последовательность перемещений будет удовлетворять всем необходимым условиям). Например, если трасса имела бы такой вид, как на рисунке справа, то в ответе необходимо записать числа 1, 2, 2, 2, 1, 1, 1. На рисунке эти числа записаны в конечных клетках соответствующего перемещения.

Задача 3. Бег по пересечённой местности

Участникам соревнования по бегу по пересечённой местности необходимо преодолеть маршрут из левого верхнего угла в правый нижний угол участка, состоящего из 8×8 клеток. Участник может перемещаться из клетки в одну из четырёх клеток, имеющих общую сторону с клеткой, где он находится в данный момент, не выходя при этом за границу квадрата. На рисунке изображён вид участка и один из возможных маршрутов бегуна.

Участники всегда выбирают кратчайший маршрут. Организаторы соревнований хотят удлинить маршрут спортсменов, для этого они планируют перекрыть некоторые клетки препятствиями, чтобы они стали недоступны для участников. Организаторы хотят разместить препятствия так, чтобы кратчайший маршрут от старта до финиша стал как можно длиннее. Также они хотят использовать минимально возможное число препятствий. В ответе запишите 8 строк по 8 символов «.» и «#», где символ «.» означает пустую клетку, а символ «#» — клетку с препятствием.

Левый верхний и правый нижний углы вашего ответа должны быть свободными, также должен существовать маршрут из левого верхнего в правый нижний угол. Чем длиннее будет кратчайший путь от старта до финиша в вашем ответе, тем больше баллов вы получите. При одинаковой длине кратчайшего пути больше баллов получит ответ, содержащий меньшее число препятствий. При этом, независимо от количества препятствий, решение с большей длиной пути получит больше баллов, чем с меньшей.

Задача 4. Конференция

Для выступления на очень важной конференции подали заявки 1000 докладчиков. Каждый из них готов сделать доклад строго в указанное время, но одновременно может выступать только один докладчик, поэтому удовлетворить все заявки невозможно. Выберите наибольшее число докладчиков так, чтобы указанные ими времена выступления не пересекались. В один момент времени может завершиться один доклад и начаться другой.

Данные для выполнения этого задания находятся в файле электронной таблицы. Вы можете скачать файл в одном из двух форматов: Microsoft Excel (XLSX) или LibreOffice Calc (ODS). Файл содержит три колонки. В колонке A указан номер докладчика от 1 до 1000, в колонках B и C указаны желаемые времена начала и окончания доклада в формате времени электронной таблицы. Количество секунд во всех временах равно нулю. В ответ запишите номера докладчиков (числа от 1 до 1000), которых вы выберете для выступления на конференции.

Каждое число записывайте в отдельное поле ввода, добавляя поля по мере необходимости. Времена выступлений выбранных докладчиков не должны пересекаться. Чем больше докладов вы выберете, тем больше баллов получите (при условии, что предложенный вами набор докладчиков удовлетворяет условию задачи). Для выполнения задания вы можете использовать электронные таблицы из офисного пакета или любые другие средства вашего компьютера.

Задача 5. Пара-тройка конфет

Ограничение по времени: 1 секунда У Алисы сегодня день рождения, и она хочет угостить своих одноклассников конфетами. В магазине, в который она успеет зайти перед школой, есть сладости двух видов: шоколадные и карамельные. Они продаются наборами по 3 штуки, причем в упаковке есть конфеты каждого из двух видов (то есть в одной упаковке лежат две конфеты одного вида и одна конфета другого вида).

По внешнему виду упаковки нельзя понять, какие конфеты лежат внутри. Чтобы никого не обидеть, всем в классе нужно раздать конфеты одного вида, а оставшиеся девочка заберёт домой. Алисе нужно собираться в школу, поэтому она попросила вас посчитать, какое минимальное число упаковок нужно купить, чтобы конфет хватило на всех. Формат входных данных В единственной строке задано число n (1 6 n 6 109 ) — количество человек в классе. Формат выходных данных Выведите единственное число — количество упаковок, которое должна купить Алиса. Система оценки Решения, правильно работающие при n 6 103 , будут оцениваться в 25 баллов. Решения, правильно работающие при n 6 106 , будут оцениваться в 50 баллов.

Замечание В первом примере Алиса купит две упаковки с конфетами. В первой упаковке лежат 2 конфеты одного вида, и 1 конфета другого вида. Если вторая упаковка будет такая же, как и первая, то у Алисы окажется 4 конфеты одного вида и 2 конфеты другого вида. Если вторая упаковка будет отличаться от первой, то у Алисы будет по 3 конфеты каждого вида. В любом случае у Алисы найдётся 3 конфеты одного вида. Как видно из первого примера, для того, чтобы гарантированно получить 4 конфеты одного вида, недостаточно купить две упаковки.

Задача 6. Речной бой

Ограничение по времени: 1 секунда Поле в игре «Речной бой» представляет собой полоску длины n клеток и шириной в одну клетку. Где-то на поле расположен корабль из k клеток (k 6 n). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: «мимо», «ранен» или «убит». Формат входных данных Первая строка входных данных содержит целое число n (1 6 n 6 109 ). Вторая строка входных данных содержит целое число k (1 6 k 6 n). Формат выходных данных Выведите одно целое число — количество выстрелов. Система оценки Решения, правильно работающие при n 6 10, будут оцениваться в 40 баллов.

Замечание В первом примере поле состоит из n = 4 клеток, корабль имеет длину k = 2. Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет «ранен», то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет «мимо», то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

Задача 7. Сломанный индикатор

Ограничение по времени: 1 секунда У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от 0 до 9 в виде цифр «почтового индекса» (см. рисунок): После неудачного эксперимента индикатор повредился, и часть сегментов могла перегореть. Когда сегмент перегорает, индикатор теряет возможность показывать цифры, использующие этот сегмент. Алексей уже выяснил, что индикатор всё ещё способен показать какие-то n цифр.

Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе. Формат входных данных Первая строка входных данных содержит число n (1 6 n 6 10) — количество цифр, которые смог показать на индикаторе Алексей. Следующие n строк содержат по одной цифре ai (0 6 ai 6 9) — сами цифры, которые Алексей смог показать. Гарантируется, что все ai различны. Формат выходных данных Выведите элементы искомого множества в порядке возрастания, каждую цифру в отдельной строке. Система оценки Решения, правильно работающие при 2 6 ai 6 4, будут оцениваться в 28 баллов.

Задания для 9-11 классов

Задача 1. Пара-тройка конфет Ограничение по времени: 1 секунда У Алисы сегодня день рождения, и она хочет угостить своих одноклассников конфетами. В магазине, в который она успеет зайти перед школой, есть сладости двух видов: шоколадные и карамельные. Они продаются наборами по 3 штуки, причем в упаковке есть конфеты каждого из двух видов (то есть в одной упаковке лежат две конфеты одного вида и одна конфета другого вида).

По внешнему виду упаковки нельзя понять, какие конфеты лежат внутри. Чтобы никого не обидеть, всем в классе нужно раздать конфеты одного вида, а оставшиеся девочка заберёт домой. Алисе нужно собираться в школу, поэтому она попросила вас посчитать, какое минимальное число упаковок нужно купить, чтобы конфет хватило на всех. Формат входных данных

В единственной строке задано число n (1 6 n 6 109 ) — количество человек в классе. Формат выходных данных Выведите единственное число — количество упаковок, которое должна купить Алиса. Система оценки Решения, правильно работающие при n 6 103 , будут оцениваться в 25 баллов. Решения, правильно работающие при n 6 106 , будут оцениваться в 50 баллов.

Замечание В первом примере Алиса купит две упаковки с конфетами. В первой упаковке лежат 2 конфеты одного вида, и 1 конфета другого вида. Если вторая упаковка будет такая же, как и первая, то у Алисы окажется 4 конфеты одного вида и 2 конфеты другого вида. Если вторая упаковка будет отличаться от первой, то у Алисы будет по 3 конфеты каждого вида. В любом случае у Алисы найдётся 3 конфеты одного вида. Как видно из первого примера, для того, чтобы гарантированно получить 4 конфеты одного вида, недостаточно купить две упаковки.

Задача 2. Речной бой Ограничение по времени: 1 секунда Поле в игре «Речной бой» представляет собой полоску длины n клеток и шириной в одну клетку. Где-то на поле расположен корабль из k клеток (k 6 n). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: «мимо», «ранен» или «убит». Формат входных данных Первая строка входных данных содержит целое число n (1 6 n 6 109 ). Вторая строка входных данных содержит целое число k (1 6 k 6 n). Формат выходных данных Выведите одно целое число — количество выстрелов. Система оценки Решения, правильно работающие при n 6 10, будут оцениваться в 40 баллов.

Замечание В первом примере поле состоит из n = 4 клеток, корабль имеет длину k = 2. Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет «ранен», то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет «мимо», то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

Задача 3. Красивый шарф

Ограничение по времени: 1 секунда Алиса решила поздравить своего друга с началом нового учебного года. Впереди холодная осень, поэтому она решила связать для него собственными руками шарф. Незаметно для друга Алиса узнала, что ему большего всего нравятся k различных цветов. Алиса приняла решение связать шарф размером n × m, в котором будут чередоваться полоски различных цветов.

Её друг никогда не ищет легких путей, поэтому она решила, что шарф с горизонтальными или вертикальными полосками покажется ему слишком «примитивным». Алиса решила, что полоски определённо должны быть диагональными! Закончив вязать шарф, Алиса вспомнила, что один из k цветов её друг считает особенным! Это цвет c, который по его мнению приносит школьникам удачу на олимпиадах по информатике. И Алисе стало невероятно интересно, сколько фрагментов шарфа имеют именно такой цвет. Шарф получился очень большим, Алиса очень устала, пока его вязала, поэтому сама она уже не может ответить на этот вопрос и просит вас о помощи… Более формально шарф можно представить в виде таблицы размером n × m, каждая клетка которой покрашена в один из k цветов. Цвета нумеруются от 1 до k.

Первая строка таблицы покрашена в цвета 1, 2, …, k, 1, 2, …, k и т.д. Каждая следующая строка получена из предыдущей сдвигом влево на одну клетку. Таким образом, таблица состоит из диагональных полос. При n = 4, m = 8 и k = 3 таблица будет иметь следующий вид: По данным числам n, m, k и c определите, сколько всего клеток покрашено в цвет c. Формат входных данных Первая строка входных данных содержит натуральное число n — ширину шарфа. Вторая строка входных данных содержит натуральное число m — длину шарфа.

Третья строка входных данных содержит натуральное число k — количество любимых цветов друга Алисы. Числа n, m и k не превосходят 109 . Четвёртая строка входных данных содержит натуральное число c — номер особенного цвета (1 6 c 6 k). Формат выходных данных Программа должна вывести одно целое число — количество клеток шарфа, которые покрашены в цвет c. Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Система оценки Решения, правильно работающие, когда число n не превосходит 10, будут оцениваться в 16 баллов. Решения, правильно работающие, когда одно из чисел n или m делится нацело на k, будут оцениваться в 16 баллов. Решения, правильно работающие, когда числа n и m не превосходят 800, будут оцениваться в 40 баллов. Решения, правильно работающие, когда число k не превосходит 900, будут оцениваться в 56 баллов. Решения, правильно работающие, когда числа n и m не превосходят 105 , будут оцениваться в 60 баллов. Решения, правильно работающие, когда число k не превосходит 105 , будут оцениваться в 84 балла.

Задача 4. Гостиница для жирафов

Ограничение по времени: 1 секунда В гостинице для жирафов администрация хочет запастись подушкам так, чтобы удовлетворить потребности любого своего возможного постояльца. Известно, что жирафам в зависимости от длины их шеи нужно сложить стопку подушек (в стопке одна или несколько подушек) толщиной от 1 до n сантиметров. При этом администрация хочет обойтись как можно меньшим числом подушек, а среди наборов подушек, удовлетворяющих этим требованиям, администрация выберет набор минимальной суммарной толщины, чтобы он занимал минимальный объём в шкафу.

Помогите администрации составить нужный набор подушек, позволяющий получить стопку любой высоты от 1 до n сантиметров включительно. Формат входных данных Во входных данных записано единственное целое число n — максимально возможная длина шеи жирафа (1 6 n 6 109 ). Формат выходных данных В единственной строке через пробел выведите толщину каждой подушки в этом наборе в произвольном порядке. Если ответов несколько, выведите любой из них. Система оценки Решения, правильно работающие при n 6 20, будут оцениваться в 20 баллов. Решения, правильно работающие при n 6 1000, будут оцениваться в 40 баллов.

Замечание В примере из условия необходимо подобрать такой набор из минимального числа подушек, чтобы используя данные подушки удавалось сложить стопку любой целочисленной толщины от 1 до 9 см. Таким набором является набор из подушек толщиной 1, 2, 3, 3 см. Действительно, стопку толщины 1, 2, 3 см можно сложить из одной подушки. Оставшиеся числа получены так: 4 = 1 + 3, 5 = 2 + 3, 6 = 3 + 3, 7 = 1 + 3 + 3, 8 = 2 + 3 + 3, 9 = 1 + 2 + 3 + 3. Возможны и другие варианты ответа с тем же количеством подушек и их суммарной толщиной. Выполнить условие задачи, используя только три подушки, нельзя.

Задача 5. Сломанный индикатор

Ограничение по времени: 1 секунда У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от 0 до 9 в виде цифр «почтового индекса» (см. рисунок). После неудачного эксперимента индикатор повредился, и часть сегментов могла перегореть. Когда сегмент перегорает, индикатор теряет возможность показывать цифры, использующие этот сегмент. Алексей уже выяснил, что индикатор всё ещё способен показать какие-то n цифр.

Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе. Формат входных данных Первая строка входных данных содержит число n (1 6 n 6 10) — количество цифр, которые смог показать на индикаторе Алексей. Следующие n строк содержат по одной цифре ai (0 6 ai 6 9) — сами цифры, которые Алексей смог показать. Гарантируется, что все ai различны. Формат выходных данных Выведите элементы искомого множества в порядке возрастания, каждую цифру в отдельной строке. Система оценки Решения, правильно работающие при 2 6 ai 6 4, будут оцениваться в 28 баллов.

ПОДЕЛИТЬСЯ МАТЕРИАЛОМ