Недавно делал маленький контест в полигоне. Почти все понравилось - после выкачивания package мне было достаточно разархивировать данные в тестирующую систему и поменять xml-файл с настройками.

А не понравилось вот что: файлы с тестами, генерируемые на полигоне, имеют вид 01 и 01.a, ..., 99 и 99.a, а затем 100 и 100.a и т.д.
Если тестов больше 100, то я не могу задать в xml-ке с настройками маски входных и выходных файлов, т.к. у некоторых тестов имя состоит из двух символов, а у некоторых - из трех. Приходится писать скрипт для переименования, что не очень удобно.

В связи с этим есть предложение: добавить в полигон настройку имен файлов с тестами. Думаю, это очень несложно.

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

Если вы считаете, что мат в один ход найдет абсолютно любой человек - эти позиции для вас!

   

Пожалуйста, пишите свои ответы под спойлерами!

Обновление. Вроде народ не против, так что вот еще две боянистые задачки. Правда, теперь их сложность - VERY HARD.

3). Партия из начальной позиции закончилась 5 ходом черных, когда конь съел ладью и поставил мат. update: Известно, что первый ход белых был 1. e4. Восстановите партию.

4). Из начальной позиции партия продлилась 4 хода и закончилась матом белым. Белые ходили 1. f3, 2. Крf2, 3. Крg3, 4. Крh4. А как ходили черные?

Сначала в общих чертах о раунде.
Моими задачами в этом раунде были задачи A-div2,  B-div2,  C-div2/A-div1,  E-div2/C-div1,  D-div1. Сначала я хотел провести на них контест исключительно для второго дивизиона. Однако затем мы решили провести общий раунд. MikeMirzayanov подготовил задачу про молоко, anonymous предоставил задачу E-div1. Кроме того, по напутствию RAD были усложнены Аземблер и Флаги.
По-моему, получилось неплохо для первого раза (кроме небольшого фейла с рамочками). Во всяком случае, мне понравилось. Правда, я не ожидал, что Аземблер и Флаги решит так мало народу.

А теперь разбор.


Задача A (div.2) - Восстановление пароля

Текст задачки был актуален чуть более года назад, когда свирепствовал вирус piggy.exe :) Но в то время у меня не было возможности где-либо опубликовать эту задачу.

Вот пример решения: http://pastebin.com/hMV0NcjN

Задача B (div.2) - Друзья

Возможно, некоторых смутила формулировка утверждения. Однако именно так оно звучит в книжке, из которой я его нагло скопировал :)

Т.к. вершин в графе всего 5, достаточно написать 3 вложенных цикла for (каждый цикл соответствует одной вершине графа) и проверить, что ребра между этими вершинами имеют одинаковый цвет.

Пример решения: http://pastebin.com/gswaxGmM

На самом деле ответ FAIL будет лишь в одном случае - когда в графе ровно 5 ребер и они образуют цикл длины 5 (как в тесте 2). Вот шуточное решение на эту тему: http://pastebin.com/09T0ixrJ

Задача A (div.1) / C (div.2) - Рамочки

Самый простой способ решить задачу --- проверить, что ответ 1 или 2, а иначе вывести 3. Давайте рассмотрим, в каких случаях ответ меньше 3.

Итак, пусть ответ - единица. Значит, все требуемые папки можно выделить за одно движение мышкой. Вот эти случаи (в скобках показан тест для этого случая):

• первая и последняя папки находятся в одной и той же строчке (21 5 7 9);
• первая папка находится в самом левом столбце, а последняя - в самом правом (21 5 1 15), этот случай покрывает случай m = 1;
• первая папка находится в самом левом столбце, а последняя имеет номер n (21 5 6 21). Сюда же относится тот случай, когда надо выделить вообще все папки.
  

Теперь рассмотрим все случаи, когда ответ равен 2:

• первая и последняя папки находятся в соседних строчках (21 5 8 14);
• первая папка находится в самом левом столбце (21 5 6 13);
• последняя папка находится в самом правом столбце (21 5 4 15);
• последняя папка имеет номер n (21 5 4 21);
• столбец, в котором расположена первая папка, находится непосредственно справа от столбца, в котором расположена последняя папка (21 5 3 12). Мне кажется, это самый хитрый случай в задаче.
  

Если ни одно из этих условий не выполняется, то ответ равен 3.

Пример решения: http://pastebin.com/8QRytzzF

Еще эту задачу можно было писать сжатием координат и перебором, но психов среди нас нет :)

