Сергей Мухамедов

© Babr24.com

Интернет и ИТМир

2580

22.07.2013, 15:04

Мозги

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

Спортивная арена. Сто двадцать команд. Зрители. Две телекамеры онлайн-трансляции. И... абсолютная тишина все пять часов.

Никакого экшена, только невероятная мыслительная работа.

Сложно представить, как эти соревнования проходили 37 лет назад. Арифмометр "Феликс", логарифмическая линейка и карандаш с листом бумаги? ЭВМ в то время были размером с дом или комнату.

Это финал международного командного чемпионата мира по программированию ACM ICPC. Впервые за всю историю, он проходил в России.

Это самое крутое в мире командное соревнование программистов.

35 тысяч участников из 2322 университетов 91 страны боролись за то, чтобы попасть в этот зал и решить 11 сложных алгоритмических задач

Это лучшие молодые мозги мира.

Несмотря на то, что они еще учатся в университетах, все, кто дошел до финала, уже трудоустроены

Следить за ними начинали класса с шестого, когда они побеждали на своей первой олимпиаде по программированию.

Им уже гарантированы зарплаты от 120 тысяч долларов в год и доли акций в компаниях

И совсем не обязательно, что эти компании будут иностранными

У нас им будут платить не меньше, чем на западе. Да и мотивация у таких людей совсем другая.

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

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

Их ждут компании, которыми вы пользуетесь ежедневно - это Гугл, Фейсбук, Яндекс... И конечно в сложные и интересные стартапы. Работу в банках они считают "ниже плинтуса".

Но сама концепция чемпионата не предполагает охоту за сотрудниками. Тот же самый Яндекс, выступая официальным партнером ACM ICPC, даже не имел в зале никакой рекламной растяжки. Всех российских, украинских и белорусских ребят компания знает лично, благодаря своим академическим программам на которые за шесть лет потратила миллиард(!) рублей.

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

Шарики вручают за решенные задачи, а так же за другие заслуги типа "Первая команда, выполнившая задание F"

Через 5 часов эти ребята в черных футболках будут победителями. До этого, в разных составах, перербургская команда Национального исследовательского университета информационных технологий, механики и оптики (НИУ ИТМО) становилась чемпионами мира четыре раза.

Второе место заняла команда Шанхайского технического университета, третье – Токийский университет

Для примера перевод одной задачи этого года. Оригинал естественно был на английском:

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

Акция казино включает следующее: вы можете играть столько, сколько хотите. И после того, как вы закончите, какую бы сумму вы ни проиграли с момента начала, казино возвращает х% ваших потерь. Естественно, если вы оказались в выигрыше, вы забираете его весь.

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

Для простоты предположим, что все ставки стоят 1 доллар, а выигрыш составляет 2 доллара. Теперь допустим, что х равно 20. Если вы сделаете всего 10 ставок, перед тем как закончить игру, и только 3 из них выиграют, то ваши общие потери составят 3,2 доллара. Если 6 ставок выиграют, то ваш выигрыш составит 2 доллара.

Даны x и p (вероятность выигрыша единичной ставки в процентах), вам требуется написать программу для определения максимального ожидаемого выигрыша, который вы можете получить, используя любую стратегию игры.

Входные данные состоят из одного теста, который содержит процент возврата х (0 ? х <100) и вероятность выигрыша в процентах p (0 ? p <= 50). x и p имеют не более двух цифр после запятой.

Выведите максимальный ожидаемый выигрыш с абсолютной погрешностью не более 10 -3

Для тех, кто знает основы теории вероятностей и умеет программировать задачка может показаться простой, но это не так - при приближении параметров к допустимым границам возникают серьезные проблемы…

Вот как описал чемпионат Алексей Дергунов из команды Самарского государственного аэрокосмического университета, занявшей 35 место:

