A. HQ9+

В задаче давалось описание HQ9+ и спрашивалось, выведет ли заданная программа что-то на печать. Ввиду исключительной простоты языка для этого было достаточно проверить, содержит ли программа хотя бы один из символов H, Q и 9 (с учетом регистра).

B. Unary

У замечательного языка Brainfuck есть диалекты на все случаи жизни; подозреваю, что при желании по ним можно было бы придумать целый раунд (не Unknown Language Round, конечно, слишком уж он известен), но на этот раз я ограничилась только одной задачей.

В решении нет ничего сложного: нужно всего лишь в точности следовать описанию преобразования кода на Brainfuck в код на Unary. В языках со встроенной длинной арифметикой можно действовать напролом: заменить символы каждого типа на соответствующие бинарные коды, преобразовать полученную строку в длинное число и взять его по модулю.

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

C. Лента Тьюринга

Еще одна задача на реализацию, навеянная не менее замечательным языком INTERCAL. Технически чуть сложнее предыдущей за счет выполнения операции "отобразить зеркально байт" и выполнения не описанной процедуры, а обратной. Для i-ого символа входных данных зеркально отображаем его и сохраняем в rev[i], а i-ое число вывода получаем как (rev[i - 1] - rev[i] + 256)%256 (для i = 0 rev[i - 1] = 0).

D. Piet

Замечательный язык Piet отличается от прочих графически-эзотерических языков особо зверским подходом к реализации указателя инструкций — в задаче предлагалась очень упрощенная версия.

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

............
..X----->...
..|XXXXXX...
..vXXXXXX...
............

При этом лично мне удобно было пронумеровать блоки, запомнить их цвета и координаты границ — чтобы два раза не перебирать. Затем я вычислила "функцию переходов" между блоками: для каждого состояния счетчика инструкций выяснить, в какое он перейдет из него за один шаг. Для этого можно проиндексировать состояния счетчика следующим образом. Указатель на текущий блок задается индексом блока, значения указателя направления соответствуют числам от 0 (влево) до 3 (вверх), указателя выбора блоков — 0 (влево) и 1 (вправо). Тогда состояние счетчика однозначно задается числом 8*(указатель на текущий блок) + 2*(указатель направления) + (указатель выбора блоков). Это число находится в диапазоне от 0 до 8*N-1 (N — количество цветных блоков) и изменяется по сравнительно несложным правилам: в начале выполнения программы оно равно 0 (если нумеровать блоки естественным образом, в порядке их нахождения), и если на каком-то шаге переход между блоками возможен, изменяется слагаемое 8*(указатель на текущий блок), а если невозможен, то слагаемое 2*(указатель направления) + (указатель выбора блоков) просто увеличивается на единицу (по модулю 8).

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

E. Черепашка Logo

Задача на динамическое программирование (и единственная на не-эзотерический язык :-)). Подходов может быть несколько. Я хранила два трехмерных массива: самое левое и самое правое положение черепашки, если использовано I команд из списка, сделано ровно J изменений в этих командах и черепашка смотрит в направлении K. Начальное условие — при I = J = 0 и черепашке, смотрящей вправо (начальное направление можно выбрать произвольно) left = right = 0. Правила перехода между позициями: если сейчас выполнится команда T (либо она текущая и изменение не происходит, либо эта команда — результат изменения), координата черепашки сохраняется, а направление меняется на противоположное. Иначе направление сохраняется, а координата меняется в соответствии с этим направлением.

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

Div1 D. Константы на языке Шекспира

Две последние задачи раунда были вдохновлены не менее замечательным языком Shakespeare и по изначальной задумке были одной задачей, которая звучала как "Как вывести заданную последовательность символов с использованием минимального количества прилагательных?". Но потом мы одумались :-) и сделали из этого монстра две задачи.

Напрашивающееся жадное решение (разбить бинарную запись числа на группы единиц, идущих подряд, записать группу размера 1 как одну степень, группу размера 2 и больше — как разность двух степеней) неверно; это можно показать на тесте 4 "10110111": жадное решение вернет 5 ( + 2⁷ + 2⁶ - 2⁴ + 2³ - 2⁰), в то время как существует решение размера 4 ( + 2⁸ - 2⁶ - 2⁴ - 2¹).

Правильное решение основано на следующей идее. Пусть у нас есть фрагмент бинарной записи, содержащий биты, соответствующие степеням двойки от N до M (N < M), в котором K нулей и L единиц. Его можно записать непосредственно через сумму степеней, соответствующих позициям единиц, использовав для этого L слагаемых. А можно записать его как 2^M + 1 - 2^N - ..., где ... — степени, соответствующие позициям нулей, использовав 2 + K слагаемых. Очевидно, что применять второй способ записи есть смысл только к фрагментам, начинающимся и заканчивающимся на единицы (иначе можно применить его к более короткому фрагменту, не содержащему начальные/конечные нули, сэкономив на этом слагаемое) и не содержащих последовательности 00 внутри (иначе можно разбить эту последовательность на две в том месте, где находятся эти нули, и записывать их по отдельности, при этом не увеличив, а то и уменьшив количество слагаемых).

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