Метка «спортивное программирование» - 2

Отчёт со Всероссийского Открытого Чемпионата по программированию
Первый день: как видите, многие финалисты со своими ноутбуками

В эту пятницу закончился Всероссийский Открытый Чемпионат по программированию, где нужно сначала решать задачи, а потом «взламывать» решения других участников.

Кто и откуда приехал?

Участвовало 3500 программистов со всей России, из стран СНГ и совсем немного — из других стран. К первому туру было отобрано 2000 участников, ко второму — 400, а в финал в Москве вышло 50 человек. Уровень в этом году был явно выше чем в прошлом: либо сказались тренировки и то, что турнир набирает известность, либо то, что в игру включились гости из других стран. Приезжали участники финалов прошлых лет.

В финал попало 16 москвичей, 14 петербуржцев, по двое жителей Екатеринбурга, Нижнего Новгорода, Саратова, один участник приехал из Новосибирска. Также в финал вышли по трое из Беларуси, Польши, Украины и даже один человек из Японии. По правилам турнира мы оплачивали дорогу всем, кроме жителей Польши и Японии, а проживание оплатили каждому участнику.Читать полностью »

Школьник об олимпиадном программировании
Здравствуй!
Пишет тебе девятиклассник, призер регионального этапа всероссийской олимпиады по информатике. В последнее время я стал замечать, что у читателей повысился интерес к олимпиадам по программированию. Как их активный участник я постараюсь ответить на все вопросы, рассказать о своем пути, привести примеры реальных, запомнившихся мне задач.
Читать полностью »

Олимпиадные задачи по программированию: что за зверь?Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с примера олимпиадной задачи.

Этот же пример, чтобы по ссылке не ходить

ИТ-рестораны

ограничение по времени на тест: 4 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: standard input
вывод: standard output

В городе N. очень плохо с дорогами, общепитом и IT-инфраструктурой. Всего в городе n перекрестков, некоторые пары которых соединены двусторонними дорогами. Дорожная сеть состоит из n - 1 дороги, по дорогам можно добраться с любого перекрестка на любой другой. Да, вы правы — дорожная сеть образует неориентированное дерево.

Недавно мэр города придумал способ, устраняющий проблемы с общепитом и IT-инфраструктурой, причем одновременно! Решено поставить на перекрестках города ресторанчики двух известных сетей кафе для IT-шников: «iMac D0naldz» и «Burger Bing». Так как владельцы сетей не дружат, категорически запрещается размещать рестораны двух разных сетей на соседних перекрестках. Есть и другие требования. Вот полный список:

  • в каждом перекрестке должен находится не более чем один ресторан;
  • каждый ресторан принадлежит либо «iMac D0naldz», либо «Burger Bing»;
  • каждая сеть должна построить не менее одного ресторана;
  • не существует пары перекрестков, которые соединены дорогой и на которых стоят рестораны разных сетей.

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

Помогите мэру проанализировать ситуацию. Найдите все такие пары (a, b), что a ресторанов может принадлежать «iMac D0naldz», b — «Burger Bing», а сумма a + b максимальна.

Входные данные

В первой строке входных данных содержится целое число n (3 ≤ n ≤ 5000) — количество перекрестков в городе. Далее в n - 1 строке перечислены все дороги, по одной дороге в строке. Каждая дорога задана парой чисел xi, yi (1 ≤ xi, yi ≤ n) — номерами соединяемых перекрестков. Считайте, что перекрестки пронумерованы от 1 до n.

Гарантируется, что заданная дорожная сеть представляет собой неориентированное дерево с n вершинами.

Выходные данные

В первую строку выведите целое число z — количество искомых пар. Далее выведите все искомые пары (a, b) в порядке увеличения первой компоненты a.

Примеры тестов

Входные данные

5
1 2
2 3
3 4
4 5

Выходные данные

3
1 3
2 2
3 1

Входные данные

10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4

Выходные данные

6
1 8
2 7
3 6
6 3
7 2
8 1

Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.
Читать полностью »

Russian Code Cup: как это было, как это будет
В 2013 году Mail.Ru Group организует очередную, третью по счёту, международную олимпиаду для самых сильных программистов – Russian Code Cup 2013. Мы задумывали олимпиаду как способ популяризации программирования, поднятия престижа профессии (и, конечно, как отличный повод измерить свою скорость мысли на интеллектуальной гоночной трассе).
Russian Code Cup: как это было, как это будет
Читать полностью »

Приходите на чемпионат по программированию: будем решать задачи и «ронять» код оппонентов
Финал прошлого чемпионата для студентов МГТУ – фото MDovzhenko

Правила простые — 5 «олимпиадных» задач разной сложности, плюс возможность «взламывать» решение оппонента сложным набором входных данных. То есть, сначала пишем свой код, потом «ломаем» чужой. Официально всё это называется Всероссийский Открытый Чемпионат по программированию «КРОК-2013» при поддержке Codeforces и Саратовского ГУ.

