Здравствуйте, извините за неканоническое использование шаблона "Спортивное программирование и...".

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

1. TopCoder

В свое время (то есть до 2006 года, к которому относится самая свежая из найденных мной задач) на TopCoder промелькнуло несколько задач о ЯП.

Roco — язык очень простой: с одной стороны, достаточно эзотерический, то есть все, что о нем нужно знать, помещается на две страницы, а с другой, достаточно емкий, чтобы на нем можно было писать сравнительно сложные программы, не ломая голову над каждой элементарной операцией, как в Brainfuck. Одна только возможность обращаться к переменной по имени (числовому, но все-таки имени) — уже подарок для программиста :-)

188A - Шестиугольные числа

Как обычно, первая задача проверяет способность участника выполнять базовые арифметические действия языка и решается по аналогии с примером.

iin [0]
mul [1] [0] 2
dec [1]
mul [1] [1] [0]
iout [1]
ac

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

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

Язык сегодняшнего раунда — Roco, малоизвестный эзотерический язык с особым подходом к циклам и подпрограммам. Программы на нем выглядят несколько громоздко, особенно по сравнению с Befunge, но это компенсируется их сравнительной простой и понятностью. Вот пример программы, вычисляющей сумму двух заданных чисел:

iin [0]
iin [1]
add [2] [1] [0]
iout [2]
ac

Информации об этом языке в интернетах очень мало: мне известны только авторский сайт языка и статья в Прогопедии с прокомментированными примерами программ.

Интерпретатор у языка тоже ровно один, авторский. Для запуска интерпретатора необходимо иметь установленный C++ (и автор, и мы используем g++), скомпилировать код интерпретатора в исполняемый файл и запускать программы командой "roco program.roco". Скачать интерпретатор (исходник и скомпилированные файлы) можно здесь.

Финалы Challenge 24 наконец закончился, и, как обычно, я спешу поделиться впечатлениями о нем. Спонсор впечатлений — команда Progopedia в составе: Андрей Максай (maksay), Сергей Дымченко (kit1980) и я (Nickolas). Такие вещи лучше всего писать сразу после контеста, пока еще свежи впечатления и эмоции. Можно, конечно, начинать писать их еще во время соревнования (в прошлом году я так и сделала — все равно к ночи от меня толку было мало), но в этом году мы были настроены бодро и боролись за баллы до последних минут контеста, поэтому блогу пришлось подождать.

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

Я очень люблю формат соревнований Surprise/Unknown Language Round. Теоретически я люблю в них участвовать, но на практике чаще получается, что я их провожу. Что же в них мне так дорого?

1. Необычность. В определенный момент (который у меня настал достаточно быстро) традиционные соревнования приедаются и сливаются в одно размытое пятно. Если задуматься, из 70 СРМов и десятка CF-раундов, в которых я участвовала, я отчетливо помню от силы пару штук — SRM с задачей MooresLaw (ах, какие челленджи там были! И это, кажется, мое единственное первое место в комнате), отборочный раунд TCO, в котором я прошла за счет сданного в последний момент 500pt, GCJ-раунд из тех времен, когда он проводился еще на базе TopCoder, в котором я безнадежно застряла в парсинге условия и так и не добралась до собственно решения... и, пожалуй, все. С марафонами дело обстоит получше, не в последнюю очередь из-за того, что их было меньше, и каждому отдельно взятому раунду уделялось больше времени и внимания. Но все-таки необычные соревнования оставляют самые яркие и долгоживущие впечатления.

2. Соответствие моим навыкам и умениям :-) Языки, в которых нет циклов, строк или еще чего-то такого же привычного, не шокируют меня и не угрожают моему психическому здоровью. Нет, конечно, существуют языки, которых я опасаюсь, но их на ULR пока не попадалось и вряд ли попадутся.

Мои поздравления KADR, который первым решил все 8 задач!

171A - Загадочные числа - 1

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

Что же до самой задачи, то в ней требовалось найти сумму первого числа и зеркального отображения второго.

171B - Звезда

