Контест окончен; надеюсь, вам понравилось. 1465 человек решило хотя бы одну задачу — по-моему, отличный результат. Увы, все 6 задач не дались никому; мои поздравления ShadowSong, который выиграл контест, решив 5 из них с наименьшим штрафом!
290A - Таинственные строки
Год назад было экспериментально установлено, что отсутствие условия не мешает участникам благополучно решить и сдать задачу, а автору экономит немножко усилий по его написанию. Сегодня мы еще раз в этом убедились. Можно было бы сочинить длинную и запутанную легенду о том, как вас, юного, но многообещающего программиста, вызвали в Белый дом и дали важнейшее задание: составить интерактивный список президентов Соединенных Штатов от основания страны до наших дней. В ней могли бы фигурировать долгие и напряженные поиски нужной информации, погони, перестрелки, умирающий напарник, последними словами которого было "Восьмой — Van Buren, не забудь... вывести Van, просто Buren... не пройдет..." Но зачем? Трех примеров и любимого поисковика (из соображений политкорректности не буду уточнять, какого конкретно) вполне достаточно, чтобы определить нужную зависимость между входными и выходными данными: порядковый номер N — фамилия N-ого президента США, а также найти все нужные для этого данные.
290B - QR код
Условие, состоящее из одной картинки, — это уже любопытнее. Функций, переводящих пару чисел в одно число, по трем примерам из условия можно придумать довольно много — начиная с "0, если числа одинаковой четности, и 1, если разной". Чтобы не перебирать их все, придется поискать подсказку в картинке — то есть в QR-коде. Любой онлайн-дешифратор кодов подскажет, что в картинке спрятана ссылка на текстовый файл, состоящий из 0 и 1. Внимательное изучив файл, можно узнать в нем тот же QR-код, записанный поблочно — 1 для черных блоков и 0 для белых. Подсказка, указывающая на себя саму... Так может, это и есть условие? Входные данные от 0 до 32, а сколько блоков в картинке, 33x33?
И впрямь, в задаче требовалось вернуть цвет блока изображения, находящегося на пересечении заданных строки (первое число) и столбца (второе число). А текстовый файл дан в основном для того, чтобы избавить догадавшихся до этого людей от генерации этого массива.
290C - WTF?
Условие! Наконец-то настоящее текстовое условие! Почитаем... Что за черт?
Чтобы расшифровать это условие, нужно было либо вспомнить, кто автор контеста и как сильно я люблю всякие странные языки программирования, либо выделить из текста несколько ключевых слов и поискать их в интернетах. HAI и KTHXBYE совершенно однозначно указывают на то, что этот текст — код на забавном языке Lolcode; остается разобраться, что он делает, и продублировать это на каком-нибудь нормальном языке. Сделать это можно опять же двумя способами: найти список команд языка и вчитаться в код, или найти онлайн-интерпретатор языка и попробовать запустить программу на разных наборах данных.
Если бы в этой задаче была настоящая легенда, она звучала бы примерно так. Вам дана последовательность дуэлей игрового персонажа с противниками; в каждой дуэли он либо побеждает, либо терпит поражение. Рейтинг персонажа определяется как отношение "количество побед" / "общее количество дуэлей". Вычислите максимальный рейтинг, который когда-либо был у персонажа.
290D - Orange
Еще одно условие-картинка, выдержанная в замечательной оранжевой гамме. Как может правильно предположить человек, умудренный опытом участия в контестах моего авторства, это тоже язык программирования, только еще менее известный, чем обычно: Baltie. Интерпретатор языка существует только под Windows, да и программу в него так легко не скопируешь, так что проще было бы, наверно, угадать примерный смысл пиктограмм-команд. Ящички — переменные, стрелки — оператор присваивания, пиктограммы цикла и if-then-else подписаны, вот с остальными придется повозиться...
Можно, впрочем, пойти и другим путем и попробовать угадать задание по единственному примеру. Содержимое строки явно не меняется, меняется только регистр некоторых букв... Немного шаманства — и мы узнаем, что нужно перевести в верхний регистр первые N букв алфавита и в нижний — все остальные.
290E - HQ
В порядке исключения над решением этой задачи надо было подумать два раза: до и после того, как становилось понятно условие. Краткий экскурс в описание языка HQ9+ позволит узнать, что команды H и Q выводят сообщение Hello, World! и текст программы, соответственно. Логично будет предположить, что язык HQ состоит из этих же двух команд, и делают они примерно то же. Чтобы продвинуться дальше, придется попотеть — гипотезы типа "дан исходный код программы, верните Yes, если его вывод будет иметь четную длину" оказываются несостоятельными. На самом деле все наоборот: дан не исходный код, а вывод программы (команда H выводит сообщение H, без лишних букв), и нужно выяснить, существует ли программа, которая сгенерирует такой вывод. Увы мне, всего несколько человек смогли это отгадать и оценить всю красоту задачи. Мои поздравления ShadowSong, который первым сдал эту задачу в начале второго часа контеста!
Как решать? Прежде всего нужно сделать несколько полезных наблюдений. Если в исходной программе nH символов H и nQ символов Q, то каждая H выведет одну H, а каждая Q — nH H и nQ Q. Значит, количество Q в выводе должно быть точным квадратом (можно и 0), и можно либо сразу сказать, что вывод не генерируется никакой программой, либо узнать nQ. Аналогично количество H в выводе равно nH * (nQ + 1), и либо вывод некорректен, либо мы узнаем nH.
При небольших ограничениях этого было бы уже достаточно, чтобы решить задачу перебором всех возможных перестановок известного количества H и Q и сравнением вывода, сгенерированного каждой перестановкой, с заданным. Увы, ограничения до 10^6 не оставляют шанса такому подходу, и приходится думать дальше. Найдем первый символ Q в выводе; очевидно, он появится там в результате выполнения команды Q. Половина H до этого момента появится в результате выполнения этой же команды Q, вторая половина — в результате выполнения отдельных команд H. Значит, мы можем либо забраковать вывод, если количество H до первой Q нечетно, либо узнать количество H, с которого начинается исходная программа. Аналогично поступаем с хвостом вывода и узнаем количество H, которым исходная программа заканчивается.
И наконец, последний шаг. Первые nQ символов Q в выводе появляются в результате выполнения одной и той же команды Q. Значит, если взять первый и nQ-ый символы Q, фрагмент вывода между ними и нужные префикс и суффикс, состоящие из H, мы как раз и получим исходную программу! Остается только проверить, что эта программа действительно генерирует нужный вывод (отличия могут быть после первых nQ символов Q).
290F - Жадный Петя
Эта задача принадлежит перу Gerald и раскрывает несколько другой аспект чувства юмора команды авторов :-) Всю вторую половину контеста мы все сильнее и сильнее огорчались, что недооценили сложность задачи, но буквально на последних минутах Deamon сделал рывок и все-таки сдал ее, за что ему мое личное огромное спасибо :-)
В этой задаче требовалось угадать, какое именно неправильное жадное решение придумал Петя для задачи о нахождении гамильтонова пути (а то, что оно неправильное, становилось понятно из третьего же примера). Петя использовал довольно известную жадность:
- Будем хранить граф списками смежности.
- Удалим из графа все кратные ребра и петли.
- Отсортируем вершины в списках, по степени вершины. Сначала вершины с меньшей степенью, потом с большей. Вершины с одинаковой степенью сортируются по номеру.
- Переберем вершину, из которой начнется путь, и далее пытаемся из текущей вершины перейти в порядке соответствующего списка смежности в еще непосещенную вершину.
Если алгоритм не находит цикла, выводим "No".
Недавно в школе читали Weblish English, стал расшифровывать 290C - WTF?, ошибся немножко, жаль однако..
if(foo * quz == bar * baz)А я в Е гуглил что-то про бродячего енота, нашёл какого-то поцыка в твиттере с таким ником, который как раз 13 часов назад что-то написал, а до этого писал около года назад... На прогопедии нашёл ссылку на какого-то Хорьковского или Харьковского, который писал что-то про автостоп, подумал, что бродячий енот намекает на это... Минут за 10 до конца узнал, что бродячий енот — это тот, на кого всё сваливают. Сказать, что я огорчился — сказать мало. У меня был истерический багет
[whine] В условии задачи E вранье, язык HQ в том виде, в котором он использован в задаче, не является подмножеством HQ9+,
с его помощью нельзя вывестинаоборот, с помощью HQ9+ нельзя вывести одну только букву H.Hello, world!, например.[/whine]
Было весело, спасибо!
Спасибо за Е! Красиво. И я надеюсь что ещё много нерешивших, прочитав анализ, всё равно смогли оценить красоту задачи.
Дак по сути же, условие задачи довольно очевидное: гуглим HQ9+, смотрим на входные данные в нашей задаче, смотрим на выходные, кодим =) Главное — хотя бы на минутку предположить, что то, что нам дано — не исходный код.
Ну я например посмотрев на задачу в которой дано ничего и надо вывести Yes/No решил, что там не очень много тестов. И ее надо сдать подбором ответов. Логично же, нет?
А по-моему ограничение на длину теста (до 10^6) намекает на то, что тестов может быть довольно много.
И, честно говоря, я даже не предпологал до этого контеста, что с помощью памяти можно такой подбор устраивать=)
Какой stderr? o_O? Я памятью подбирал.
Ого круто! Я так понимаю, что таким образом можно числовые тесты от 0 до 262144 выводить) А если еще временные интервалы выполнения программы задействовать:)
Ну вот не совсем. Там с погрешностью плохо. Я пробовал передавать много — ничего не получилось. А вот по 4 бита спокойно.
извиняюсь, понял=)
Просто, все 3 хэш-решения, что я глянул, выводили хэш в cerr/stderr, и я подумал, что в нём соль...
Та же фигня, 80 попыток чуть больше чем за час и 36 пройденных тестов.
Там же в середине контеста с +1 сдали, какой подбор? :) Это меня, например, окончательно убедило, что решение должно быть разумное и очень логичное.
Спасибо за контест! А сколько было тестов в F? Интересно, сколько времени не хватило havaliza, чтобы послать первоапрельское решение первоапрельской задачи?
45, оставалось совсем чуть-чуть =)
Блин, мне аж обидно за это решение. Оно просто великолепно.
Протупив и отказавшись от поисковика в С, интуитивно отгадываем синтаксис... Меня это позабавило, в следующий раз советую дать задачу на это, то есть использовать в условии свой собственный язык)
Ага, русский аналог Шекспира, например... :)
Ну он так себе русский :)
Не ну, я и говорю, специально для контеста сделать русский аналог.
В этом списке президентов есть один пропуск:
http://en.wikipedia.org/wiki/List_of_nicknames_of_United_States_Presidents
Следующая ссылка позволяет этот пропуск исправить:
http://en.wikipedia.org/wiki/List_of_children_of_the_Presidents_of_the_United_States
Автор контеста знал об этом?
Автор контеста брал список с http://en.wikipedia.org/wiki/List_of_Presidents_of_the_United_States, логично рассудив, что уж эта-то статья выверена как следует :-)
Я вообще из украинской версии брал :)
А что означает первая картинка в последней строчке задачи D?
Какое-то шаманство с выводом на печать — без этого не выводилось. В интерпретаторе нет подсказок на пиктограммах, а разбиралась я с этим два года назад, так что в точности установить не удалось :-)
honestly problems were very nice :) I count the days for next year's contest :D
I ended up solving problem 290C the hard way, by trying to interpret the language myself. I didn't even think it was a language actually defined somewhere!
Definitely was very fun and a unique challenge. Looking forward to another like it soon. I wouldn't complain if this type of contest were thrown in the mix every once in a while and not just on April Fools.
Love to solve 'Orange'... Feel like puzzle solving :)
Почему в задаче C входные данные во всех тестах содержат только числа от нуля до одного? В условиях задачи на обоих языках говорится, что они от нуля до девяти. Конечно, это первоапрельский контест, но, если я правильно понимаю лолкод, он вполне справляется с большими числами.
О, и теста из одного-единственного нуля тоже нет.
В основном потому, что все числа, кроме первого, — это результаты дуэлей, 0 для проигрыша и 1 для победы. Можно было бы, конечно, ввести понятие "особо убедительной победы" со значениями от 2 до 9, но лично мне это кажется перебором. А тест из одного нуля — это отсутствие дуэлей вообще, появляется неоднозначность определения ответа в этом случае.
290A - Таинственные строки list USA president
https://en.wikipedia.org/wiki/List_of_presidents_of_the_United_States_by_previous_experience#:~:text=5%20References-,By%20the%20numbers,people%20have%20served%20as%20president.