 |
|
|
|
Как и почему МФТИ стал лидером Международной студенческой олимпиады по программированию
Как и почему МФТИ стал лидером Международной студенческой олимпиады по программированиюВ области спортивного программирования, в основе которой лежит работа с алгоритмами, Россия показывает результаты значительно более высокие, чем все другие страны: c 2000 года российские команды завоевали 33 золотые медали, китайские – 13, команды стран Европы – 12, США – 7.
Одним из основных направлений деятельности Центра является подготовка студентов к ведущим международным соревнованиям по спортивному программированию. Для этих целей Центр основал международный проект Moscow Workshops. Его миссия – дать возможность студентам реализовать свой потенциал и улучшить свои позиции в турнирных таблицах соревнований по спортивному программированию, учиться и путешествовать. Проект состоит из открытых онлайн-курсов, заочных чемпионатов, проектов для школьников и тренировочных кэмпов. В Moscow Workshops уже приняли участие 2950 студентов из 221 вуза 58 стран. Команды московского Физтеха, начиная с 2011 года, привезли пять медалей финала ICPC – Международной студенческой олимпиады по программированию (три золота, одно серебро, одна бронза). Сегодня Физтех – единственный вуз, имеющий непрерывную череду медалей.
Помимо этого, Центр создал и продолжает развивать лагерь для школьников по подготовке к Международной олимпиаде школьников по информатике Moscow Workshops Juniors, фестиваль по программированию MosCode, который в этом году расширится и станет всероссийским проектом RuCode, организует Moscow Programming Contest и регулярные тренировки на кампусе Физтеха. В 2019 году Центр организовал следующие соревнования и сборы: MosCode Festival (Москва), Moscow International Workshop (Долгопрудный), Moscow Pre-Finals Workshop (Долгопрудный), Moscow Programming Contest (Москва и Московская область). В квалификационном туре Moscow Programming Contest приняли участие рекордное число человек – 1275 студентов и 1009 школьников отборочного тура Московской командной олимпиады школьников по программированию, объединенной с Moscow Programming Contest. Общая цифра участников, 2284, была зафиксирована в Реестре рекордов России. Также были проведены восемь выездных тренировочных сборов проекта Moscow Workshops: Discover Grodno 2019 by Moscow Workshops (Гродно, Республика Беларусь), Discover Vladivostok 2019 by Moscow Workshops (Владивосток, Россия), Discover Kyrgystan 2019 by Moscow Workshops (Бишкек, Кыргызстан), Discover Baikal 2019 by Moscow Workshops (Иркутск, Россия), Discover Riga 2019 by Moscow Workshops (Рига, Латвия), Discover Singapore 2019 by Moscow Workshops (Сингапур), ByteDance + Moscow Workshops Programming Camp 2019 (Пекин, Китай), Hello Muscat Pre-Finals ICPC (Маскат, Оман). В прошлом году студенты МФТИ взяли призовые места – в Moscow Programming Contest (Москва), в финале ICPC 2019 (бронза), на открытой международной студенческой олимпиаде по программированию имени С.А. Лебедева и В.М. Глушкова KPI-OPEN 2019 в Киеве (1 место), Открытом чемпионате БГУИР (Минск, Республика Беларусь), в XX открытой Всесибирской олимпиаде по программированию им. И.В. Поттосина, VIII Открытом чемпионате БГУИР по программированию, Baltic Sea Digital Event, Petrozavodsk Programming Camp ICPC, Moscow Capture The Flag М*CTF, сборах Moscow Workshops. Центр развития ИТ-образования – организатор первого университетского лагеря «Олимпиадные школы МФТИ», который проводится на кампусе Физтеха по STEM-предметам. За семь лет 3500 школьников из 20 стран прошли обучение в лагере. Выпускники «Олимпиадных школ МФТИ» уверенно выигрывают на олимпиадах: за это время треть учеников завоевали дипломы регионального и заключительного этапов Всероссийской олимпиады школьников. Кроме этого, 16 ноября 2019 года, на площадке «Яндекса» была проведена Всероссийская физико-математическая контрольная «Выходи решать!». В решении онлайн по всей России приняло участие 78 тысяч человек. В прошлом году Центр провел юбилейную десятую Зимнюю компьютерную школу (Moscow Workshops Juniors) – сборы для школьников 9–11 классов и две смены в центре «Сириус». В 2019 году российские школьники стали единственной сборной, которая завоевала сразу четыре золотые медали. На базе МФТИ проходят регулярные тренировки команд Физтеха с тренером Михаилом Тихомировым. Помимо них в 2019-2020 учебном году впервые открылись Московские тренировки по спортивному программированию, организованные при поддержке Мэра Москвы, которые может посетить любой студент московского вуза совершенно бесплатно. С 2018 года в МФТИ проходит отбор и подготовка национальной сборной на Международную олимпиаду школьников по информатике IOI (International Olympiad in Informatics). Сборы проводятся в ноябре и мае, в каждых участвуют более 20 ребят, отобранных по результатам Всероссийской олимпиады школьников и других выступлений и заслуг. В результате четверо из них представляют страну на IOI. Команду готовят к соревнованиям тренеры из ведущих университетов России. С 20 по 24 ноября 2019 года российские школьники завоевали 37 медалей из 91, в том числе 14 золотых, на Международном турнире по информатике в Шумене (Болгария), из которых 15 победителей – участники сборов МФТИ. Также в 2019 году российская сборная стала единственной командой, завоевавшей четыре золота IOI, проходившей в Баку. IOI проводится в формате индивидуального состязания в два ытура, продолжительностью по пять часов, в каждом из которых нужно решить по три задачи по программированию. За каждую задачу можно получить до 100 баллов в зависимости от полноты представленного решения (количества и сложности правильно решенных подзадач). Следующие соревнования пройдут с 19 по 26 июля 2020 года в Сингапуре. В 2019 году студенты МФТИ приняли участие в 19 российских и международных чемпионатах и сборах. Участие студентов в соревнованиях поддержал Фонд целевого капитала МФТИ.
В 2020 году Центр развития ИТ-образования МФТИ реализует следующие мероприятия:
Задача. «Контакт» для двоих
Лось Валера очень любит играть в «Контакт» – широко популярную словесную игру; однако поиграть в нее в последнее время удается нечасто, ведь в игре должны участвовать не менее трех игроков, а собраться вместе как минимум втроем из-за нехватки времени и нестыкующихся графиков крайне затруднительно... В силу этого, лось Валера придумал новую игру – «Контакт для двоих». Суть ее заключается в следующем. Один из игроков загадывает некоторое непустое слово S, которое второй игрок должен отгадать, и сообщает первую букву этого слова. Второй игрок, пытаясь угадать слово, называет одно за другим слова, начинающиеся на заданную букву, а первый игрок сообщает ему, верное ли слово, причем второй игрок не должен повторяться. Если второй игрок назвал некоторое наперед заданное число K слов и так и не угадал слово, то первый игрок сообщает вторую букву слова; после этого, второй игрок может называть лишь слова, начинающиеся с этих двух букв и не названные им ранее (в том числе и когда он знал лишь одну букву). Если после появления второй буквы, второй игрок сумеет назвать еще K слов, то первый игрок сообщает третью букву, и т.д. Если в какой-то момент оказывается, что первый игрок уже назвал все буквы своего слова, а второй после этого назвал K слов, начинающихся с него, но само слово не назвал, то первый игрок просто сообщает, что уже открытые буквы и образуют загаданное слово, и игра заканчивается. Чтобы игра была интереснее, лось Валера, играя за первого игрока, старается загадать такое слово, чтобы второй игрок сделал как можно больше попыток угадать его (удачная попытка также считается). Однако сам процесс игры зависит от словарного запаса второго игрока, а также от выбранного числа K. Так как лось Валера хорошо знает своих друзей, то для каждого из них Валера может выписать все слова, которые тот знает. Конечно же, чтобы не расстраивать второго игрока, Валера всегда загадывает слово, которое игрок знает. Однако, не так-то просто выбрать это слово и число K. Поэтому Валера решил написать программу, которая по заданному словарю и Q парам «загаданное слово – значение K» определяет, какое максимальное число слов может назвать второй игрок, пока игра не закончится угадыванием слова вторым игроком или сообщением слова первым. Лось Валера справился с задачей. Справитесь ли вы? Формат входных данных В первой строке записано единственное целое положительное число N – количество слов в словаре потенциального второго игрока. В каждой из следующих N строк записано одно непустое слово этого словаря, состоящее из строчных букв английского алфавита. Суммарная длина слов не превосходит 2 · 105. Обратите внимание: слова могут быть одинаковыми по написанию, например, потому, что они различаются при произношении ударениями: к примеру, в русском языке слова «замОк» и «зАмок» разные слова, хотя пишутся одинаково. В языке, на котором лось Валера и его друзья любят играть в «Контакт», количество возможных акцентов, делающих одинаково записываемые слова разными по звучанию, очень велико. Во время игры участники полностью различают одинаково записываемые слова, произнося их по разному. В (n + 2)-й строке содержится целое число Q, (1 ≤ Q ≤ 2 · 105) – количество исследуемых пар «загаданное слово – значение K». В следующих Q строках записаны по два целых числа w и K (1 ≤ w, K ≤ n) – номер загаданного слова из словаря и предполагаемое значение K. Cлова нумеруются в том порядке, в котором они заданы выше, начиная с единицы. Формат выходных данных Для каждой из Q пар выведите в отдельное строке единственное целое число – максимальное количество слов, которые может назвать второй игрок. Примеры
|
Алексей Малеев:
Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
