952A - Quirky Quantifiers

Этой задачей я обязана генератору каламбуров JAPE и одной из самых известных его шуток:

What do you call a quirky quantifier? An odd number.

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

952B - Карта кошки

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

Решение предельно простое: погладьте кота! Если ответная реакция — "no", попробуйте погладить другую часть кота, иначе вы можете сразу определить тип. Главное — не увлечься: после седьмой попытки погладить любого кота ему это надоедает, и он отсылает вас, не дождавшись вашего ответа.

Единственное, что я не учла — интерактивные задачи редко встречаются на Codeforces, так что эта задача оказалась гораздо сложнее следующей.

952C - Равиоли-сортировка

Назовем ряд стопок "стабильным", если для каждой пары соседних стопок в нем разница их высот не превышает 1 (т.е. ни один равиоль не собирается соскальзывать в другую стопку). Несложно показать, что если исходный ряд стабилен, то ряд, полученный из него удалением самой высокой стопки, также стабилен. Действительно, удалим из ряда стопку a_i; после этого единственная новая пара соседних стопок — пара a_i - 1 и a_i + 1. Исходный ряд был стабилен, поэтому |a_i - a_i - 1| ≤ 1 и |a_i - a_i + 1| ≤ 1. Но стопка a_i была самой высокой, поэтому a_i - 1 ≤ a_i - 1, a_i + 1 ≤ a_i. Таким образом, разница высот между a_i - 1 и a_i + 1 не превышает 1, и новый ряд также стабилен.

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

952D - Мне повезет!

Вы знаете, как работает настоящая рулетка? Каждый раз, когда вы играете, выигрывает новый номер (даже если вы ставите на один и тот же номер). В этой задаче чекер точно такой же: при каждом запуске решения чекер генерирует новый выигрышный номер. В задаче было два теста, так что выигрышную ставку надо было сделать дважды.

Эта задача требовала немного нестандартного мышления. Очень сложно выиграть, делая ставку на число (хотя я видела решение, которое получило 26 на обоих тестах). Но вам не нужно выиграть крупную сумму, вам достаточно просто выиграть — так почему бы не попробовать ставки с более высокой вероятностью выигрыша, например, красное ("red") или четное ("even")? Чекер поддерживал довольно много ставок, изображенных на картинке в условии, так что надо было просто немного поэкспериментировать.

952E - Сырная доска

Эта задача была придумана на английском языке и многое теряет в переводе: первая строка статьи Chessboard гласит "Not to be confused with cheese board" (в русской википедии такого, увы, нет). Действительно, cheese board, chess board, какая разница?

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

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

952F - 2 + 2 != 4

Эта задача основана на реальном баге в чекере для задачи 784G - Калькулятор BF. К счастью, мы заметили ее до начала контеста, иначе я не смогла бы над ней смеяться :-)

Чекер благополучно проходил по всем символам выражения, накапливая их в переменную "текущее число" и прибавляя или вычитая его из результата. Но в коде накопления текущего числа не хватало проверки на тип символа, и из-за этого знаки плюс и минус тоже считались цифрами текущего числа. В примере "2+2" первое число было вычислено правильно, а в начале второго числа появилась дополнительная "цифра" ('+'-'0') = -5, поэтому второе число было проинтерпретировано как (-5)*10 + 2 = -48. Знак минус трактовался как дополнительная "цифра" ('-'-'0') = -3.

Код с ошибкой:

long long result = 0, cur = 0;
expr += "+";
int sign = +1;
for (char c : expr) {
    if (c == '+' || c == '-') {
        result += sign * cur;
        cur = 0;
    }
    if (c == '-')
        sign = -1;
    if (c == '+')
        sign = +1;
    // bug: + and - signs are accumulated into the number
    cur = cur * 10 + (c - '0');
}

952G - Язык-паззл

"Язык-паззл", описанный в этой задаче, — ортогональный Puzzlang, малоизученный вариант языка Puzzlang.

Существует множество подходов к генерации программ на этом языке.

Разумеется, способ, показанный в примере, — не самый простой и выбран вполне целенаправленно :-) В принципе его можно доработать — использовать треугольные блоки для увеличения значения в ячейке памяти, затем сдвигаться в нужную ячейку и выводить ее значение на печать. Это требует внимательности при работе с несколькими символами, значениями, не являющимися точными квадратами (треугольник соответствует увеличению на квадрат его высоты, и да, знак \$ в примере тоже выбран не случайно) и т.д.

Авторское решение использует гораздо более простой подход. Самая простая команда на этом языке, декремент, представляет собой отдельный X без соседей. Поскольку ячейки памяти в Brainfuck хранят значения по модулю 256, из любого значения можно получить любое другое, просто вычтя из него единицу нужное количество раз. Сгенерированной программе достаточно всего двух столбцов и двух команд: '-' (декремент), реализованный как ".." — newline — "X." и '.' (вывод на печать), реализованный как "X.".

Это решение можно слегка оптимизировать с минимальным усложнением. Код все еще генерирует программы из двух столбцов, но обе команды '-' и '.' записываются как ".X" или "X." в зависимости от предыдущей команды. В итоге символы X, соответствующие вычитанию, расположены в шахматном порядке (по диагонали от предыдущего символа X), а символы X, соответствующие выводу на печать, расположены под предыдущим символом X. Это уменьшает длину программы вдвое.

Еще одно мое решение использовало тороидальную топологию программы вместо того, что значения в памяти хранятся по модулю 256. В программе все еще два столбца и команды '-' и '.' записываются так же, как в прошлом варианте. Последовательность из 2*N команд '+' можно представить как блок из N+1 строк "XX" (со строкой ".." перед ним). Первая строка блока интерпретируется как ",,", но интерпретатор BF проигнорирует эти команды. Каждая строка блока, начиная со второй, интерпретируется как "++". Такой подход генерирует более короткие программы, но требует гораздо более внимательной реализации — мне удалось написать его без багов только с четвертой попытки :-)