В начале контеста мы сильно растерялись. Я и craus очень долго думали над задачей F — мы сдали ее под занавес первого часа, по пути отсеяв несколько неверных решений и написав то, к которому не получилось придумать контрпример. Затем мы решали задачу D. Не понимая, как ее делать, Hohol распечатал ответы на первые несколько тестов, но ничего не извлек. Потом я вспомнил задачу с тимуса и написал точно такой же перебор — оказалось, что кандидатов на ответ порядка 50 тысяч (конечно, порядочный ACM-щик должен знать, что их мало, но мы такими не являемся), так что работает прекальк. Дальше подоспели решения задач A и H, которые пришлось немного подебажить, так как писать с первого раза мы так и не научились. Затем мы решили задачу C: сабмит в 3:5x был уже правильным, но TL-ным: команда из трех желтых участников не умеет писать maxflow и поэтому копипастит его с Team Reference, где есть лишь алгоритм Диница, да еще и с кучей ArrayList-ов. Заменив все ArrayList-ы на массивы, мы сразу же получили Accepted. Оставалось немногим более получаса, мы решили, что не умеем решать J за это время (задача, надо сказать, очень противная, из тех, что я особенно ненавижу — куча тупейшей бессмысленной реализации), и поэтому попытались решить B, но, как оказалось, надо было решать специфическую системку уравнений за O(1), как когда-то учили на третьем курсе (на самом деле приятная неожиданность — знания, полученные и успешно забытые в универе, оказались нужными в ACM ICPC!)

На следующий день после финала министр обороны России Сергей Шойгу поручил разыскать(!) петербургских студентов, пять раз становившихся чемпионами мира по программированию, чтобы укомплектовать создающиеся в российской армии научные роты.

Михаил Кевер, Нияз Нигматуллин и Геннадий Короткевич, доучивайтесь и держитесь от министра подальше. Вы заслуживаете большего, чем набивать школьные рефераты сыну начальника части.

Источник: Оттенки Серого

Сергей Мухамедов

© Babr24.com

Интернет и ИТМир

2580

22.07.2013, 15:04

URL: http://babr24.com/?ADE=116841

bytes: 9303 / 4392

Обсудить на форуме Бабра в Telegram

Поделиться в соцсетях:

Автор текста: Сергей Мухамедов.

Другие статьи в рубрике "Интернет и ИТ"

Сергей Эмдин: «Люди распробовали новый цифровой образ жизни»

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

Александр Макаров

Интернет и ИТЭкономика и бизнесИркутск Россия

2758

17.09.2020

В Прибайкалье впервые открылся набор в Яндекс.Лицей

У юных программистов Иркутской области появилась возможность проявить себя и научиться новому у специалистов крупнейший IT- и интернет-компании в России. Обучение бесплатное. «Программирование – это творчество». Яндекс.

Анна Амгейзер

Интернет и ИТОбразованиеМолодежьИркутск

3813

02.09.2020

Реклама Yota посмотрит на своих зрителей

Yota запустила рекламную кампанию в поддержку максимального пакета связи для новых клиентов. Цель кампании #каждыйтретий - рассказать людям о том, что с Yota можно не переплачивать за мобильную связь.

Ярослава Грин

Интернет и ИТИркутск

13167

25.08.2020

Цифровизация оказалась благом

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

Дмитрий Верхотуров

Интернет и ИТЭкономика и бизнесНаука и техникаМир

13254

09.06.2020

Рейтинг политических Телеграм-каналов Восточной Сибири. Весна 2020

Бабр публикует весенний 2020 года рейтинг региональных политических телеграм-каналов Восточной Сибири.

Максим Бакулев

Интернет и ИТПолитикаИркутск Красноярск Бурятия

23727

03.06.2020

Yota запускает продажи SIM-карт на Wildberries и «Онлайн Трейд.ру»

Заказать SIM-карты Yota теперь можно на маркетплейсе Wildberries и в интернет-магазине «Онлайн Трейд.ру». На двух площадках доступна как курьерская доставка, так и пункты самовывоза: в «Онлайн Трейд.ру» 322 пункта, в Wildberries – 6658 пунктов.

Ярослава Грин

Интернет и ИТИркутск

13223

29.04.2020

Юные монголы создали игру, в которой нужно сражаться с коронавирусом