Зачёт индивидуальный, призы — 100 000 рублей за первое место, 70 тысяч — за второе, 50 тысяч — за третье. Плюс будет дополнительный игровой конкурс, победитель которого тоже получит приз. Для финалистов из РФ — бесплатная поездка в Москву, питание и проживание на два дня.

В прошлом году проводилось похожее мероприятие, тогда участвовало примерно 1500 человек (в квалификационном раунде), поэтому в этом году схема будет такая:

  • Квалификационный раунд – 13-14 апреля, удалённо (на следующий этап проходит не более 2000 участников).
  • Первый отборочный раунд – 15 апреля, удалённо (проходит 400 участников).
  • Второй отборочный раунд – 22 апреля, удалённо (проходит 50 участников).
  • Финал чемпионата состоится 16 и 17 мая в Москве в офисе компании КРОК.

Во всех раундах 5 задач, по мере приближения к финалу их сложность будет немного увеличиваться.Читать полностью »

Расскажу о своем участии в Russian AI Cup. Я — участник с ником Hohol, занявший второе место в финале.

У меня уже имелся некоторый опыт в написании бота для управления танком. Дело в том, что я вот уже пять лет участвую в ACM ICPC. Четвертьфинал нашего региона проходит в стенах Саратовского Государственного Университета, который, напомню, является одним из организоторов Russian AI Cup. На четвертьфинале каждый раз проводится неофициальный игровой конкурс Code Game Challenge. Суть все та же — напишите бота, который всех порвет. И хотя боты оказываются то волшебниками в шляпе и с посохом, то гоночными автомобилями, то суднами на воздушной подушке — мы всегда звали их танчиками.

Так как я участвовал в CGC аж пять раз, конкурс особого энтузиазма у меня поначалу не вызвал.

Но познакомившись с правилами поближе, решил, что конкурс мне все же интересен.Читать полностью »

Здравствуйте, Хабровчане!
Предлагаю вашему вниманию историю своего участия и победы в финале конкурса по программированию CodeTanks 2012.

Путь к победе на Russian AI Cup 2012

Про соревнование я узнал на Хабре, решил выяснить подробнее, пошел на сайт проекта. Обрадовала возможность писать на С++ под Linux без танцев с бубном. Сразу подумалось, что будет выигрыш в производительности по сравнению с участниками, пишущими на языках типа Java/Python. Ну и сам формат соревнования мне понравился: до первого раунда две недели, дальше по неделе перерыва между раундами. Не нужно в жутком цейноте рожать правильно работающий код, а можно относительно спокойно все продумать и запрограммировать. Дальнейшее изучение правил и просмотр боев на сайте только укрепили решение участвовать: мне гораздо более интересно программировать AI в сложном и плохо определенном окружении, чем в полностью формализованном, типа настольных игр.

Читать полностью »

Яндекс готов дать официальный старт новой «Интернет-математике». Регистрация участников продлится до 15 декабря, а прием решений – до 22 декабря. Сайт конкурса: switchdetect.yandex.ru.

В 2012 году конкурс проводится в седьмой раз. В этом году конкурс сосредоточится на предсказании переходов на другую поисковую систему в рамках одной поисковой сессии.

Специально для конкурса Яндекс предоставляет полностью обезличенный набор данных — информацию о запросах и кликах пользователей на документы, а также о том, в какой момент сессии они воспользовались любым другим поисковиком, помимо Яндекса.

Читать полностью »

Russian AI Cup 2012
Спешим поделиться с вами новостью: 29 октября 2012 мы запустили соревнование для программистов под названием Russian AI Cup 2012: CodeTanks! Нет, здесь вам не надо будет решать алгоритмические задачи на скорость — в этот раз участникам предстоит написать искусственный интеллект для танка и принять участие в сражениях.

Читать полностью »

Всем привет! В сентябре прошла международная олимпиада по программированию, IOI 2012. И мы, сборная России, на неё весьма успешно съездили, как вы могли видеть.

Я — Макс Ахмедов. Мне предложили поделиться с общественностью, что из себя представляют подобные соревнования и какие задачи нам приходится решать. Я расскажу о последней задаче второго тура «Jousting Tournament». Английский вариант условия можно найти здесь. К слову, это наиболее простая из трёх задач в тот день :-)

Легенда

В задаче идёт речь о церемонии обручения герцога Лодовико Сфорца, наместника Милана, и герцогини Беатриче д’Эсте, произошедшей в 1491. Организовывать празднества и управлять культурной программой герцог пригласил своего хорошего друга Леонардо да Винчи, который ему предложил, в частности, устроить шикарный рыцарский турнир.

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

Такая вот захватывающая история.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js