Разбор Codeforces Round #126 (Div. 2) [200A - Кино](http://mirror.codeforces.com/contest/200/problem/A) В этой задаче было дано поле размером $n \times m$ и $k$ запросов. Каждый запрос –-- это клетка поля. Нужно было для каждого запроса находить ближайшую к заданной не занятую клетку (при этом ближайшая клетка находится по манхэттенской метрике). После этого найденная клетка помечалась как занятая. В задаче предполагалось решение за время $O(k \cdot \sqrt k)$. Сначала поясним идею решения, затем покажем, как достигается такая временная оценка. Идея решения состоит в следующем. Прежде всего, если $n > m$, то повернем матрицу на 90 градусов (далее будет пояснено зачем). Будем хранить две матрицы $n \times m$, в которых для каждой клетки будем хранить ближайшую свободную клетку слева и справа. Пусть теперь приходит запрос клетка $(x, y)$. Будем перебирать величину $d$ на сколько строчек мы отступим вниз и вверх. Когда мы зафиксировали $d$, то рассмотрим строку, например, $x – d$ (аналогичные действия нужно будет проделать для с...

Full text and comments »

Разбор Задач Codeforces Beta Round #25 <h3>Задача A - IQ Тест</h3>Надо просто посчитать количество чётных и нечётных числ. В данных числах может быть или только одно чётное число, или только одно нечётное число --- надо найти его и вывести его номер.<br><br><h3>Задача B - Телефонные Номера<br></h3>Есть много методов разбить на группы из 2 или 3 цифр. Представим один простой вариант: вывести группы из двух цифр пока останется больше чем 3 цифр:<br><br>&lt;code&gt;<br>for( i=0; i&lt;n; i++ )<br>{<br>&nbsp;&nbsp;&nbsp; putchar(buf[i]);<br>&nbsp; &nbsp; if( i%2 &amp;&amp; i&lt;n-(n%2)-2 ) putchar('-');<br>}<br>&lt;/code&gt;<br><br><br> <h3>Задача C - Дороги в Берляндии<br></h3>Входнные данные --- матрица $D$, в которой $D[i][j]$ явлется кратчайшим расстоянием между городами $i$ и $j$. Если создадим новуюу дорогу между городами $a$ и $b$ с расстоянием меньше чем $D[a][b]$, как обновить остальные расстояния в $D$?<br><br>Пусть матрица $D'[i][j]$ --- кратчайшее расстояние между $i$ и $j$ если добавим в граф новое ребро $ab$. Дл...

Full text and comments »

Codeforces Round #121 Здравствуй, сообщество Codeforces! Очередной раунд Codeforces #121 для вас сделали студенты ФИВТ МФТИ Александр Тимин ([user:AlTimin,2012-05-26]) и Иван Смирнов ([user:ifsmirnov,2012-05-26]). В своем первом раунде мы предложим вам хорошо провести время в старой доброй Берляндии: провести митинг, разогнать митинг, разобраться с главными берляндскими проблемами (обеими!) и многое другое. За неоценимую помощь в подготовке контеста хочется сказать огромное спасибо [user:Gerald,2012-05-26]. Он же является автором одной из задач. Кроме того, мы выражаем благодарность [user:delinur,2012-05-26] за перевод условий на английский язык, [user:Aksenov239,2012-05-26] за вычитку условий и [user:MikeMirzayanov,2012-05-26] за возможность провести контест на замечательной платформе Codeforces. Традиционно, раунд пройдет в обоих дивизионах на частично пересекающемся наборе задач. Информация о разбалловке будет опубликована позже. Мы желаем вам успехов и надеемся, что раунд вам понравится! ...

Full text and comments »

Берляндия? Мне стало интересно -- а откуда пошло упоминать в легендах задач страну Берляндию (Berland)? Гугл по соответствующему запросу ничего кроме олимпиадных задачек не выдает. Может, кто-нибудь из ветеранов знает?

Full text and comments »

Счастливые билеты. Здравствуйте. Как решить эту задачу ? В стране Берляндии очень развит общественный транспорт. Проезд в нем бесплатный, но при этом каждому пассажиру при входе выдают билетик с уникальным номером. Особенно ценятся так называемые счастливые билетики. Билетик называется счастливым, если сумма цифр на четных позициях в его номере равна сумме цифр на нечетных позициях. Васе известно, что билеты выдаются подряд в порядке возрастания номеров. В очередной раз войдя в автобус Вася получил свой очередной билет и тут ему стало интересно, какой существует минимальный счастливый билетик с номером, меньшим номера билетика Васи. Помогите Васе узнать ответ на этот вопрос. Формат входных данных В единственной строке задан номер билетика Васи — натуральное число, имеющее в своей десятичной записи не более 100 цифр. Формат результата Выведите минимальный номер счастливого билетика, который больше номера билетика Васи.

Full text and comments »