Во время карантина два мальчика родом из Монголии создали веб-страницу и мобильную игру "2020 AR War", основная цель которой – обезвредить коронавирус. Игра доступна для бесплатного скачивания в App Store.

ivan.off

Интернет и ИТОбществоМонголия

3346

22.04.2020

Консультанты Yota стали работать в салонах связи «МегаФон»

Yota начала предоставлять услуги в салонах связи «МегаФон» в нескольких регионах. Клиенты смогут получить консультацию или приобрести услуги связи Yota офлайн, как и прежде, несмотря на вынужденное закрытие некоторых точек продаж.

Ярослава Грин

Интернет и ИТИркутск

15562

21.04.2020

Yota открыла продажи SIM-карт в Merlion

Yota начала продажу SIM-карт для смартфона в партнерских сетях широкопрофильного дистрибьютора Merlion. Теперь продукт Yota для смартфона доступен на сайтах ритейлеров «Ситилинк», «Позитроника», а также многих других, входящих в партнерскую сеть Merlion.

Ярослава Грин

Интернет и ИТИркутск

11276

17.04.2020

Самоизоляция с Yota: модем на дом, интернет без перебоев

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

Ярослава Грин

Интернет и ИТИркутск

16062

13.04.2020

Yota даёт возможность бесплатно обмениваться сообщениями в роуминге

Yota обнулила трафик мессенджеров в роуминге. С 19 марта клиенты мобильного оператора могут бесплатно обмениваться текстовыми сообщениями в WhatsApp и Viber в международном роуминге при отсутствии средств на счёте.

Ярослава Грин

Интернет и ИТИркутск

54468

20.03.2020

Yota запустила рекламную кампанию #хозяинтарифа  

Yota запустила новую рекламную кампанию #хозяинтарифа. Её цель – рассказать пользователям о том, что в Yota отсутствуют фиксированные тарифы, которые лишают клиентов выбора, навязывая определенное количество минут и ГБ, а также различные ненужные опции.

Ярослава Грин

Интернет и ИТОбществоИркутск

11770

27.02.2020

Смарт: Бабр для умных

Новые ПДД: тонировка, «островки» и средства индивидуальной мобильности

Вслед за корректировкой регламента по приёму экзаменов на водительские права обществу явили новые изменения в правила дорожного движения. Проект ПДД с поправками разработали совместно Минтранс и ГИБДД. Ранее на SmartBabr: Будет сложно.

Алиса Беглова

Интернет и ИТРоссия

1949

16.09.2020

Гарантированный доход: путь к тунеядству?

Бывший премьер-министр России Дмитрий Медведев предложил ввести в России гарантированный доход.

Алиса Беглова

Интернет и ИТРоссия

3932

09.09.2020

Номерок блатной - три семёрочки

В России с 1 января 2021 года может появиться электронный сервис резервирования и регистрации понравившегося «красивого» номера для автомобиля через портал госуслуг. Претендентам на самые желанные номера предложено биться за них в открытых электронных аукционах.

Александр Егоров

Интернет и ИТРоссия

4336

07.09.2020

Главные киберугрозы-2020: фишинг, шпионы, трояны и бэкдоры

Специалисты международной компании Group-IB, специализирующейся на предотвращении кибератак, назвали самые распространённые киберугрозы первого полугодия 2020 года — то есть как в тот отрезок времени, когда в России и по всему миру бушевала пандемия.

Алиса Беглова

Интернет и ИТРоссия

1075

19.09.2020

Пронесло: законопроект о блокировке «экстремистских» сайтов без суда отклонён

Недавно стало известно, что в Госдуму внесён законопроект, предполагающий блокировку «экстремистских» сайтов оперативниками. Без суда и следствия. На основании мнения одного эксперта. Правительство РФ, к счастью, не поддержало данную инициативу. Как же власть упустила такую прекрасную возможность?

Александр Егоров

Интернет и ИТРоссия

977

18.09.2020

Лица Сибири

Таевский Павел

Банько Сергей

Самаринов Андрей

Савин Александр

Игнатенко Виктор

Константинова Оксана

Бурлаков Александр

Дубровин Сергей

Савин Олег

Шарапов Юрий