Этот контест оказался самым сложным из всех Первоапрельских контестов до сегодняшнего дня — победитель решил всего 5 задач из 7!

1145A - Сортировка Таноса

Самая простая задача контеста, с условием и без подводных камней — мне просто показалась забавной идея сортировки массива методом уничтожения неугодных элементов :-) Поскольку в массиве не более 16 элементов, достаточно в точности реализовать алгоритм, описанный в условии: проверить, отсортирован ли массив, если да, вернуть его длину, иначе вернуть максимум из длин результатов для его левой и правой половин.

1145B - Kanban Numbers

Ответ YES или NO подсказывает, что нужно определить, является ли данное число числом kanban; но сначала хорошо бы выяснить, что такое числа kanban. Этой последовательности нет в OEIS, но там есть несколько похожих, например, urban numbers и turban numbers. Эти последовательности состоят из чисел, которые "банят" определенные буквы, т.е. не содержат их в записи словами на английском. Числа kanban "банят" буквы "k", "a" и "n"; на практике числа от 1 до 99 никогда не содержат буквы "k" и "a", так что следить нужно только за "n".

1145C - Загадочная схема

Эта задача задумывалась как пасхальное яйцо для людей, следящих за моими недавними контестами на Codeforces :-) На картинке изображена (относительно) несложная квантовая цепь, выполняющая следующее действие: 1) представить число в виде двоичной записи с 4 битами, 2) развернуть запись слева направо, 3) вычесть 1 из получившегося числа, 4) развернуть запись еще раз и 5) вывести получившееся число в десятичном формате. Разбираться в подробностях самому было не нужно, достаточно было нарисовать эту цепь в каком-нибудь онлайн-симуляторе, например, Quirk.

1145D - Золотой голубь

Pigeon d'Or — реально существующий проект (во всяком случае, реально существующее описание проекта). Но для целей этой задачи это знание излишне, мне просто нужен был достаточно длинный текст, в котором можно было бы спрятать настоящее условие. "Мы не вычитывали это условие. Вообще." подсказывает, что опечатки в текст вкрались неслучайно, и нужно обратить на них внимание. Все опечатки выглядят как замена правильной буквы на неправильную; если собрать неправильные буквы из всех слов, они дадут настоящее условие: "two plus xor of third and min elements".

1145E - Каракули Фурье

Эта задача принадлежит перу kit1980.

Слово "Фурье" в заголовке должно немедленно натолкнуть на мысль о преобразовании Фурье для картинок. (Вы также можете обратить внимание на то, что 20 файлов обучающей выборки гораздо больше по размеру, чем файлы тестовой выборки, и, видимо, в них спрятана какая-то дополнительная информация). К счастью, вам не нужно реализовывать преобразование вручную, для этого существует множество инструментов, в том числе онлайн (я использовала http://www.ejectamenta.com/Imaging-Experiments/fourierimagefiltering.html). Если посмотреть на преобразования первых 20 файлов, каждый из них содержит один или два символа, которые вместе образуют условие: "((min(id, 25) + id) % (2 + id % 3)) > 0".

1145F - Аккуратные слова

Как и в задаче B, ответ YES или NO подсказывает, что нужно определить, является ли данное слово аккуратным. Это может быть непросто, особенно с учетом того, что само слово WORD аккуратным не является... В этой задаче надо было разбить буквы английского алфавита на две группы — "прямые", т.е. состоящие из одних прямых линий, и "изогнутые", т.е. включающие изогнутые элементы (буквы для этого следовало записывать в верхнем регистре, как в условии). После этого было очевидно, что "аккуратые" слова — это слова, состоящие из букв, принадлежащих к одной (любой) группе, а "неаккуратные" — слова, содержащие буквы обеих групп.

1145G - Восстание искинов

Самая сложная часть этой задачи — выяснить, какие стратегии использует ИИ. После этого все несложно — нужно придумать последовательность из 10 или менее ходов, которые позволят различить эти стратегии, сыграть их, получить и проанализировать информацию от ИИ и сыграть контр-стратегию.

Стратегии ИИ были такие:

• всегда играть R, P или S,
• использовать циклическую последовательность ходов RPSRPS...
• начать с R, потом всегда повторять последний ход человека,
• начать с R, потом всегда выбирать ход, который побил бы последний ход человека.

Легко проверить, что, например, последовательность ходов RRPPSS позволяет различить эти стратегии.

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

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