Задача B (div.1) / D (div.2) - Окончание сессии

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

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

Остается это просто написать - ничего сложного, как мне кажется. Единственный момент - сравнивать вещественные числа надо, используя EPS. Без этого можно получить WA на тесте 12 (50 1000 49), где из-за неправильного сравнения программы некоторых участников выдавали NO, тогда как решение существует.

В обсуждении ниже показано, что ответ можно считать в целых числах, если взять объем бутылки, равный mn. А при выводе будем делить на mn и умножать на w. Ни одно из трех решений жюри до этого не додумались :)

Пример решения: http://pastebin.com/HG5Nrxne (оно уже не такое красивое, как предыдущие, но понять, как мне кажется, можно)

Задача C (div.1) / E (div.2) - Аземблер

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

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

Чтобы при этом не возникло TLE, надо хранить максимальную глубину рекурсии (собственно, это первое число в ответе), в которой мы достигли ответа, и не ходить глубже. Также не следует ходить в те состояния, где мы получаем число, большее n. Если же мы получили ровно число n, и наша глубина рекурсии меньше минимальной, запомним ответ и скопируем его в безопасное место, чтобы потом вывести.

Еще есть улучшение, которое состоит в том, чтобы перебирать числа по убыванию (так работает быстрее), но ограничения в 5 секунд хватало, чтоб перебирать числа как угодно.

Были и другие подходы к решению этой задачи: поиск в ширину и перебор для конкретного ответа.

Вот два решения: обычный перебор (http://pastebin.com/Z6ZF36st) и перебор для конкретного ответа (http://pastebin.com/viiYF9CB).

Задача D (div.1) - Флаги

Сначала я расскажу, как считать ответ для одного числа (т.е. L = R), а потом переделаю решение для общего случая. Дело в том, что изначально задумывалась как раз формулировка с конкретным числом полос N, и только потом мы было принято решение усложнить задачу. Мое решение не сильно оптимально (задачи все-таки не "фиолетовые", как оказалось, а некоторые решения - "фиолетовые" :) ). Я видел коды других участников, и у них все попроще.

Итак, задача для фиксированного N.

Обозначим за число флагов с N полосами, считая симметричные флаги разными. Посмотрим, как, имея эту информацию, получить ответ на задачу.

На первый взгляд, достаточно поделить на 2. Но, посмотрев повнимательнее, можно обнаружить, что это верно только для флагов, не являющихся палиндромами. Например, флаги-непалиндромы WBWB и BWBW симметричны, и надо учитывать только один из них --- здесь деление на 2 законно. А вот флаги-палиндромы, такие, как WBW, симметричны сами себе, поэтому деление на 2 для них приведет к ошибке.

Посмотрим, что можно сделать. Во-первых, заметим, что при четном N корректных флагов-палиндромов вообще не существует, т.к. иначе в центре встретились бы 2 полосы одного цвета, что невозможно, поэтому для четных N формула верна.

Эта задача решается формулой включений и исключений. Только многие получили TLE, т.к. они почему-то не прогнали максимальный тест на своем компьютере (да, прогоняйте макс. тесты на своем компьютере!).

А остальные почувствовали, что что-то тут не так, и запоминали ответы для небольших N и конкретного a_i в массив, чтобы в дальнейшем их не считать. Например, можно посмотреть решение победителя турнира rng_58, там все очень четко и понятно написано. Вот еще один пример такого решения: http://pastebin.com/4kcfJdAi

Более подробно об этой задаче написал ее автор anonymous вот в этом посте: http://codeforces.net/blog/entry/2216. У него есть решение, укладывающееся в ограничение по времени при N ≤ 10¹⁵, что, скорее всего, не сделало бы ни одно из решений, отправленных во время контеста. Это решение можно посмотреть в дорешивании.

Всем привет!

Меня зовут Алексей Дергунов, и я рад представить первый "фиолетовый" раунд в истории Codeforces. Надеюсь, что задачи покажутся вам не слишком "фиолетовыми" :)

Благодарю за большую помощь в подготовке контеста следующих людей:

• MikeMirzayanov (Михаил Мирзаянов)
• RAD (Артем Рахов)
• Connector (Макар Красноперов)
• anonymous (Анонимус)
• Delinur (Мария Белова)
  

• 1 место - rng_58
• 2 место - hos.lyric
• 3 место - ilyakor

• 1 место - pmnox
• 2 место - muliguishou
• 3 место - craus