Говорят, лучше один раз увидеть, чем десять раз услышать или сто раз прочитать. В этой задаче мы решили это проверить и заменить традиционное текстовое условие одной-единственной картинкой. Как и в предыдущей задаче, такой формат условия не вызвал затруднений — как минимум 645 участников узнало звездные числа (последовательность http://oeis.org/A003154 в OEIS), то есть количества шариков, из которых можно сложить шестиугольную звезду определенного размера. После этого оставалось только закодировать формулу их вычисления —

Разбор задач

Возможно, некоторые из вас уже заметили в календаре соревнований контест с интригующим названием "Первоапрельский". На английском оно звучит лучше — April Fools Day Contest, что как бы намекает на его нетипичность, несерьезность и даже некоторое ехидство. При желании можно было даже угадать автора — самого ехидного из имеющихся, то есть меня :-)

Я вообще люблю нетипичные контесты — Surprise/Unknown Language, в котором решения нужно писать на необычном языке, Time Limit Exceeded, в котором решения пишутся на обычном C, но необычным образом... Чаще всего в таких контестах раскрывается тема необычных решений. Для разнообразия я решила раскрыть дуальную тему — необычных условий.

Итак, в этом раунде вас ждет несколько необычных задач и два часа времени на их решение. Раунд будет нерейтинговым (еще бы!), и проводиться он будет по схеме ACM ICPC (без взломов, положение в результатах определяется количеством решенных задач и набранным штрафным временем). Решения можно сдавать на любом языке, поддерживаемом Codeforces — если, конечно, иное не оговорено в условии задачи :-)

Сразу предупреждаю — для успешного и радостного участия в контесте требуется чувство юмора, совместимое с моим! В конце концов, это первое апреля. Удачи!

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

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

162A - Пятиугольные числа

Почти точно такая же задача, как 130A - Шестиугольные числа с раунда про Befunge. Чтение и вывод данных делается в точности как в примере, а кроме них, используются только базовые операции со стеком.

USING: io kernel math math.parser ;

readln string>number
dup 3 * 1 - * 2 /
number>string print

Factor отличается отлично развитой системой встроенных библиотек, которые избавляют программиста от решения очень и очень многих рутинных задач. Поэтому после первой тривиальной задачи шли несколько штук, которые решались "в одну строку" -

Раунд окончен. Мое искреннее восхищение победителю в общем зачете nab, который решил все 10 задач за 1 час 25 минут, и поздравления победителю в официальном зачете winger, повторившему этот подвиг за 1 час 52 минуты (мне кажется, не стоило так уж сильно за него беспокоиться, а?). Официальные результаты будут объявлены позже, после удаления явных читеров.

Разбор задач здесь.

Язык этого раунда — Factor, стековый функциональный язык с развитой системой встроенных библиотек.

Ну что, делимся впечатлениями, признаемся, кто участвовал, в какой команде и что нарешал? Ужасно не хватает более детальной информации по контесту — стран участников и общего балла явно недостаточно :-)

Список команд:

И немного впечатлений от Progopedia в моем лице.

Итак, разбор задач. Я старалась подбирать задачи так, чтобы каждая из них раскрывала какой-то аспект языка — особенность или часто используемый глагол. Если участник его узнавал/нагугливал, задача должна была стать очевидной.

153A - A + B

Сразу скажу, что приведенный в посте пример работет и в Custom test, и в ideone, и локально — если вводить числа по одному на строку и (внимание!) после второго тоже поставить перевод строки. Этот последний перевод строки не отображается в тестах, но на самом деле он там есть! И для COBOL это важно. Все тесты на Codeforces сгенерированы аккуратно, с переводом строки всюду, где нужно, поэтому при сабмите проблем возникать не должно было.

Самая очевидная особенность COBOL — это хранение чисел в десятичной записи заданной программистом ширины, со всеми последствиями. В данном случае внимание фокусировалось на том, что по умолчанию число выводится фиксированной ширины, при необходимости дополненное спереди нулями. От этих нулей и предлагалось избавиться.

Раунд окончен, надеюсь, вам понравилось. Разбор задач здесь.

