В этом году 3 человека решили все задачи, что ровно на 3 больше, чем в 2014! А вот участников, решивших хотя бы одну задачу, было всего 1097.
656A - Da Vinci Powers
В этой задаче надо было определить последовательность целых чисел по двум примерам и названию задачи. Это оказалось неожиданно сложно, гораздо сложнее, чем мне казалось. Поиск по OEIS показывает, что хотя последовательностей, содержащих числа из примеров, довольно много, ровно одна из них имеет отношение к Леонардо да Винчи (а если сразу искать "Da Vinci", последовательностей находится всего две). http://oeis.org/A221180 — последовательность степеней двойки, вычисленная да Винчи с ошибкой и записанная в "Codex Madrid I".
656B - Scrambled
Одно слово: typoglycemia. Существует миф (не подтвержденный никаким известным исследованием) о том, что люди легко читают текст даже с перемешанными буквами, если первая и последняя буквы слов остатся на своих местах. Мне показалось забавным проверить на маленькой (и очень необъективной) выборке спортивных программистов. Судя по результатам, текст действительно читается на ура :-)
Расшифрованное условие становится историей о двух соседях по комнате, которые пытаются найти справедливое разделение домашнего хозяйства. (Забавно, но факт: идея этой задачи навеяна не реальными событиями, а спектаклем.) "Вы согласовываете два массива целых чисел M и R, нумеруете предстоящие дни (включая текущий) последовательными целыми числами (номер текущего дня равен нулю), и вы моете посуду в день N тогда и только тогда, когда существует такой индекс I такой, что N % M[I] = R[I], в противном случае ваш сосед моет посуду... Вычислите долю дней, в которые вы моете посуду"
Чтобы найти точный ответ, следует найти наименьшее общее кратное чисел в массиве M LCM. Бесконечное число дней можно разбить на одинаковые блоки размера LCM, поэтому доля всех дней будет такой же, как доля первых LCM дней. Пройдем по дням 0..LCM-1 и для каждого дня проверим, кто моет посуду (поскольку каждый элемент массива M не больше 16, LCM не будет превышать 720720, и это будет достаточно быстро).
Гораздо проще получить приближенное решение: проитерируем по большому количеству дней (не связанному с LCM) и вычислим ответ на основании их — абсолютная погрешность будет достаточно маленькой, чтобы решение прошло.
656C - Without Text
Еще одна задача без условия (и еще одна задача, оказавшаяся сложнее, чем ожидалось), но в этой хотя бы есть картинка! К этому времени любой человек с опытом участия в соревнованиях моего авторства должен узнавать программу независимо от того, на каком языке она написана. В данном случае это Sanscript, потоковый визуальный язык программирования. Картинка представляет собой лишь часть программы, тело главного цикла, но в ней содержится большая часть логики программы.
Отдельные блоки программы достаточно хорошо аннотированы, и разобраться, что же этот код делает, должно быть не очень сложно. Вся мешанина блоков и стрелочек вычисляет сумму номеров в алфавите букв в верхнем регистре во входной строке, минус то же самое для букв в нижнем регистре. Небуквенные символы игнорируются.
656D - Rosetta Problem
Мне нравится так много необычных языков программирования, что одного языка на задачу иногда недостаточно. Но можно ведь использовать несколько языков в одной задаче! К сожалению, большинство участников Codeforces не разделяют мою страсть к языкам программирования, и задача, хоть и тривиально решающаяся, оказалась самой сложной во всем контесте.
Каждый абзац условия (включая картинку) представляет собой короткую программу на одном из эзотерических языков программирования. Если опознать каждый из них, найти его интерпретатор и выполнить программу, можно получить фрагмент условия:
- Print number (Brainfuck) — http://ideone.com
- of ones in (Malbolge) — http://www.malbolge.doleczek.pl/
- base 8 (Piet) — http://www.rapapaing.com/blog/?page_id=6
- notation of a (Befunge) — http://www.quirkster.com/iano/js/befunge.html
656E - Out of Controls
Эта задача была первой и последней, в которой было бы четко сказано, что надо сделать: написать решение к несложной задаче на графы без традиционных ключевых слов циклов и условных переходов.
Решать эту задачу можно было как угодно, в зависимости от используемого языка программирования:
- Честно написать рекурсивное решение.
- Добавить дополнительные символы в запрещенные слова (/*..*/ или переносы строки в C++ или сфромировать строку, содержащую программу, и выполнить ее при помощи eval в Python).
- Использовать встроенные функции итерирования map, each и т.д.
- Я подозреваю, что пользователи Haskell вообще не заметили никаких ограничений на код :-)
656F - Ace It!
Эта задача была придумана kit1980.
Один из самых популярных способов решить задачу в Первоапрельском контесте — поискать как следует в OEIS. В этой задаче были заданы номера последовательностей в OEIS, и, найдя их на сайте, можно было заметить, что ответ — это первый элемент последовательности. Осталось только закодировать это, с учетом того, что Codeforces не дает решениям доступа к внешним сайтам, а ограничение на размер кода — 64 KB...
На этом моменте приходит пора кричать "С первым апреля" и смеяться. Забудьте про OEIS. Эта задача была тщательно составлена именно для того, чтобы натолкнуть на такой ход мысли (и у нас получилось!), но настоящее решение гораздо, гораздо проще. Входные данные представляют карты игрока в blackjack, и нужно вычислить минимальную сумму очков за нее. A — туз, 1 очко (минимальная сумма карт, представленных цифрами — 12, и если туз считать за 11, игра заведомо проиграна), цифры 2-9 соответствуют отдельным картам, а пара цифр 10 представляет собой, очевидно, десятку.
656G - You're a Professional
Эта задача — отсылка к прекрасному рассказу "Совещание" (http://alex-aka-jj.livejournal.com/66984.html). Ваша задача проста, но чекер, он жа заказчик, все время выдвигает новые требования. Сначала вам надо переписать решение на любом другом языке (независимо от исходного языка). Новое решение оказывается слишком длинным, и вам приходится его сокращать (опять же, независимо от исходной длины). Наконец, чекер требует добавить котенка (просто допишите слово kitten и сократите остальной код еще немного). Как ни странно, это оказалось гораздо проще, чем расшифровать эзотерические языки программирования!
Oh, I was sure, that in D second language was Befunge, but tested interpreters freezed.
A is probably the most frustrating problem I ever seen on Codeforces.
After reading the previous contest's problem statement and tutorial I figured out that only OEIS can save us :D
Except for Problem F.
E is the best problem i have ever seen.... :D
Wait, does G consider C++ and C++11 to be different languages? What about MS C++ and GNU C++?
Please help me. I dont understand an editorial of A.
I think our sense of humor are compatible!
Nice contest!
Really nice problems, I got fooled by F :)
Was it intentional that the first page in google search for "malbolge interpreter online" gives segmentation fault for the provided code? Only the second result (the one you point to) returns answer. BTW I didn't know what is the last language but this part of statement was unnecessary.
Without the last piece I interruptted "Print number of ones in BASE 8" as
print oct(raw_input().count('1'))[1:]There are indeed only two possibilities, though.
No.
The order of search results depends on the person, I think the one I link to from the editorial was the first one for me. I guess Malbolge is not standardized enough to be portable cross-implementations :-)
Some c++ functional-style solution of E: 17101307
You invented for_each(start, end, function), does you?
I was not sure it's not banned :) Also it's not that trivial to generate start and end (they should be iterators, not numbers).
the most boring problem is A!!!
E
Add some other characters in the middle of each forbidden keyword (/*..*/ in C++ or @ in Python with eval)
Do you mean sth like this:
But I got CE from my compiler...
Click
For D I actually went to google image search to search for that image-language. No luck
E written in C++ with a little bit ASM 17107204
In D, I tried two Malbolge interpreters: this and this, and none of them can execute the second program. Is it really correct?
I know it's a terrible thing for a software developer to say, but it worked for me with http://www.malbolge.doleczek.pl/, and it was the first interpreter in my search results. Next time I'll have to pick a more standardized language — or a different kind of joke altogether :-)
http://www.matthias-ernst.eu/malbolge/malbolge.c works for me. (under x86_64 gcc version 5.3.1 20160307 (Debian 5.3.1-11))
F is such troll.. How did you even find such sequences starting with 21, 22, 23?
In the announcement thread someone wrote that OEIS provides an archive with all sequences. From there — probably a script on local files.
Search for the given string on OEIS. That's how I got fooled.
Given small constraint in E, my first thought was to write 1000 if statements (with C++ conditional operator), similar to this: 17104757. Luckily I gave up midway and found the recursive solution :)
I didn't try this problem, but why we can't simply write Floyd-Warshall by goto loops in C++ ?
Without if statement it's a bit tricky to implement goto loops
that's what I did E-code just a recursion functions instead of 2 loops for input ,3 for Floyd-Warshall and 2 to find the answer
I figure out that he just needs to write some code to print it, but that guy is really a new phenomena.
For me error message in G was misleading. I decided that more modern language is some really modern, and start learning D. But it appears that any other language is appropriate.
In all other respects it was a merry contest!
Next time you can look at Status and see what others are doing.
My first time attempting such a contest, I really enjoyed it :-). Too bad it only comes once a year...
in problem G , why should we add the word 'kitten' !!
And, the checker didn't take my
-=^o^=-for one. So sad.In problem D, I used online Malbolge compiler, but I got RE and i gave up this problem. So sad..
Actually, once I've got the other three parts, "Prnt number ??? base 8 notation of a", I was tempted to check whether it's the number of 0s, 1s, or 2s by just submitting such three solutions.
E was fun using
iota(v.begin(), v.end(), 0)andfor_each(v.begin(), v.end(), [](){}).17115093
What is relation of "@" and eval?
PS: I did it with simple exec: 17101778
Problem F was a good one! I spent half an hour trying to fit the necessary info into 64 KBytes... Feeling foolish :P .
Thank you for the contest! Also, I'm amazed by the flexibility shown by the Codeforces platform in problems E and G.
Can anybody plz tell me why in problem G the word kitten is added in solution How come you get to know to add this word only as this is not mentioned in the problem statement.
You will be given the instruction in the verdict if you click on the "Wrong Answer on Test 1". For this task you are not penalized for these incorrect submissions so you can try as many times as you want.
how pow(2,35)not same as the what it is to be
The sequence is not actually powers of 2, it's what da Vinci believed to be powers of 2, but he made an error during calculations.
How to solve problem G? I have submit it with C++,C,Pascal,JavaScript,JAVA8,but I always get a Wrong answer on test 1
In the list of your submissions, the "Wrong answer on test 1" outcome should be clickable. Click and read what you are expected to do next.