Автор Олимпиада по информатике 9, 10, 11 класс ответы и задания для заключительного (финального) этапа 2023-2024 учебный год всероссийской олимпиады школьников ВСОШ. Вам предстоит выполнить задания и ответить на вопросы. Решением задачи является программа, написанная на одном из доступных языков программирования. Для проверки и оценивания решений жюри использует автоматическую тестирующую систему.
→ Задания олимпиады: скачать
→ Критерии и ответы: скачать
Задания олимпиады по информатике
informatika-olymp-2024-zadanie-9-10-11Критерии оценивания
roi-2024-tutorialЗадача 1. Беспилотная аэрологистика
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт На всероссийской олимпиаде по информатике 2224 года, которая проходит в Иннополисе, доставкой занимаются роботы нового поколения, которые способны создавать своих клонов. Доставку можно получить прямо через окно, не выходя из дома. Изначально есть только один робот-доставщик. В любой момент верхний робот может создать одного или нескольких новых роботов прямо над собой. Так образуется колонна роботов. Высота каждого робота равна высоте одного этажа.
В процессе доставки колонна одинаковых роботов-клонов перемещается вдоль корпусов общежития слева направо. В базе данных у роботов содержится список сделанных заказов, для каждого из которых известно окно, в которое его нужно доставить. Когда колонна роботов проходит мимо окна, соответствующего какому-то заказу, она может произвести доставку, если в колонне есть робот, расположенный на уровне окна. Во время перемещения конструкция из роботов может натолкнуться на препятствие. После препятствия движение продолжают только те экземпляры роботов, которые находились выше препятствия. Они оказываются на земле непосредственно за препятствием, по прежнему в виде вертикальной колонны, и могут продолжать движение, создавать новых клонов и доставлять заказы.
Расстояние между препятствиями и окнами достаточно большое, поэтому во время переезда через препятствие роботы не будут проезжать мимо окна. За доставку одного заказа компания-организатор доставки получает p крипторублей. Стоимость создания одного нового робота равна c крипторублей. Итоговая прибыль равна суммарному доходу от доставки заказов за вычетом суммарной стоимости создания всех роботов. Компания хочет максимизировать свою прибыль. При этом, она не обязана выполнить все заказы, а роботы могут в любой момент остановиться, и прекратить процесс доставки. Определите максимальную прибыль, которую может получить компания.
Формат входных данных
В первой строке входных данных находятся четыре целых числа n, m, c, p (0 6 n, m 6 100 000, 1 6 c, p 6 106 ) — количество препятствий, количество заказов в базе, стоимость создания клона робота и стоимость доставки одного заказа, соответственно. В следующих n + m строках идёт описание препятствий и окон, в которые нужно доставить заказы, в порядке следования колонны роботов вдоль общежитий слева направо. Каждая строка содержит два целых числа ti и hi (1 6 ti 6 2, 1 6 hi 6 106 ) — тип объекта ti (1 для препятствия и 2 для окна) и hi — высота препятствия в этажах или этаж, на котором находится окно. Гарантируется, что ровно n объектов имеют тип 1, и оставшиеся m объектов имеют тип 2.
Задача 2. 2026
Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт Новая татарская игра «2026» ведется на прямоугольной клетчатой доске, состоящей из m строк и n столбцов. Доска разбита на m × n единичных клеток размером 1 × 1. На некоторых клетках стоят квадратные фишки размером 1 × 1, на каждой фишке написана одна из 26 английских букв. С фишками производятся q операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой s длины q, состоящей из символов, соответствующих направлениям: «L» — влево, «R» — вправо, «U» — вверх и «D» — вниз. Операция выполняется следующим образом: пока на доске есть хотя бы одна фишка, для которой соседняя с ней в заданном направлении клетка является свободной, эта фишка передвигается на эту соседнюю клетку. Определите, как будет выглядеть доска после выполнения всех операций.
Формат входных данных
Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число t — количество наборов входных данных в тесте (1 6 t 6 200 000). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом: В первой строке набора заданы целые числа m и n — размеры доски (1 6 m, n 6 106 , 1 6 m × n 6 106 ). В следующих m строках задано изначальное расположение фишек на доске. В i-й строке (1 6 i 6 m) находится строка ai1ai2 . . . ain длины n, задающая i-ю строку доски. Каждый символ aij является либо строчной буквой английского алфавита от «a» до «z», либо точкой «.». Если aij = «.», то клетка в i-й строке и j-м столбце является пустой, иначе в ней находится фишка, на которой написана буква aij . В последней строке заданы q символов s1s2 . . . sq без пробелов, задающие последовательность операций (1 6 q 6 106 ). Каждый символ si является одним из символов «L», «R», «U» или «D». Сумма значений m × n по всем наборам входных данных не превышает 2 · 106 . Сумма значений q по всем наборам входных данных не превышает 2 · 106 .
Формат выходных данных
Для каждого набора входных данных выведите итоговое расположение фишек на доске после выполнения всех операций в том же формате, что и во входных данных.
Задача 3. Кейс на рейс
Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт Авиакомпания «Флагманский Флот Татарстана» предлагает в своих самолётах новый вид бизнескласса. Салон самолёта состоит из n мест, расположенных в один ряд вдоль прохода. Введём координатную прямую вдоль салона так, что расстояние между креслами будет равно 1, и места будут иметь координаты от 1 до n. Во время полёта стюарду нужно пройти по самолету и раздать всем пассажирам напитки. Напитки бывают k разных видов, пронумерованных числами от 1 до k. Каждый пассажир получает одну порцию одного напитка, пассажир заказывает предпочитаемый вид напитков при бронировании билета, поэтому все предпочтения пассажиров известны заранее.
Напитки разлиты по бутылкам, каждая бутылка вмещает p порций одного напитка. В тележку для напитков можно загрузить не более m бутылок с любыми видами напитков, гарантируется, что m > k. Пассажиры обслуживаются в порядке возрастания номеров их мест. Первоначально тележка находится в начале салона в точке 0, и её можно заполнить любыми видами напитков перед обслуживанием. После завершения обслуживания тележка должна приехать в точку n + 1. При этом в точках 0 и n + 1 могут находиться кладовые: или одна кладовая в одном из концов салона или две кладовые в двух концах, в которых имеется достаточный запас напитков каждого вида. В этих кладовых можно выгрузить из тележки пустые бутылки и погрузить полные бутылки.
По ходу обслуживания напитки будут расходоваться, поэтому время от времени возникает необходимость пополнить запас напитков на тележке в одной из кладовых. Если в текущий момент тележка находится напротив кресла номер i, то для того, чтобы доехать до кладовой в точке 0 необходимо проехать расстояние i, а для того, чтобы доехать до кладовой в точке n + 1 необходимо проехать расстояние n + 1 − i. В кладовых можно выгрузить пустые бутылки из тележки и загрузить на свободные места бутылки с напитками любых видов. Выгружаемые бутылки должны быть пустыми, нельзя выгружать бутылки, в которых остались напитки, или выливать напитки. Нельзя переливать остатки напитков между разными бутылками. Можно загружать на тележку более одной бутылки одного вида. После этого тележка должна проехать расстояние от кладовой до кресла первого необслуженного пассажира, чтобы продолжить обслуживание. Определите, какое минимальное расстояние должна проехать тележка, чтобы переместиться из точки 0 в точку n + 1 и обслужить всех пассажиров.
Формат входных данных
Первая строка входных данных содержит четыре целых числа n, m, k, p (3 6 n 6 106 , 1 6 p 6 106 , 1 6 k 6 m 6 106 ) — количество мест в салоне, вместимость тележки, количество типов напитков и вместимость каждой бутылки соответственно. В следующей строке содержится целое число c (1 6 c 6 3) — параметр, описывающий наличие кладовых в салоне. Если c = 1, то кладовая находится только в точке n+ 1. Если c = 2, то кладовая находится только в точке 0. Если c = 3, то кладовые находятся в обоих концах салона. В следующей строке содержатся n целых чисел ai (1 6 ai 6 k) — типы напитков, которые заказали пассажиры.
Формат выходных данных
Программа должна вывести одно целое число — минимальное расстояние, которое должна проехать тележка.
Задача 4. Рамазан и капуста
Ограничение по времени: 4 секунды Ограничение по памяти: 1024 мегабайта. Рамазан решил заняться серьезным бизнесом — выращиванием капусты. Поле для выращивания капусты представляет собой бесконечное клетчатое поле. В каждой клетке поля может быть посажен один кочан капусты. Рамазан засадил только часть поля. Он запланировал использовать несколько прямоугольных участков поля, причём оказалось, что некоторые из них могут пересекаться.
Клетка поля принадлежит посадкам, если она лежит хотя бы в одном из прямоугольников. Формально, Рамазан выбрал n прямоугольных участков (x L i , yL i , xR i , yR i ) (x L i 6 x R i , y L i 6 y R i , 1 6 i 6 n). Клетка (x, y) содержит капусту, если существует хотя бы один выбранный прямоугольник i (1 6 i 6 n), такой что x L i 6 x 6 x R i и y L i 6 y 6 y R i . В прошлом Рамазан был программистом (и победителем), поэтому он решил использовать роботов с искусственным интеллектом для периодической обработки посадок. Один робот может обслуживать произвольный горизонтальный участок клеток (x robot 1 , xrobot 2 , yrobot), то есть все клетки (x, y), такие что x robot 1 6 x 6 x robot 2 и y = y robot .
Задача 5. Восстание газонокосилок
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Газоны в Иннополисе косят электрические роботы-газонокосилки. Будем считать, что газон представляет собой отрезок числовой прямой, на котором в некоторых точках расположены роботыгазонокосилки. Размером роботов можно пренебречь. Один из роботов стоит в начале газона (левее него газона нет), и один — в конце (правее него газона нет). Каждый робот изначально ориентирован в одном из двух направлений: либо направо, либо налево. Заряда i-го робота хватает для обработки pi метров газона. После ночной зарядки все роботы начинают работать одновременно и движутся с одинаковой скоростью. Каждый робот движется в своём направлении вдоль прямой.
Робот останавливается в одном из трёх случаев: 1. Если у робота закончился заряд. Иными словами, если i-й робот проехал pi метров от точки старта. 2. Если робот доехал до начала или конца газона. 3. Если робот встретился в одной точке с другим роботом, который двигался ему навстречу или остановился в этой точке ранее. Перед запуском роботов вы можете поменять направление некоторых из них на противоположное. Требуется скосить траву на всём газоне. Определите, у какого минимального количества роботов нужно поменять направление, чтобы в итоге вся трава на газоне оказалась скошена. Иначе сообщите, что всю траву скосить невозможно.
Формат входных данных
В первой строке содержится целое число n (2 6 n 6 105 ) — количество роботов. В следующих n строках содержатся описания роботов в порядке их расположения на прямой слева направо. Каждый робот характеризуется тремя целыми числами xi , pi , di : начальной позицией робота, количеством метров, которые он может проехать, и направлением движения (0 = x1 < x2 < . . . < xn 6 109 , 1 6 pi 6 109 , значение di = −1 обозначает движение налево, в направлении уменьшения координаты, di = 1 обозначает движение направо, в направлении увеличения координаты). Начало и конец газона находятся в точках x1 = 0 и xn соответственно.
Формат выходных данных
В единственной строке необходимо вывести −1, если скосить всю траву на газоне невозможно. Иначе, нужно вывести одно число — количество роботов, у которых нужно изменить направление на противоположное, чтобы газон был скошен.
Задача 6. Интерактивные переходы
Ограничение по времени: 1 секунда Ограничение по памяти: 512 мегабайт Кампус Иннополиса состоит из n корпусов, соединённых m переходами. Каждый переход соединяет два различных корпуса, никакие два корпуса не соединены более чем одним переходом. Известно, что каждый корпус имеет подсветку, которая может быть включена или выключена. Изначально подсветка всех корпусов выключена. Диспетчер кампуса может за одно действие включить или выключить подсветку любого корпуса. Диспетчер может также нажимать кнопку включения подсветки, если она уже включена, или нажимать кнопку выключения, если она выключена.
Данные действия не приводят к изменению состояния подсветки корпуса. Аналогично, каждый переход имеет подсветку, которая может быть включена или выключена. Исходно подсветка всех переходов выключена. Однако в отличие от подсветки корпусов, подсветка переходов изменяется автоматически: если после очередного действия диспетчера состояние подсветки соединённых переходом корпусов оказывается одинаковым, то подсветка перехода также переходит в это состояние, а иначе она не меняется. Другими словами, если после очередного действия диспетчера подсветка обоих корпусов, соединённых переходом, оказывается выключена, то подсветка перехода также выключается.
Если подсветка обоих корпусов, соединённых переходом, оказывается включена, то подсветка перехода также включается. Если подсветка одного из корпусов оказывается включена, а другого — выключена, то состояние подсветки перехода не меняется. Перед приездом участников олимпиады по информатике директор кампуса для каждого корпуса и каждого перехода определил, должен ли этот корпус или переход быть подсвечен. Проверьте, может ли диспетчер выполнить пожелание директора, выполнив произвольное число действий. Если это возможно, то найдите любую такую последовательность действий. Решения, корректно определяющие возможность получить желаемое состояние подсветки, но не предъявляющие искомую последовательность действий, будут получать частичные баллы.
Формат входных данных
Каждый тест содержит один или несколько наборов входных данных. В первой строке теста задано целое число t — количество наборов входных данных в тесте (1 6 t 6 50 000). Далее следуют описания наборов. Каждый набор описывается следующим образом. В первой строке заданы целые числа: n — количество корпусов, и m — количество переходов (1 6 n 6 105 , 0 6 m 6 2 · 105 ). В следующих m строках следуют описания переходов. В i-й строке находятся целые числа ai , bi , ci — номера корпусов, соединённых i-м переходом, и требуемое состояние подсветки i-го перехода, соответственно (1 6 ai , bi 6 n, ai 6= bi , 0 6 ci 6 1). Если ci = 0, то подсветка i-го перехода в результате должна быть выключена, а если ci = 1, то включена. В последней строке заданы n целых чисел d1, d2, . . . , dn — требуемое состояние подсветки корпусов (0 6 di 6 1). Если dv = 0, подсветка корпуса v в итоге должна быть выключена, а если dv = 1, то включена. Сумма значений n по всем наборам входных данных не превышает 105 . Сумма значений m по всем наборам входных данных не превышает 2 · 105 .
Задача 7. Гонка дронов
Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт В Иннополисе проводятся гонки дронов. В гонке могут принять участие n дронов, i-й дрон пролетает единицу расстояния за ti секунд. Гонка проводится на прямой, на которой расположены m ворот, пронумерованных от 1 до m, i-е ворота находятся на расстоянии si от стартовой позиции гонки. В гонке примут участие первые k дронов с номерами от 1 до k. Величину k судьи объявляют непосредственно перед гонкой, поэтому вам необходимо проанализировать гонку для всех k от 1 до n.
Гонка проводится следующим образом. Дроны начинают движение из точки 0 в сторону ворот, каждый со своей скоростью. У каждого дрона есть точка восстановления — последние ворота, в которых он выполнял сохранение позиции. Изначально точка восстановления каждого дрона — точка 0. Дроны каждый раз начинают двигаться из своих точек восстановления и продолжают движение, пока один или несколько дронов не оказываются в точке, где расположены ворота (возможно, различные для разных дронов). В этот момент среди всех дронов, которые оказались в каких-либо воротах, выбирается дрон с наименьшим номером. Для этого дрона производится сохранение позиции, его точка восстановления переносится в его текущую позицию.
Остальные дроны мгновенно телепортируются в свои точки восстановления. После этого гонка продолжается таким же образом. Как только дрон сохраняет позицию в последних воротах с номером m, он финиширует. Не финишировавшие пока дроны, как обычно, телепортируются в свои точки восстановления и продолжают гонку. Когда все дроны финишируют, гонка завершается. Телепортация — очень энергоемкий процесс. Для подготовки к гонке необходимо понять, сколько суммарно телепортаций совершат все дроны до её завершения. Обозначим как ck суммарное число телепортаций, которое совершат все дроны, если в гонке будут участвовать первые k дронов. Найдите значения c1, c2, . . . , cn.
Другие олимпиады школьников по информатике:
24-26 октября 2023 Олимпиада по информатике 5-11 класс ответы и задания школьного этапа ВСОШ