Язык этого раунда — COBOL (диалект COBOL85), один из старейших языков программирования (1959 год "рождения", то есть вдвое старше меня). Несмотря на почтенный возраст, до сих пор активно используется, но не в спортивном программировании, так что для присутствующих должен стать сюрпризом :-)

Задача "A+B" (числа A и B заданы в отдельных строках) решается вот так:

       IDENTIFICATION DIVISION.
       PROGRAM-ID. SOLUTION.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 A        PIC 9(10)   VALUE ZEROES.
       01 B        PIC 9(10)   VALUE ZEROES.
       01 STR      PIC X(10).

       PROCEDURE DIVISION.
         ACCEPT STR
         MOVE STR TO A
         ACCEPT STR
         MOVE STR TO B
         ADD A TO B
         DISPLAY B
         STOP RUN.

На днях на сайте Quora меня попросили ответить на вопрос "What is it like to be a problem writer for programming competitions?". Первым пришел в голову ответ из одного слова, потом подтянулся более развернутый, потом вспомнилась очень характерная история, хм, и еще об этом нужно бы упомянуть... На второй странице я поняла, что это уже не ответ, а полноценная статья, а на третьей — решила поделиться этим шедевром с подготовленной аудиторией, то есть с вами.

Итак, каково же это — писать задачи для соревнований по программированию?

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

А что, кто-нибудь планирует завтра участвовать в TLE? Минус, конечно, что в этом году участие индивидуальное, а не командное, лично мне в хорошей компании было веселее, но контест и сам по себе забавный — на те познания в языке C, в наличии которых в приличном обществе признаваться как-то даже неловко :-)

Итак, разбор задач. Сразу уточню, что задачу MikeMirzayanov не угадал никто (неплохо мы замаскировались, а?) — это была задача C про переборчивую корыстолюбивую принцессу. Собственно, с этой задачи раунд и начался, все остальные я придумала уже для продолжения темы.

148A - Средство от бессонницы

Общее количество драконов D может быть достаточно небольшим, поэтому задачу можно решать без затей, перебором драконов от 1 до D и проверкой каждого дракона отдельно. Сложность решения — O(D).

Приветствую,

Завтра, а местами уже сегодня (2 февраля в 20:00 по московскому времени) состоится Codeforces Round #105 для второго дивизиона.

Любите ли вы сказки? Нет, любите ли вы мои сказки так, как люблю их я? Если да, то вам обязательно понравится! Если нет, надеюсь, что тоже понравится.

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

Спасибо MikeMirzayanov за пожертвованную задачу (кто угадает, которую из пяти?) и RAD за помощь в подготовке задач.

Удачи на раунде!

Формат Unknown Language Round завоевывает популярность и за пределами Codeforces: Chaos. Правда, задач всего шесть - меньше, чем делала бы я, и сами задачи проще, но для начала неплохо. Даже жалко, что мы не студенты :-)

P.S. Знаю, я опять пишу слишком поздно для рекламы контеста, но раньше я просто не успела - я и на сам-то контест опоздала на пятнадцать минут.

P.P.S. Мой отчет о контесте: Chaos Chef.

На днях открылась регистрация на замечательный контест венгерского происхождения Challenge24. Лично я его очень люблю - пожалуй, в списке моих любимых контестов он уступает только TopCoder Open. Это вполне естественно - все любят контесты, на которых их приглашают на онсайт в какие-нибудь интересные города :-) Поэтому я решила немного его прорекламировать (и даже сделать это заранее, чтобы не получилось как с CodeSprint).

Участие в контесте командное, причем в команде должно быть ровно три человека. Ограничений студент-не студент нет, равно как и на страну проживания, только что английский знать надо. Единственное требование - все участники должны предъявить подобающее резюме. Кстати, для поездки на онсайт можно заменить одного участника команды по сравнению с составом на момент онлайн-раунда. Очень гуманно, если учесть вопросы виз-денег-"да не поеду я, отстаньте со своими глупостями" :-)

