[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион

Официальные задания и ответы школьного этапа 2023-2024 всероссийской олимпиады школьников ВСОШ по Информатике 7-8 класс для Москвы 77 регион.

[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион
Приобрести полные задания и ответы

Задание 1:
Защитный экран

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

Задание 2:
Гоночная трасса

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

[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион

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

[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион

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

[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион

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

[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион

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

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

Задания по программированию

Задание 1:
Пара‑тройка конфет

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

Формат входных данных

В единственной строке задано число n (1≤n≤109) —— количество человек в классе.

Формат выходных данных

Выведите единственное число —— количество упаковок, которое должна купить Алиса.

Система оценки

Решения, правильно работающие при n≤103, будут оцениваться в 25 баллов. Решения, правильно работающие при n≤106, будут оцениваться в 50 баллов.

Замечание

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

Задание 2:
Речной бой

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Поле в игре «Речной бой» представляет собой полоску длины n клеток и шириной в одну клетку. Где‑то на поле расположен корабль из k клеток (k≤n). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: «мимо», «ранен» или «убит».

Формат входных данных

Первая строка входных данных содержит целое число n (1≤n≤109). Вторая строка входных данных содержит целое число k (1≤k≤n).

Формат выходных данных

Выведите одно целое число —— количество выстрелов.

Система оценки

Решения, правильно работающие при n≤10, будут оцениваться в 40 баллов.

Замечание

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

Задание 3:
Сломанный индикатор

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

[24-26.10.2023] Школьный этап по Информатике 7-8 класс 2023-2024 г. Москва 77 регион

После неудачного эксперимента индикатор повредился, и часть сегментов могла перегореть. Когда сегмент перегорает, индикатор теряет возможность показывать цифры, использующие этот сегмент.
Алексей уже выяснил, что индикатор всё ещё способен показать какие‑то n цифр. Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе.

Формат входных данных

Первая строка входных данных содержит число n (1≤n≤10) —— количество цифр, которые смог показать на индикаторе Алексей.
Следующие n строк содержат по одной цифре ai (0≤ai≤9) —— сами цифры, которые Алексей смог показать. Гарантируется, что все ai различны.

Формат выходных данных

Выведите элементы искомого множества в порядке возрастания, каждую цифру в отдельной строке.

Система оценки

Решения, правильно работающие при 2≤ai≤4, будут оцениваться в 28 баллов.