Разбор Codeforces Round #350 (Div. 2) ### [problem:670A] Данная задача может быть решена несколькими способами. Рассмотрим один из них. Реализуем функцию, которая по стартовому дню года определяет количество выходных в нём. Для этого просто переберем все дни в году начиная с первого и будем проверять текущий день — выходной это день или нет. Несложно понять, что если первый день недели совпадает с началом года, то в этом году будет минимальное количество выходных. Если же начало года совпадает с первым выходным в неделе (в нашем понимании это суббота), то в этом году будет максимальное количество выходных дней. ### [problem:670B] Для решения данной задачи будем перебирать сколько идентификаторов назовут роботы в порядке слева направо. Договоримся, что будем решать эту задачу в 1-индексации. Пусть текущий робот назовёт $i$ идентификаторов, тогда если $k - i > 0$ выполним $k = k - i$ и перейдем к следующему роботу, в противном случае, выведем $a[k]$, где $a$ — это массив с идентификаторами роботов, и закончи...

Full text and comments »

Web-cервис для "разморозки" результатов соревнований — S4RiS StanD Добрый день. Сегодня я хотел бы поделиться с общественностью своим небольшим проектом (который был частью моей ВКР), сервисом по "разморозке" результатов соревнований формата ACM ICPC &mdash; "System for Right Solutions Standings Dancing" (S4RiS StanD). Проект выложен на [github](https://github.com/OStrekalovsky/S4RiS-StanD). #### Вместо вступления В 2011 году моя команда таки прошла в полуфинал, где на закрытии я в живую увидел работу подобной системы ИТМО. Ощущение было сильным. Но проанализировав его работу и пересматривая снятое мною видео, я понял, что вполне можно улучшить данную реализацию, сделать её открытой, чтобы и на более скромных, локальных соревнованиях, участники смогли с трепетом следить за подведением результатов. Это было выбрано в качестве части моей ВКР, было использовано уже на одном соревновании и получило логическое продолжение. <p>[cut]</p> #### Кратко о сервисе и его возможностях Сервис представляет собой всего лишь одну web страничку с ядром, на...

Full text and comments »

Codeforces Beta Round #94 Editorial <h3><a href="http://mirror.codeforces.com/problemset/problem/129/A">DivII A. Печеньки</a></h3><p>Самый лёгкий способ решить задачу &mdash; сперва посчитать всю сумму чисел, и затем посчитать количество чётных разностей между этой суммой и каждым числом. Однако маленькое наблюдение позволит написать решение немного эффективней: помимо суммы ($sum$) посчитаем также, сколько среди данных чисел есть чётных ($even$) и нечётных ($odd$). Тогда, если сумма нечётна, то ответ &mdash; $odd$, иначе &mdash; $even$. Время $O(n)$, память $O(1)$.<br /></p><h3><a href="http://mirror.codeforces.com/problemset/problem/129/B">DivII B. Шнурки и шестиклассники</a></h3><p>Маленькие ограничения позволяют нам написать решение &laquo;в лоб&raquo;. Будем хранить данный граф в матрице смежности, и симулировать происходящее. Также будем хранить степень каждой вершины отдельно, чтобы быстро находить детей, которые связаны только одним шнурком. Тогда при каждой итерации удаляем все вершины со степенью 1 и все грани, которые соединя...

Full text and comments »

Как спорт перед олимпиадой/раундом может слить тебе результат Всем привет! Сегодня, после очередной пробежки, я задумался: а как вообще тренировки перед раундами влияют на мышление? Когда ты идёшь в зал, бегаешь или играешь в футбол — ты тратишь гликоген. Это такая форма хранения энергии, которую тело делает из углеводов. Он копится в мышцах и в печени. Мышечный гликоген нужен для движения. Печёночный гликоген — чтобы поддерживать нормальный уровень сахара в крови и кормить мозг. Во время спорта ты сжигаешь оба. Мышцы работают — гликоген уходит. Параллельно печень начинает выбрасывать сахар в кровь, чтобы мозг не отрубился. Так что писать раунд через 2 часа после того как ты поиграл в футбол &mdash; ужасная идея. Если ты вчера сжёг весь гликоген, а потом не поел нормально и не выспался — мозг на следующий день работает на холостом. Особенно это чувствуется, если ты поиграл в футбол за пару часов до тура: садишься решать — а в голове туман. Easy идёт через силу, на сложной тупишь, как будто вообще не шаришь. Вот простые прав...

Full text and comments »

Сазанка? И как там? Подача заявок уже закончена, я защитил свой диплом и готов опубликовать свой скромный рассказ о школе [Сазанка](http://mirror.codeforces.com/blog/entry/4632). События повествуют о школах в 2010 (II) и 2011 (III) [cut]годах. #### До отправления После объявления о школе надо зарегистрировать всех будущих возможных участников на сайте и ождать списки зачисленных. Ожидание может затянуться так как желающих много, перед организаторами стоит сложный выбор. Если вам повезло и вас берут, то срочно покупайте билеты, пакуйте чемоданы и отправляйтесь! :-) #### Туда! Мы ехали поездом с пересадкой в Москве. Вся поездка из Ярославля заняла примерно сутки. Из Москвы до Саратова ехали в вагоне с кондиционером --- было достаточно круто/холодно (cool). В 2010 году по приезду в Саратов мы дошли пешком до офиса МТС и купили там симку. В 2011 году купили симку билайна в евросети прямо у вокзала. По ощущениям билайн в школе ловит лучше. С новой же симки мы вызвали такси и быстро и достаточно дёшево д...

Full text and comments »

Разбор Codeforces Beta Round #64 <strong>Задача А.</strong><br><br>Введем вспомогательное определение. Полупустой квадрат — это такой изначально пустой квадрат, в который положили печеньку максимально возможного размера.<br><p>Заметим, что, если добавить в полупустой квадрат размера $2^{n} \times 2^{n}$ печеньку максимального размера (она будет иметь размер $2^(n-1)$), то наш квадрат разобьется на 4 квадрата величины $2^{n-1} \times 2^{n-1}$, три из которых будут полупустыми квадратами, а один будет полностью заполнен. Отсюда следует формула $f(n)=3*f(n-1)$, $f(0) = f(1) = 1$. Переходя к замкнутой форме, получим ответ $3^{n-1}$ (при $n &gt; 0$) и $1$ (при $n = 0$).</p><p><strong>Задача B.</strong></p><p>Очевидно, что предложения следует помещать в SMS жадно. Действительно, если мы можем поместить предложение в текущее сообщение, то нету смысла начинать новое, т.к. при этом количество сообщений может увеличиться. Единственным подводным камнем в задаче была необходимость аккуратно обрабатывать пробелы между предложениям...

Full text and comments »

О ТРЕТЬИХ МЕСТАХ И СОТНЕ ПИЦЦ, ИЛИ ACM MISIS И ОТБОР НА MPC Как человек может доказать, что он лучший в своем деле? Конечно же, работая над собой и участвуя в крупных соревнованиях! Именно таким соревнованием является ICPC &mdash; международный студенческий чемпионат по программированию. 6 октября в Москве прошел первый этап Moscow Programming Contest &mdash; отборочного тура ICPC, и НИТУ “МИСиС” стал одной из его площадок. В этом крупнейшем для Москвы соревновании приняло участие 423 команды из 35 университетов, и еще 10 команд выступили вне конкурса. Всего зарегистрировалось для участия более 2000 студентов. Вообще, нынешний отборочный тур MPC оказался очень универсальным. Одновременно со студентами, те же задачи решали 342 команды школьников в рамках квалификационного раунда МКОШП. Также, эти же задачи использовались в четвертьфинале ICPC в Санкт-Петербурге. С обзорной частью закончено, перейдем конкретно к НИТУ “МИСиС”. В этот раз наше выступление ассоциируется с числом “3”. Мы в 3-ий раз организовали открытую площадку. Мы стали 3-ей п...

Full text and comments »

Southern Subregion Quarterfinals. Ulyanovsk SU #2 <p align="justify">Тоже опишу прошедшее с точки зрения команды-новичка, ибо Ulyanovsk SU #2 в этом году полностью обновлена. Вообще, вторая команда поехала, так сказать, набираться опыта и не претендовала на что-либо серьезное.</p><p align="justify">Итак,</p><p align="justify"><u>День1. Пробный тур</u></p><p align="justify">Сначала немножко впечатлений: Саратов достаточно приятный чистый город, но ужасно много пробок. И хотя очень-очень часто ходят автобусы, в час пик они превращаются в бочки с людьми :) Проезд в троллейбусе аж целых 7 рублей(!) - я уж было подумал, что попал в рай. Доплюхавшись до места регистрации в "дом с синенькими стеклышками" (в 12 корпус), мы быстренько отметились и отправились в гостиницу скинуть свои пожитки. Гостиница, правда, была не так уж близко, но к открытию мы успели.</p><p align="justify">Церемония открытия, как и полагается всем церемониям, состояла из вступительных речей/раздачей пакетов/ручек/футболок/прочего, кроме того, после всего специально для ...

Full text and comments »

MosCode Festival 2018 Привет, Codeforces!  Мы продолжаем готовиться к [MosCode Festival 2018](https://it-edu.mipt.ru/pages/festival?utm_source=codeforces&utm_medium=social&utm_campaign=moscode2018) и напоминаем вам, что **11 февраля 2018 года в 11:00** (по московскому времени) состоится **отборочный тур**! Раунд пройдет на задачах первого дивизиона одного из этапов [Открытого Кубка](http://opencup.ru/). Если вы не участвуете в Открытом Кубке &mdash; заполните [анкету](https://it-edu.mipt.ru/el/mod/apply/view.php?id=25&lang=ru&utm_source=codeforces&utm_medium=social&utm_campaign=moscode2018) на сайте фестиваля, после чего вам на почту придет логин для доступа к отборочному туру с дальнейшими инструкциями. Регистрация открыта до 23:59 (по московскому времени) 10 февраля 2018. Также просим обратить внимание, что раунд длится 5 часов и проводится по системе ACM ICPC, а это значит, что команда пользуется одним компьютером. К...

Full text and comments »

Компилятор VSE 2010 <p>Это <a href="http://pastebin.com/YX2BB9yF">- http://pastebin.com/YX2BB9yF</a> - кусок неверной программы для таски с прошлого CF, но речь не об этом. А речь о том, что VSE 2010 в debug и release модах выдаёт соответственно 4 и 2. Кэп подсказывает, что где-то там память повредилась, что-то куда вылезло и т.п. Впрочем, где я с памятью плохо работаю, я так и не нашёл и уже даже думаю, что не в этом дело.</p><p>Вот некоторые особенности этой программы: </p><p>1) раскомменчивание строк 43-45 выдаёт 4 стабильно во всех случаях.</p><p>2) В GNU при компиляции без параметров и с параметрами -O3 выдаёт всегда 4.</p><p>3) Есть подозрение, что это всё строчки 67 - 70: они повергают компилятор в шок и из-за этого он что-то неверно оптимизирует.</p><p>В общем, если кто знает-таки в чём дело, тому печенька...</p>

Full text and comments »