Победители олимпиады «Технокубок» от Mail.ru Group, Физтеха и Бауманки смогут поступить в российские университеты без экзаменов. Задачи будут рассчитаны на учащихся 8-11 классов, которые готовятся к поступлению в вузы. Отборочный этап олимпиады начнется 17 октября.
Регистрация на олимпиаду «Технокубок» доступна по ссылке.
Отборочные раунды пройдут 17 октября, 14 ноября и 12 декабря 2021 года – участвовать можно в каждом раунде. Они пройдут дистанционно на мировой платформе для спортивного программирования Codeforces. Принять участие могут школьники из любого уголка России и стран СНГ.
Задачи рассчитаны на учащихся 8-11 классов, которые готовятся к поступлению в вузы. Результаты олимпиады будут действовать в течение четырех лет.
«Победители и призеры не только получат льготы при поступлении, но и смогут познакомиться со специалистами нашей компании, а также узнать про возможности карьерного роста в ИТ для абитуриентов», – отметил технический руководитель образовательных проектов Mail.ru Group Дмитрий Санников.
Финал олимпиады состоится в марте 2022 года.
29 ноября начинается отборочный этап на международную олимпиаду по программированию для школьников 8-11 классов. Участвовать могут ребята из любого региона России и стран СНГ. Соревнования пройдут в онлайн-формате, необходима регистрация.
Олимпиада «Технокубок» состоит из двух этапов: отборочного и финального. В отборочном этапе школьникам предлагают решить задания по программированию дистанционно. Всего есть три раунда, участвовать можно в любом из них. По итогам каждого раунда формируются списки, лучших участников приглашают в финал.
Можно выбрать часовой пояс и решать задания в комфортное время. Организаторы проследят за процессом с помощью специально разработанной системы прокторинга. Специалисты будут записывать экран и участника на видео, чтобы избежать случаев нечестного прохождения олимпиады.
«Технокубок» является олимпиадой первого уровня и позволяет победителем автоматически получить 100 баллов за ЕГЭ по информатике или поступить в профильный вуз без экзаменов. Также победители получат привилегии при поступлении на образовательные программы Mail.ru Group. Диплом олимпиады действителен четыре года с момента прохождения.
Финал пройдёт в смешанном формате: офлайн и онлайн весной 2021 года.
Фото на обложке: Unsplash
В этом 2021-2022 учебном году олимпиада технокубок по программированию вошла в проект перечня олимпиад школьников и имеет первый уровень.
Расписание олимпиады технокубок 2021-2022
Олимпиада Технокубок проводится в два этапа: отборочный (отборочные раунды) и финальный (финальный раунд). Отборочный этап проводится дистанционно. Перед каждым отборочным раундом проходит двухдневный ознакомительный раунд, в котором можно потренироваться и проверить свои силы.
Решение ознакомительных задач не влияет на результат Олимпиады. Участвовать можно в любом отборочном раунде. После каждого отборочного раунда приглашается N участников (значение зависит от суммарного количества участников в раунде), ставших победителями и призерами отборочного этапа. В финал приглашаются участники, прошедшие отборочный этап.
В зависимости от эпидемиологической обстановки, финальный этап Олимпиады может пройти очно или заочно с применением дистанционных технологий, включая технологию прокторинга. О формате проведения финального этапа будет сообщено позднее на сайте чемпионата.
Что даст олимпиада технокубок
Технокубок» — ежегодная олимпиада по программированию для учащихся 8 –11 классов. Организаторами являются Московский физико-технический институт (государственный университет), Московский государственный технический университет им. Н.Э. Баумана и компания Mail.ru Group. «Технокубок» проводится с 2015/2016 учебного года.
Олимпиада предоставляет льготы при поступлении в большинство российских вузов, поскольку входит в проект перечня РСОШ и имеет I уровень («Об утверждении перечня олимпиад школьников и их уровней на 2021/22 учебный год»). Победители и призеры олимпиады могут поступить в вуз без экзаменов или получить 100 баллов за ЕГЭ по информатике.
Кроме того, победители получат ценные призы, а также привилегии при поступлении на образовательные проекты Mail.ru Group.
Другие олимпиады для школьников
ВСЕРОССИЙСКИЕ олимпиады 2021-2022 задания и ответы
ПОДЕЛИТЬСЯ МАТЕРИАЛОМ
Время на прочтение
VK, МФТИ и МГТУ им. Н. Э. Баумана открыли регистрацию на участие в олимпиаде по спортивному программированию для школьников 8-11 классов «Технокубок» 2022/2023.
Мероприятие «Технокубок» имеет II уровень в перечне олимпиад Российского совета олимпиад школьников. Это означает, что победители и призёры олимпиады получат льготы для поступления в вузы.
Участникам соревнования даётся три попытки пройти отборочный дистанционный этап на платформе All Cups. Первый отборочный раунд олимпиады состоится 20 ноября. Второй — 11 декабря, Третий — 15 января следующего года.
Школьники могут участвовать в каждом из трёх отборочных раундов до тех пор, пока не попадут в финальные списки. Перед каждым отборочным раундом можно будет проверить себя и потренироваться в двухдневном ознакомительном раунде. По итогам отборочных этапов лучших участников пригласят в финал соревнования, который состоится в марте 2023 года.
«Наши образовательные проекты помогают молодёжи построить карьеру в IT. Вместе с ведущими техническими вузами страны мы проводим «Технокубок» уже восьмой год — и видим, что соревнованием интересуются тысячи школьников. В предыдущем сезоне олимпиады 154 ученика школ стали призёрами и получили привилегии для поступления в университеты. Мы рады создавать для ребят возможности проявить свой талант — и делать образование и карьеру в IT ещё доступнее», – пояснила директор по образовательным проектам VK Анна Степанова.
«Популярность IT продолжает расти среди молодёжи России. По статистике, всё больше школьников участвуют в олимпиадах по информатике и сдают ЕГЭ по этой дисциплине. Олимпиады помогают погрузиться в решение сложных задач, показать всю красоту предмета. МФТИ в сотрудничестве с ведущими ИТ-компаниями, вузами, а также школами страны развивает комплексную систему работы со школьниками. Она включает олимпиады и конкурсы, заочную физико-техническую школу и сезонные олимпиадные школы, программы повышения квалификации для педагогов школ и адресную работу с регионами. На кампусе московского Физтеха сборная России участвовала этим летом в Международной олимпиаде школьников по информатике IOI, а компания VK предложила членам сборной «персональные стажировки», – рассказал директор Центра Развития IT-образования МФТИ Алексей Малеев.
В подготовке к олимпиаде помогут примеры задач из олимпиад «Технокубок» прошлых лет (например, условия финального этапа «Технокубка» 2021/2022):
Дефрагментация памяти
Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).
Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.
Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.
Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.
Решение. Для решения данной задачи нужно сформировать массив, который будет равен памяти компьютера после дефрагментации. Для этого, например, можно запомнить про каждый процесс (в порядке слева направо) количество ячеек, которые он занимает. Верно следующее утверждение: пока дефрагментация не закончена, всегда будет две такие ячейки с номерами pos1 и pos2 в памяти компьютера, что ячейка pos1 пуста, а ячейка pos2 занята процессом, который по окончании дефрагментации должен находиться в ячейке номер pos1. Таким образом, ответ на задачу — это количество таких ячеек в памяти, которые должны быть заняты каким-то процессом после окончания дефрагментации, причём до начала дефрагментации либо эти ячейки пусты, либо в них записаны другие процессы (отличные от тех, которые должны быть записаны после дефрагментации).
Разбор задач отборочных раундов Технокубка
23 и 26 марта онлайн, на платформе IT.Mail.Ru совместно с Codeforces, прошли два отборочных раунда олимпиады по программированию «Технокубок-2016» для учащихся 8–11-х классов. Больше полутора тысяч участников со всей России и СНГ боролись за возможность встретиться на московской площадке. 300 лучших прошли в финал, который состоится 17 апреля в МГТУ им. Н. Э. Баумана и МФТИ.
В апреле им представится возможность вновь проявить себя и побороться за привлекательные призы: iPad mini 2, iPod nano, iPod shuffle. Помимо приземлённых материальных наград, а также непременного почёта и уважения, победители первого Технокубка (диплом I степени) получат целых восемь дополнительных баллов при поступлении на программы бакалавриата и специалитета в МФТИ и МГТУ им. Н. Э. Баумана, а призёры (диплом II и III степени) — шесть дополнительных баллов. Ребята уже сейчас смогут познакомиться с ведущими IT-специалистами, а в дальнейшем, возможно, решат совмещать обучение в одном из лучших технических вузов Москвы с дополнительными образовательными программами Технопарка и Технотрека.
«Технокубок — важная социальная инициатива: благодаря олимпиаде талантливые юные программисты получат дополнительную возможность поступить в ведущие технические вузы страны. Мы планомерно работаем над тем, чтобы дать студентам и школьникам как можно больше возможностей набрать знания и практику, необходимые для работы в крупной компании или для того, чтобы начать разрабатывать собственный проект. На это ориентированы наши образовательные проекты с вузами (Технопарк, Техносфера и Технотрек), наши IT-чемпионаты, а теперь этот список пополнит и Технокубок», — Дмитрий Dmitry21 Волошин, директор департамента исследований и образования Mail.Ru Group.
Для участников этого года и тех, кто хотел бы подготовиться к будущим Технокубкам, представляем разбор задач.
Этажи
Есть n-подъездный дом, в каждом подъезде по m этажей, и на каждом этаже каждого подъезда ровно k квартир. Таким образом, в доме всего n • m • k квартир. Они пронумерованы естественным образом от 1 до n • m • k, то есть первая квартира на первом этаже в первом подъезде имеет номер 1, первая квартира на втором этаже первого подъезда имеет номер k + 1 и так далее. Особенность этого дома состоит в том, что он круглый. То есть если обходить его по часовой стрелке, то после подъезда номер 1 следует подъезд номер 2, затем подъезд номер 3 и так далее до подъезда номер n. После подъезда номер n снова идёт подъезд номер 1.
Эдвард живёт в квартире номер a, а Наташа — в квартире номер b. Переход на один этаж вверх или вниз по лестнице занимает 5 секунд, переход от двери подъезда к двери соседнего подъезда — 15 секунд, а переход в пределах одного этажа одного подъезда происходит мгновенно. Также в каждом подъезде дома есть лифт. Он устроен следующим образом: он всегда приезжает ровно через 10 секунд после вызова, а чтобы переместить пассажира на один этаж вверх или вниз, лифт тратит ровно одну секунду. Посадка и высадка происходят мгновенно.
Помогите Эдварду найти минимальное время, за которое он сможет добраться до квартиры Наташи. Считайте, что Эдвард может выйти из подъезда только с первого этажа соответствующего подъезда (это происходит мгновенно). Если Эдвард стоит перед дверью какого-то подъезда, он может зайти в него и сразу окажется на первом этаже этого подъезда (это также происходит мгновенно). Эдвард может выбирать, в каком направлении идти вокруг дома.
Решение. Для решения данной задачи нужно было аккуратно реализовать то, что написано в условии. Основная сложность заключалась в определении номера подъезда и номера этажа по номеру квартиры. Это можно было сделать следующим образом: если в доме n подъездов, в каждом подъезде по m этажей, а на каждом этаже по k квартир, то квартира с номером a находится в подъезде номер (a – 1) / (m • k) и на этаже номер ((a – 1)%(m • k)) / k, причём эти номера 0-индексированы, что удобно для дальнейших вычислений. После определения номеров подъездов и этажей нужно было рассмотреть два случая: когда номера подъездов Эдварда и Наташи равны (тогда нужно было выбрать, что оптимальнее — доехать на лифте или подняться/спуститься по лестнице) и когда эти номера различны (тут нужно было не забыть, что дом круглый, и выбрать нужное направление).
Печать условий
На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает ai страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.
Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.
Путь Робота
Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой, что:
Ниже изображены несколько примеров допустимых циклов:
Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.
В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:
Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).
Найдите искомую последовательность команд, допускается любое направление обхода цикла.
Решение. Сначала найдём стартовую позицию Робота, сохраним её и присвоим значение стартовой позиции звёздочке. Так как по условию задана ломаная без самопересечений и самокасаний, верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звёздочка, перейдём в соседнюю клетку, значение которой равно звёздочке, и присвоим её значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звёздочкой, значит, мы обошли всю ломаную и нужно закончить работу программы.
Автобус
Вдоль дороги стоят n путешественников. Дорога представляет собой прямую, размерами путешественников можно пренебречь, считая их точками.
Водитель автобуса Василий, благодаря мобильному приложению, знает для каждого путешественника точку xi, в которой тот стоит. Кроме того, он знает расстояние di, которое i-й путешественник хочет проехать на автобусе. Таким образом, i-й путешественник планирует выйти из автобуса в точке xi + di. Теперь Василий хочет выбрать, кого из путешественников он подвезёт, а кого оставит пылиться у дороги.
Василий решил, что сегодня он должен хорошо заработать, поэтому нужно перевезти в точности a путешественников. В автопарке есть автобусы любых видов. Чем больше мест в автобусе, тем дороже стоит его аренда.
Помогите Василию определить минимальное количество пассажирских мест в автобусе, которых будет достаточно для перевозки ровно a путешественников. Ни в какой момент времени в автобусе не может быть путешественников больше, чем количество пассажирских мест в автобусе. Василий сам может решить, какое конкретно подмножество из a путешественников он перевезёт на автобусе.
Решение. Изначально отсортируем всех путешественников по их начальным позициям в неубывающем порядке, а при равенстве позиций — отсортируем по дистанциям, которые путешественникам нужно преодолеть, также в неубывающем порядке. Затем необходимо бинарным поиском подобрать минимальное количество мест в автобусе, которых будет достаточно для перевозки a путешественников.
Целевая функция бинарного поиска должна работать следующим образом. Пусть mid — количество мест в автобусе. Тогда найдём cnt — максимальное количество путешественников, которых мы сможем подвезти на таком автобусе. Это можно сделать с помощью set’a, в котором мы будем хранить позиции выходов путешественников, которые зашли в автобус, и их индексы.
Переберём всех путешественников слева направо (в том порядке, в котором они были отсортированы). Пока в set’е есть путешественники, которые выйдут из автобуса не позднее момента, когда зайдёт текущий путешественник, удалим позиции их выходов из set и добавим их индексы в отдельный вектор ans. В противном случае, если самая дальняя позиция выхода путешественника в set’е больше, чем потенциальная позиция выхода текущего путешественника, заменим в set’е самого дальневыходящего путешественника на текущего.
После того как мы переберём всех путешественников, добавим индексы всех оставшихся в set’е путешественников в ans. Если размер вектора ans меньше a, сдвинем в mid левую границу бинарного поиска, иначе сдвинем в mid правую границу бинарного поиска. После бинарного поиска запустим ещё раз целевую функцию от ответа и выведем индексы путешественников из вектора ans.
Собери число
Решение. Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на k. Действительно, если текущий префикс ответа имеет остаток от деления на k, равный r, то при приписывании к префиксу числа ai этот остаток станет равным остатку от деления на k числа r • 10li + ai (li — количество цифр в записи числа ai).
Тогда, очевидно, нас интересует получать любой остаток от деления такой операцией, используя минимальное количество цифр в записи. Конечно, остаток 0 мы можем получить сразу, используя пустой префикс, поэтому для остатка 0 нас будет интересовать второй по величине ответ.
Всё описанное выше позволяет нам построить граф на k вершинах (от 0 до k – 1, соответственно остаткам), рёбра в котором определяются числами ai: из вершины v в вершину
длины li, означающее, что с помощью дописывания li цифр мы можем из префикса с остатком v получить префикс с остатком u. Легко заметить, что некоторые ai в этом графе будут соответствовать одним и тем же рёбрам (сейчас их nk) — это числа с одинаковой длиной десятичной записи и остатком от деления на k, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10k), и тогда количество рёбер не будет превышать 10k2.
Теперь всё, что от нас требуется, — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину k, имеющую те же исходящие рёбра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины k в вершину 0, что можно решить алгоритмом Дейкстры за O(k2). Однако, в силу специфичности задачи, решение алгоритмом Форда — Беллмана (с правильными отсечениями, конечно) также проходит все тесты, хоть в теории и имеет столь большие O(k3).
Восстановление ответа в задаче довольно стандартно, за исключением хранения дополнительного числа для каждой вершины, образовавшего ребро, по которому был осуществлён нужный в кратчайшем ответе переход.
Решение алгоритмом Дейкстры
Собери стол
Вася купил стол, у которого n ножек. Каждая ножка состоит из двух частей, которые соединяются друг с другом. Каждая часть может быть произвольной положительной длины, но гарантируется, что из всех 2n частей возможно составить n ножек одинаковой длины. При составлении ножки любые две части могут быть соединены друг с другом. Изначально все ножки стола разобраны, а вам заданы длины 2n частей в произвольном порядке.
Помогите Васе собрать все ножки стола так, чтобы все они были одинаковой длины, разбив заданные 2n части на пары правильным образом. Каждая ножка обязательно должна быть составлена ровно из двух частей, не разрешается использовать как ножку только одну часть.
Наибольший подъём
Профиль горного хребта схематично задан в виде прямоугольной таблицы из символов «.» (пустое пространство) и «*» (часть горы). Каждый столбец таблицы содержит хотя бы одну «звёздочку». Гарантируется, что либо любой из символов «*» находится в нижней строке матрицы, либо непосредственно под ним находится другой символ «*».
Маршрут туриста проходит через весь горный хребет слева направо. Каждый день турист перемещается вправо — в соседний столбец в схематичном изображении. Конечно, каждый раз он поднимается в самую верхнюю точку горы (или опускается), которая находится в соответствующем столбце.
Считая, что изначально турист находится в самой верхней точке в первом столбце, а закончит свой маршрут в самой верхней точке в последнем столбце, найдите две величины:
Любимые числа Поликарпа
Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на бóльшую степень числа 2.
Решение. Для решения данной задачи нужно воспользоваться фактом, что степени двойки быстро растут и максимальная степень двойки, на которую может делиться число, не превосходящее 109, равна 29. Поэтому нужно просто проитерироваться по заданным числам, найти максимальную степень двойки, на которую делится текущее число, и обновить ответ этой максимальной степенью.
Собачки и миски
На координатной прямой сидит n собачек, i-я собачка находится в точке xi. Кроме того, на прямой есть m мисок с едой, для каждой известна её координата на прямой uj и время tj, через которое еда в миске остынет и станет невкусной. Это значит, что если собачка прибежит к миске в момент времени, строго больший tj, то еда уже остынет и собачка кушать её не станет.
Считая, что каждая собачка бежит со скоростью 1, найдите максимальное количество собачек, которые смогут покушать. Считайте, что собачки побегут к тем мискам, на которые вы им укажете. Из одной миски не могут кушать две или более собачки.
Собачки могут обгонять друг друга, то есть, если одна из них остановится покушать, другая может пройти мимо неё, чтобы попасть к другой миске.
Будем решать задачу жадно. Рассмотрим самую левую собачку и те миски, из которых она может поесть. Если таких мисок нет, то собачка не сможет покушать. В противном случае из мисок, доступных самой левой собачке, выберем для неё миску с самым левым правым концом. Далее не будем рассматривать эту собачку и эту миску и продолжим аналогично наши рассуждения.
Легко видеть, что такая жадность приводит к оптимальному ответу:
По этой задаче можно было попробовать написать другие жадности, но многие будут неправильными.
Для того чтобы это реализовать, отсортируем собачек и миски (по левому концу) слева направо. Будем идти слева направо, обрабатывая события «появилась миска» (в этом случае добавим её правый конец в какую-нибудь структуру данных) и «появилась собачка» (нужно для собачки в структуре данных найти самый левый подходящий правый конец).
Сложность: O(nlogn) или O(n) в зависимости от структуры данных (*set* или queue).
Решение на С++
Лучшие результаты
В первом отборочном раунде приняло участие 929 человек. Лучший результат показал Владислав Макеев (Москва, Россия). Второе и третье место заняли Ростислав Величко (Ставрополь, Россия) и Роман Горбунов (Москва, Россия).
Второй отборочный раунд собрал 686 человек. С большим отрывом первое место в рейтинговой таблице занял Влад Мосько (Гомель, Белоруссия). Второе и третье место — Назарбек Алтыбай (Актобе, Казахстан) и Владимир Романов (Москва, Россия).
Мы ещё раз поздравляем всех финалистов и ждём новых участников в следующем году.