Проводится контест в два этапа: Electronic Contest (онлайн отборочный раунд длиной 5 часов) и собственно финалы-онсайт (24 часа, но об этом я стараюсь не вспоминать) в Будапеште, на которые приглашают лучшие 27 команд по результатам онлайн раунда плюс 3 команды, занявшие первые места в прошлом году. Сразу уточню важный момент: в отличие от общеизвестных турниров, организаторы не оплачивают дорогу и проживание. Впрочем, бумажное приглашение для визы присылают исправно, если попросить как следует.

Codesprint закончился, можно обсудить задачи. Лично я полностью решила четыре штуки:

• Picking Cards - произведение ((количество карт номиналом < i) - i + 1) по i от 1 до N.
• Coin Tosses - рекурсия по количеству орлов, которые осталось выбросить с текущего момента; за один шаг рекурсии рассматриваю один бросок монеты, и получаю либо орла (переход к "осталось выбросить на одного орла меньше"), либо решку (переход к известному матожиданию числа бросков, нужных для того, чтобы выбросить N орлов подряд - 2^N+1-2). Немного начудила - считала не в целых, а в Decimal (Python), так что преобразование в строку получилось страшноватое, но прошло.

Я тут отвлеклась ненадолго от всяческих спортивно-программных вещей и сделала новогодний квест. Правила и сообщения об исправленных багах (буде таковые объявятся) тут. А комментировать можно и здесь :-)

С наступающим!

Update. Разбор заданий квеста.

A. HQ9+

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

В субботу 3 декабря состоится Codeforces Beta Round #96, мой первый классический раунд на Codeforces. Чтобы несколько сгладить переход от неизвестного языка к известным, я сделала раунд тематическим, и тема эта, разумеется, языки программирования :-)

Спасибо MikeMirzayanov, maksay и RAD за помощь в подготовке задач.

Удачи на раунде!

P.S. Баллы за задачи: первый дивизион — 500-1500-1500-2000-2500, второй дивизион — 500-1000-1500-2500-2500.

P.P.S. Разбор задач здесь.

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

A. Шестиугольные числа

&:2*1-*.@

"Утешительная" задача, требующая только понимания принципа работы со стеком. Дублируем прочитанное число n, верхнюю копию умножаем на 2 и вычитаем из результата один — теперь в стеке два числа n и 2n - 1. Перемножаем их и выводим на печать.

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

Язык этого раунда — Befunge, очаровательный двухмерный эзотерический язык программирования. Как для эзотерического, он достаточно лаконичен и удобен в использовании. Так, например, задача "A+B" (числа A и B заданы в отдельных строках) решается вот так:

&&+.@

Для знакомства с языком можно почитать авторскую документацию (в некоторых браузерах отображается с ошибкой) и примеры программ на Rosetta Code. На русском есть статья в Википедии и статья в Прогопедии с разобранными примерами программ.

Система тестирования использует интерпретатор befungee, реализующий диалект Befunge-93. Для запуска интерпретатора необходимо иметь установленный Python (версии 2.6 или около того — в версиях 3.* интерпретатор работать не будет). Следует скачать файлы befungee.py, boards.py и funge.py, сохранить их в той же директории, что и исходные коды ваших программ, и запускать программы командой python befungee.py <имя программы на Befunge>. Обратите внимание на встроенный дебаггер (опция запуска --debug --delay=100), позволяющий отслеживать перемещения указателя инструкций в ходе выполнения программы.

В качестве локальной альтернативы можно использовать интерпретатор WASABI, требующий для запуска Java. Скачайте архив с интерпретатором, распакуйте его и запускайте среду разработки командой java -jar "Wasabi v1_4.jar" <имя программы на Befunge>.

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

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

Сложнее всего мне пришлось в Лас-Вегасе. Туда я летела со строгим напутствием сестры будущего мужа: привезти ей футболку с надписью "Las Vegas". Кроме того, меня неотступно преследовал печальный взгляд самого будущего мужа, которому неожиданно не дали визу в США; а в выигранной поездке на TCO нет особого смысла без визы. Так что программа шоппинга у меня получалась непривычно насыщенная.