Блог пользователя Nickolas

Автор Nickolas, 9 лет назад, перевод, По-русски

В этом году 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 не разделяют мою страсть к языкам программирования, и задача, хоть и тривиально решающаяся, оказалась самой сложной во всем контесте.

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

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 и сократите остальной код еще немного). Как ни странно, это оказалось гораздо проще, чем расшифровать эзотерические языки программирования!

  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Oh, I was sure, that in D second language was Befunge, but tested interpreters freezed.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

A is probably the most frustrating problem I ever seen on Codeforces.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E is the best problem i have ever seen.... :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wait, does G consider C++ and C++11 to be different languages? What about MS C++ and GNU C++?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help me. I dont understand an editorial of A.

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

I think our sense of humor are compatible!

Nice contest!

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :-)

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Some c++ functional-style solution of E: 17101307

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    You invented for_each(start, end, function), does you?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

the most boring problem is A!!!

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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:

f/*..*/or (int i = 0; i < n; i++);

But I got CE from my compiler...

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

For D I actually went to google image search to search for that image-language. No luck

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

E written in C++ with a little bit ASM 17107204

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

In D, I tried two Malbolge interpreters: this and this, and none of them can execute the second program. Is it really correct?

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

F is such troll.. How did you even find such sequences starting with 21, 22, 23?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    In the announcement thread someone wrote that OEIS provides an archive with all sequences. From there — probably a script on local files.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Search for the given string on OEIS. That's how I got fooled.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I didn't try this problem, but why we can't simply write Floyd-Warshall by goto loops in C++ ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I figure out that he just needs to write some code to print it, but that guy is really a new phenomena.

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My first time attempting such a contest, I really enjoyed it :-). Too bad it only comes once a year...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem G , why should we add the word 'kitten' !!

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In problem D, I used online Malbolge compiler, but I got RE and i gave up this problem. So sad..

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E was fun using iota(v.begin(), v.end(), 0) and for_each(v.begin(), v.end(), [](){}).

17115093

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

@ in Python with eval

What is relation of "@" and eval?

PS: I did it with simple exec: 17101778

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how pow(2,35)not same as the what it is to be

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.