Подведены итоги Олимпиады по программированию среди школьников

    С 16 по 22 января в Московском университете стали и сплавов прошла III Международная олимпиада по программированию среди школьников. Мероприятие было организовано НИТУ «МИСиС» и Cognitive Technologies. Признаться, понадобилось практически три недели, чтобы уговорить организаторов открыть хотя бы пару условий предложенных на мероприятии задач и получить разрешение опубликовать их разбор.

    Поверьте, это было не просто. Хотя их можно понять.
    Как известно, составление условий задач считается одним из наиболее сложных этапов подготовки соревнований по программированию.

    По их завершению они, как правило, используются при проведении тренировок команд, а также внешних контестов.
    Коллективы тренеров от разных вузов регулярно обмениваются контестами.
    Вообщем, повторное использование задач принято в олимпиадном движении.



    Но обо всем по порядку.


    К участию в очном туре олимпиады были приглашены более 70 школьников с 8 по 11 классов из разных регионов России и Республики Беларусь, успешно выступивших в заочном туре олимпиады.
    Напомним, формат мероприятия подразумевает проведение двух этапов: заочный (проводится осенью; в прошлом году он состоялся 16 ноября 2014 года; подробнее о нем можно посмотреть: http://ug.ru/news/13584) и очный (проводится в начале января).
    Организаторы при этом отмечают, что не делают ставку на гениев и вундеркиндов из спецшкол Москвы и Санкт-Петербурга.
    Целью проведения олимпиады является поиск перспективных и талантливых ребят, главным образом, из регионов России и ближнего зарубежья, желающих получить хорошее образование и реализовать себя в сфере информационных технологий.

    Начиная со 2 курса обучения студенты кафедры инженерной кибернетики проходят практику в университетских лабораториях и лучшим из них предлагается принять участие в реальных научно-прикладных проектах в области ИИ реализуемых совместно с компанией  Cognitive Technologies.

    Очный тур олимпиады был проведен по следующим правилам.

    • Продолжительность тура: 5 часов.
    • Количество задач: 10.
    • Рабочий язык: русский.

    При ранжировании участников и выявлении победителей главным фактором являлось количество решенных задач.
    При их равенстве учитывалась сумма времен от начала турнира до принятия проверяющей системой решения по всем решенным задачам плюс по 20 минут штрафа за каждое отвергнутое решение.
    Штрафы за неверные решения накладывались только на те задачи, которые в конечном итоге были приняты проверяющей системой.
    Для автоматизированной проверки решений использовалась система ejudge (https://ejudge.ru/).

    В итоге 10 задач не решил никто.

    Победителем олимпиады стал серебряный призер международной олимпиады по информатике (International Olympiad in Informatics) Алексей Вистяж из Ивьевской средней школы Республики Беларусь, который решил 9 задач.

    С заметным отрывом от него (5 решенных задач) второе место поделили Александр Зойкин (Оренбург) и Юрий Бондарчук (Беларусь).

    На третьем месте с четырьмя решенными задачами оказались Павел Бесчетнов (Тольяти), Дмитрий Галов (Москва) и Алексей Довгаль (Беларусь).

    16 школьников, признанные победителями и призерами получили ценные призы и  дополнительные баллы к общим результатам ЕГЭ при поступлении в НИТУ «МИСиС».

    Наибольшую сложность вызвала задача I. «Зеркало в коридоре».
    На удивление, участники плохо справились с задачами на геометрию.
    Организаторы считали их относительно простыми.


    Текст задачи I


    Ограничение времени: 0.5 секунды
    Ограничение памяти: 64 Мегабайт
    Ввод: Стандартный поток ввода (stdin)
    Вывод: Стандартный поток вывода (stdout)

    Простуженный Петя лежал в постели, как вдруг кто-то открыл дверь. Пете было лень вставать и он посмотрел в зеркало, чтобы увидеть кто пришёл. Известны координаты вошедшего (его можно считать материальной точкой), необходимо узнать, удасться ли Пете увидеть отражение вошедшего в зеркале. Зеркало имеет форму круга с центром в начале координат и расположено в плоскости ax + by + cz = 0. Петю тоже можно считать материальной точкой. Гарантируется, что Петя и незнакомец не лежат в плоскости зеркала и что Петя всегда видит отражающую сторону зеркала. Если изображение попадает на границу зеркала, то Петя видит вошедшего. Так как и Петю и вошедшего можно считать материальными точками, Петя может увидеть отражение вошедшего как сквозь вошедшего, так и сквозь свое собственное отражение.

    Исходные данные


    В первой строке записано натуральное число n – количество тестов, не превышающее 500. Каждый тест состоит из четырёх строк. В первой из них записан радиус зеркала. Во второй – коэффициенты a, b, c. Далее следуют координаты Пети. В четвёртой строке каждого теста записаны координаты вошедшего. Все числа целые и по модулю не превосходят 1000.

    Результат


    Выведите n строк. В каждой строке – ответ на очередной тест. “Yes”, если Петя видит вошедшего и “No” в противном случае.

    Пример


    Исходные данные Результат
    2
    2
    0 1 0
    0 2 0
    0 1 0
    1
    0 1 0
    2 -2 0
    1 1 0
    Yes
    No

    Разбор задачи I «Зеркало в коридоре»


    Отразим Петю относительно плоскости зеркала.
    Проведём прямую через отражённого Петю и незнакомца и пересечём её с плоскостью зеркала. Посмотрим, попадает ли точка пересечения в зеркало. Отдельно рассмотрим случай, когда Петя и незнакомец лежат по разные стороны от зеркала – тогда Петя его точно не видит.



    Текст задачи H «Ось симметрии»


    Ограничение времени: 1 секунда
    Ограничение памяти: 64 Мегабайт
    Ввод: Стандартный поток ввода (stdin)
    Вывод: Стандартный поток вывода (stdout)

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

    На рисунках ниже изображены два воздушных змея, летающих устойчиво и все варианты прикрепления к ним хвоста,
    а также один воздушный змей, летающий неустойчиво.




    Сколько существует точек на границе многоугольника, таких что, если приклеить к ним хвост, в результате получится воздушный змей, летающий устойчиво?

    Исходные данные


    В первой строке записано единственное целое число N (3 ≤ N ≤ 1000). В следующих N строках записаны через пробел по два целых числа, не превосходящие по модулю 10000 – координаты вершин многоугольника в порядке обхода.

    Результат


    Вывести единственное число – количество точек на границе многоугольника, к которым можно приклеить хвост змея.

    Пример


    Исходные данные Результат
    6
    3 3
    6 2
    6 -1
    3 -2
    0 -1
    0 2
    4
    3
    -2 2
    2 4
    0 0
    2
    4
    0 6
    6 0
    0 -3
    -2 0
    0


    Разбор задачи H «Ось симметрии»


    Ось симметрии многоугольника может проходить только через его вершины и через середины его сторон.
    Выпишем координаты 2N точек – вершин многоугольника и середин его сторон в порядке обхода и занумеруем их от 0 до 2N-1.
    Рассмотрим все претенденты на ось симметрии – прямые, проходящие через точки i и i+N, 0 ≤ i ≤ N-1.
    Для того, чтобы такая прямая была осью симметрии многоугольника, необходимо и достаточно, чтобы каждая пара точек i+j и (i-j)mod 2N, 1 ≤ j ≤ N-1, была расположена симметрично относительно этой прямой.

    Проверить симметричность расположения точек C и D относительно прямой AB проще всего, установив, что прямые AB и CD ортогональны и точка их пересечения делит отрезок CD пополам.
    Чтобы не выходить за пределы вычисления с целыми числами, достаточно все координаты точек увеличить в 4 раза.
    Трудоемкость такого решения равна O(N2).

    С задачей H «Ось симметрии» справилось двое участников А.Вистяж и П.Бесчетнов.

    Зимняя школа


    Во время очного тура для ребят также проводилась зимняя школа программирования.

    В ее рамках участникам олимпиады известные ученые и специалисты по ИТ читали лекции, проводили мастер-классы и учебно-тренировочные контесты.
    Участие в зимней школе и очном туре олимпиады по программированию было бесплатным для приглашенных участников. Им обеспечивался трансфер, питание и проживание.
    Каждого участника встречали на вокзале и провожали до места проведения мероприятий. На все время пребывания, со школьниками работали профессиональные вожатые, прошедшие подготовку в школе вожатых организуемой туристической компанией «ОСТ-ВЕСТ».

    Задачи и тесты для очного тура олимпиады разрабатывал коллектив тренеров по спортивному программированию НИТУ «МИСиС» и Cognitive Technologies во главе с членом-корр. РАН В.Л. Арлазаровым. В их числе: к.ф.-м.н. И.А. Фараджев, к.т.н. В.В. Постников, к.ф.-м.н. И.Б. Мамай, В.В. Соколов. А также аспиранты НИТУ «МИСиС»: К.Булатов, Т.Чернов и Н.Скорюкина.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 22

      +1
      Отражение Пети находится для него внутри зеркала (судя по точке прохода сквозь плоскость зеркала), то есть Петя видит не только гостя, но и себя. Но нарисованная перспектива, на мой взгляд, противоречит такому раскладу.

      А кто умеет аргументированно подсказать, может ли выделенная точка находиться там, где ее нарисовал автор?

      image
        0
        Почему нельзя смотреть вот так:
        image
          0
          Потому что если автор просто запутался с перспективой, то вы ее совсем потеряли.
            0
            У меня по-прежнему стойкое ощущение, что на изначальном рисунке путают линзу и плоское зеркало.
              0
              Ничего никто не путает. Как вы будете искать в плоскости зеркала такую точку, чтобы угол падения был равен углу отражения, без дополнительных построений?
                0
                С дополнительными, но ради бога не с такими. На рисунке изначальном угол падения НЕ равен углу отражения.
                Сначала рассмотрим двухмерный случай (повернём зеркало так, чтобы осталась только тонкая линия).
                image
                Пусть А = Xp+Xv. Пусть B = Xv:Xp = Rv:Rp = Hv:Hp (дважды теорема Фалеса). Решаем систему относительно Хр: Хр = А / (1+В)
                Зная Хр легко выходим в точку О. Дальше достаточно проверить попадание этой точки в эллипс нашего зеркала.

                Как прийти к этой картинке из трёхмерного случая? Вот так: провести плоскости, параллельные плоскости зеркала, через точки P и V (если это одна плоскость, задача вырождается в элементарную), после чего построить плоскость, перпендикулярную плоскости зеркала, содержащую оба перпендикуляра Нр и Hv.
                  0
                  PS. У меня почему-то стойкое ощущение, что на бумаге задачу решили все, а с программированием не справились те, кто не знал формул, позволяющих все те же действия проделать с конкретными трехмерными координатами. Ну, или в тестах попадались хардкорные ситуации с точкой на зеркале на расстоянии R±ε (погрешность плавающей точки) (я бы не делал таких тестов)
                    0
                    Хардкорных тестов не было, я проверял (у меня решение зашло без каких-либо «безопасных» сравнений чисел с плавающей точкой). Возможно на бумаге действительно задачу решили многие, однако посылка во время контеста была всего одна, и с ошибкой в формуле, а не в технике.
                      0
                      однако посылка во время контеста была всего одна

                      Прошу прощения, можете пояснить, что Вы имели в виду?
                      Из всех участников попытался решить только один, и у того – была ошибка в формуле?
                        0
                        Да, попытка решения задачи была всего одна, и она получила вердикт Wrong Answer на втором тесте.

                        Прошу прощения, насчет ошибки в формуле я вас дезинформировал, только что пересмотрел ту посылку. В решении используется двойной тернарный поиск точки, в которой углы падения и отражения будут равны. Как будет свободное время, я попытаюсь сдать эту задачу тем же способом (чтобы понять, что конкретно участник делал неправильно).
                    0
                    Ваше решение абсолютно верно, и, прошу заметить, никак не противоречит авторскому. На вашем рисунке вы также просто нашли бы точку O просто ортогонально отражая точку P относительно плоскости зеркала (на вашем рисунке — относительно вертикальной прямой, содержащей зеркало) и пересекая плоскость зеркала с прямой, проходящей через отражение P и точку V.

                    Как правильно заметил mayorovp, пожалуй единственной проблемой оригинального рисунка состоит в том, что прямая P'P должна быть перпендикулярно прямой, содержащей бОльшие полуоси эллипса. Доказать корректность авторского подхода просто — так как прямая P'P перпендикулярна плоскости зеркала, она перпендикулярно любой прямой, лежащей в этой плоскости. А значит, P'P перпендикулярна прямой, проходящий через точки пересечения плоскости и прямых P'P и P'V. Из этого же следует (обозначив буквой C точку пересечения плоскости и прямой P'V), что углы между плоскостью и прямыми PC и CV равны. После этого останется только проверить, что точка С находится на зеркале. Перехода к планиметрии при таком подходе не требуется, и код программы получается очень короткий.
                      0
                      Естественно, при РР' перпендикулярном плоскости зеркала рисунок автора выродится в мой, и мой вопрос автоматически исчезнет. Я бы даже не стал заморачиваться с собственным чертежом, если бы не резанул по глазам авторский рисунок, на котором автор поленился расставить прямые углы.
                        0
                        Обычно в таких случаях помогает чтение текста рядом с рисунком. В тексте было черным по белому написано, что P1 — отражение точки P в зеркале.

                        «Геометрия — это искусство делать правильные выводы из некорректных рисунков»
            0
            Система координат на рисунке не задана — поэтому введем свою. Пусть плоскость проекции будет плоскостью ZOX — а за «глубину» отвечает ось OY.

            На проекции большая ось эллипса вертикальна — значит, плоскость зеркала параллельна OZ. Но тогда нормаль к этой плоскости должна быть перпендикулярна OZ. Но такая прямая в проекции должна стать горизонтальной.

            Следовательно, прямая PP1 должна быть строго горизонтальной, а не наклонной.

            Эти рассуждения верны как для ортогональной проекции, так и для центральной.
            +1
            Приглашаем на олимпиаду школьников из Беларуси, называем ее международной. Признак международной олимпиады — наличие школьников из по крайней мере двух стран, проверять тексты задач на ошибки уровня тся/ться для этого вовсе не обязательно. Мне вот интересно, откуда у неизвестных в олимпиадном программировании вузов такое стойкое желание организовать олимпиаду с как можно более громким названием?
              0
              В заочном туре участвовали ученики из 4 стран.
              Спасибо за информацию, тексты проверим.
                0
                Стойкое желание вполне понятно, и, как мне кажется, вполне резонно — «неизвестному в олимпиадном программировании» вузу хочется стать более известным.
                Я конечно необъективен, так как выпускник этого вуза, и олимпиадник, но все-таки считаю организацию олимпиады для школьников самым приличным способом повысить известность вуза в олимпиадном плане. Вуз принимает участие в олимпиадах, выходит в финал ACM ICPC, и тем временем остается не очень известным. Организует (ежегодно, хотя хотелось бы чаще) олимпиаду для школьников, школьники отзываются, приезжают, решают задачи, победители получают призы. Взамен ~100% участников этой олимпиады узнают про этот вуз, а какой-то, пусть маленький, процент, возможно рассмотрит этот вуз в качестве будущей альма матер. Не вижу подвоха, с моей точки зрения — это win-win.
                  +1
                  Зачем ехать на межнар не умея писать довольно простой перебор с комбинаторикой — мне не очень понятно, но это не важно. Попасть на финал из неизвестного вуза довольно легко и я слышал об энтузиастах, которые поступают в неизвестный вуз, чтобы проделать этот трюк.

                  МАИ, например, довольно часто светится, выставляет стабильно много команд и некоторые добиваются довольно серьезных успехов, но что-то я никогда не слышал, чтобы МАИ организовывала открытые олимпиады для школьников. Но это тоже неважно.

                  Называть олимпиаду международной можно только формально и инициатива выглядит, как попытка косить под почти идентично зовущийся IOI, в которой уровень слова «международный» совершенно иной. Но это тоже неважно.

                  Что важно — так это отношение организаторов. Глупые орфографические ошибки в условиях; картинки, которые даже на хабре всех путают, закрытые задачи и результаты; список победителей лежит на бывшей странице регистрации и у нее все еще неверный заголовок, призеров называют победителями, победителей — призерами и не дают им диплом первой степени, как это обычно принято; олимпиада не ориентирована на уровень ниже, чем у московских спецшкол, но серебряный призер IOI все равно участвует и еще миллион мелочей, явно показывающий, что на образовательные и рекламные цели олимпиады всем пофиг, а людей с прямыми руками, которые могут сделать все по-нормальному в вузе нет совсем.

                  Все это очень напоминает воронежскую олимпиаду: esci.ru/ttb/vserossiyskaya_studencheskaya_olympiada_in_informatics.htm. Когда я был школьником, я прочитал этот текст и точно знал, в какой вуз я никогда не пойду даже заглянуть внутрь.
                    0
                    Спасибо за Ваше мнение, учтем при проведении следующей олимпиады.
                +1
                На удивление, участники плохо справились с задачами на геометрию.

                Видимо вы не много соревнований провели. Иначе не удивлялись бы. Это вполне обычная картина.
                  0
                  Я не понимаю, откуда такое мнение. 70% задач на геометрию — тупые построения, как обе задачи из этой темы. Из оставшихся задач 95% решаются сканлайном либо выпуклой оболочкой. Оставшиеся задачи используют геометрические примитивы только для формулировки: они либо основаны на вытаскивании чисел и запихивании их в структуру данных, либо очень технические и не требуют думать, а просто аккуратно реализовать 9000 шагов, описанных в условии. Последние тяжело назвать геометрическими, это все равно что считать задачи с домами задачами на архитектуру. Это все дополняется тем, что ответ часто дробный и можно одним тестом проверить весь код сразу с очень неплохим шансом. Если задачи на геометрию решаются плохо — обычно это значит, что кто-то перегробил геометрию в туре.
                    +1
                    Во-первых, да. Из геометрии легко сделать гроб, за который никто не возьмётся.
                    Во-вторых, частные случаи, которые не сразу можно заметить и из-за которых сдача затягивается на несколько попыток.
                    В третьих, тупые построения вместе с частными случаями требуют довольно много кода и тестирования, из-за чего геометрия откладывается на потом.
                    Отсюда и получается, что в таблице на месте геометрических задач либо прочерки, либо периодические "-12", "-23", сменяющие "+2", "+3"… :)

                Only users with full accounts can post comments. Log in, please.