Размер:
A A A
Цвет: C C C
Изображения Вкл.Выкл.
Обычная версия сайта
Demidov Yaroslavl State University
27/10/2016

18-20 октября РГАТУ принимал четвертьфинал ACM ICPC, или International Collegiate Programming Contest – чемпионат мира по спортивному программированию, который ежегодно проходит под эгидой Ассоциации вычислительной техники (ACM). В соревновании приняли участие студенты из 12 российских городов. ЯрГУ традиционно участвует в ACM ICPC и в этом году отправил на четвертьфинал чемпионата 4 команды. Yaroslavl SU #1 - Григорий Ахременко, Анастасия Торопова, Дмитрий Крайнов – завоевала первое место на этом этапе чемпионата, решив 10 задач за 1345 мин. Yaroslavl SU #2 – Артем Лютенков, Игорь Маслеников, Даниил Федулов – заняли шестое место; попав в верхушку турнирной таблицы эта команда, вместе с победителями, отправится на полуфинал ACM ICPC в Санкт-Петербург.

Yaroslavl SU #4 (Константин Пичкур, Роман Гибадулин, Владислав Петряков) и Yaroslavl SU #3 (Дарья Колесова, Егор Медведев, Игорь Серебряков) закрыли десятку лучших команд ЦФО, заняв 10 и 11 места соответственно.

Соревнования ACM ICPC проводятся в России уже более двадцати лет. Полуфинальные соревнования Северо-Восточного Европейского региона студенческого командного чемпионата мира по программированию АСМ пройдут в ноябре-декабре 2016 года в Санкт-Петербурге. А финал этого престижного соревнования на этот раз примет Rapid City (США).

Участники команд, студенты математического факультета и факультета ИВТ ЯрГУ: «Это было круто. Задачи понравились, но было легче, чем на тренировках.»

Тренер команд, зам. декана по учебной работе математического факультета, канд. физ.-мат. наук Надежда Быкова: «Чем объяснить успех Yaroslavl SU #1? Наверное, уровнем подготовки. Эта команда чаще всего ездила на тренировочные сборы по сравнению с другими нашими командами за последнее время.»

Попробуй решить!

Задача, которую команда Yaroslavl SU #1 решила за мин. : Школьник Вася так долго работал за компьютером, что у него заболели глаза и он перестал различать цвета. Врач выписал больному витамины, которые нужно принимать три раза в день: утром - белую таблетку, после обеда - красную и синюю на ночь. При этом таблетки помещены в одну банку и Вася не может отличить одну таблетку от другой, но прочитав инструкцию он обнаружил, что таблетки отличаются по весу: белые самые тяжелые, красные полегче, а синие самые легкие. Вася достал аптекарские весы и приступил к взвешиванию таблеток. Для каждого взвешивания мальчик выбирал две таблетки и клал их на чаши весов, а результат взвешивания записывал в таблицу. После m взвешиваний Вася решил, что получил достаточно информации, чтобы определить цвет каждой таблетки. Напишите программу, которая по частично заполненной таблице взвешиваний, восстановит цвета всех таблеток.

Решение: Таблетки раскладываем по кучкам, если две таблетки равны, то они в одной кучке (для этого есть специальная структура данных - система непересекающихся множеств). Дальше, если про какие-то три таблетки известно, что первая меньше второй, а вторая меньше третьей, то в кучке, где лежит вторая таблетка, все таблетки красные. Если для какой-то кучки известно, что в ней есть таблетка меньше таблетки из красной кучки, то эта кучка синих таблеток (аналогично если больше, то таблетки белые) для остальных таблеток цвет определить нельзя.

Источник: Монависта

Возврат к списку