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

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

Этот контест оказался самым популярным за всю историю Первоапрельских контестов: 10343 участников решили хотя бы одну задачу! Набор задач был неплохо сбалансирован — каждую из более сложных задач решило не менее 200 участников, но всего 17 человек решили все 8 задач.

1331A - Is it rated?

Эта задача была задумана как "утешительная", и все равно многие участники просили подсказку — некоторые даже до начала раунда! Если вы все еще не уверены, как ее решать, анонс контеста откровенно намекал, что раунд нерейтинговый, так что ответ — решительное "NO" (в любом регистре, без кавычек) :-)

1331B - Лимерики

В этой задаче было условие, что довольно нетипично для такого типа контестов. Настоящее задание было спрятано в нем при помощи самой простой стеганографии — первые буквы строк составляют текст "TWO FACTORS", то есть "два множителя" (к сожалению, мне не удалось написать эквивалентные лимерики на русском языке). Примеры подтверждали это: задача требовала разложить заданное число на множители и вывести их (в неубывающем порядке, без разделяющего пробела).

1331C - ...И счастливо долго жили и они

Сказки часто заканчиваются фразой "...и жили они долго и счастливо". Название задачи — почти что эта фраза, но со словами в другом порядке. Если проверить условие на другом языен, заголовок будет другой (столь же устойчивой) фразой из 6 слов, с той же перестановкой слов. Входные данные — целое число от 0 до 26-1, что в сочетании с длиной заголовка должно натолкнуть на мысль о двоичной системе счисления. Решение следующее: прочитайте число, переведите его в бинарную строку длины 6, и переставьте биты в том же порядке, что и слова в заголовке (т.е., поменяйте местами второй и шестой биты, а также третий и четвертый).

1331D - Опять?

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

В этой задаче надо было найти остаток от деления заданного шестнадцатеричного числа на 2. Задача не имеет отношения к OEIS, точно так же, как и 656F - Ace It!.

1331E - Смайлик Жордана

Задача основана на Jordan curve theorem, а точнее на этом блог посте. Вам даны координаты пикселя на картинке, и надо выяснить, находится ли он внутри или снаружи области, заданной замкнутой кривой.

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

1331F - Элементарно!

Oтвет YES или NO подсказывает, что нужно определить, является ли данное слово "элементарным". Казалось бы, элементарно, Ватсон! — но тот факт, что "HOLMES" дает ответ "NO", а "WATSON" — "YES", запутывает ситуацию. На самом деле использовалось другое значения слова "элементарно", имеющее отношение к периодической таблице химических элементов. Слово было "элементарным", если его можно было записать с использованием только символов элементов: Ge-Ni-U-S or W-At-S-O-N.

1331G - Lingua Romana

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

Условие этой задачи — исходный код на Perligata. Если у вас получится его запустить на разных примерах (или перевести с латыни!), вы можете узнать TPK алгоритм. После этого можно реализовать его с нуля или подсмотреть реализацию на RosettaCode.

1331H - It's showtime

И название задачи, и сообщение об ошибке, которое вы получите при попытке запустить какой-нибудь случайный текст во вкладке "Запуск", указывают на эзотерический язык ArnoldC — язык, основанный на цитатах Арнольда Шварцнеггера. Вам придется поэкспериментировать с недокументированными фичами языка, например, вводом данных :-) Но функция вычисления остатка от деления дана в документации, и в целом язык не очень страшный — если, конечно, не пытаться делать вещи посложнее, например, массивы!

Разбор задач April Fools Day Contest 2020
  • Проголосовать: нравится
  • +170
  • Проголосовать: не нравится

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

What about problem H

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

The answer for the first problem should be "YES" since it is April FOOLS Day. Like if you agree.

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

    Then it would have been the first time a contestant would have felt a shock after getting an AC xD

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

    Well, if that's the case, they could've taken it even further by updating the ratings and changing it back afterwards.

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

"""You are probably familiar with the fairy tale ending "... and they lived happily ever after". """

NOPE

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

Forever tourist orz

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

Are permutation in title in Russian and English statement consistent?

and(5) they(4) lived(3) happily(2) ever(1) after(0)
and(5) after(0) happily(2) lived(3) ever(1) they(4)

и(5) жили(4) они(3) долго(2) и(1) счастливо(0)
и(5) счастливо(0) долго(2) жили(4) и(1) они(3)

This inconsistency made me recover permutation from samples. I think, something is wrong with Russian statement, because English permutation is same as for samples.

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

    I was confused with it aswell, but thought that english version is tested better and I used a permutation of english words.

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

    Yeah, and the double “и” threw me off anyway.
    And the samples actually allow two different permutations.
    Alright, so the trick this time was to either try both permutations, or look at the statement in English.

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

    That awkward moment when you use Google translate for the Russian version, and then realise "wtf am I doing" xD

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

    Exactly, russian doesn't work correctly.

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

    My bad, sorry about that!

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

    I've believed that Toho only attracts East Asian…… But now I know it would attract everyone, just like Vodka would even attract Patchouli!

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

This This is the Language XD

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

How to find a solution for D? Is it just a random thing you should notice? I did submit x%2 at 9th minute of the contest, but was absolutely sure it's a wrong solution.

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

Мне было лень переводить код в задаче Lingua Romana с латыни, и поэтому я использовал Filter::ExtractSource, чтобы перевести код в обычный Perl.

Правда, ExtractSource вставляет на второй строке в исходник строку use Filter::ExtractSource, из-за чего Perligata не хочет работать. Пришлось изменить так, чтобы два use (первый — use Lingua::Romana::Perligata; для подключения самой Perligata) чтобы он вообще были на первой строке.

После этого получается вполне читаемо:

;for $next (Lingua::Romana::Perligata::__enlist__ ( 1, 11)) { $var = Lingua::Romana::Perligata::getline (*STDIN );
chomp ($var );
push (@seq, $var)}
;
for $next (Lingua::Romana::Perligata::__enlist__ ( 1, 11)) { $var = pop (@seq );
 $aresult = sqrt ( abs ( $var));
 $bresult =  ( ($var ** 3) * 5);
 $result =  ($aresult + $bresult);
if ( (400 >= $result)) {printf (STDOUT 'f(%d) = %.2f', $var, $result);
print (STDOUT "\n")}
;
if ( (400 < $result)) {printf (STDOUT 'f(%d) = MAGNA NIMIS!', $var);
print (STDOUT "\n")}
}

Можно чуть-чуть подправить и сдать сразу на perl'е :)

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

After seeing problem A I was like, why it's not loading completely, but it was something different

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

I think the first question is telling us that my "Plot Twist 2: Contest is rated" will not happen. :)

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

Could someone tell me how to make a image of E consist of "#"" " or "0""1" like tourist?

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

How it feels to participate in fools day contest

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

Can anyone give me the actual code of H?

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

    Here you go: 75151340

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

      Ladies and gentlemen, we got her. Bessie the cow herself outside of Farmer John's barn.

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

Even though I only got 4 problems, I enjoyed this year's April Fools contest much more than last year's. Great job!

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

Вопрос по задаче Е. Подскажите кто-нибудь, как с графического редактора преобразовать пиксели разных цветов в массив нулей и единиц? Спасибо.

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

Contest was Great. Too much lateral thinking involved. This tells me to increase my logical thinking to new level. But contest was fun.

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

I am quite disappointed that it turned out to be a real language in G :( I was deducing the actions based on the common knowledge of latin words, and THAT was actually very entertaining.

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

JettyOller has made 73 submissions to get an AC to problem F! I am amazed! So much effort. Such Perseverance!!!!

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

Most people during the first 15 min of the contest: Busy reading questions and submitting solutions

Me: Furiously typing my login details literally every 2 minutes to try to read a question.

Seriously though, does anyone know what's going on here?

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

better than actual rounds :)

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

This contest made me miss the IPSC, but this contest is way better. Thanks for giving me this interesting experience <3

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

For D, realizing I've found a pattern, I tried to fetch the given OEIS sequence and print the first element of it. The first submission got me RTE. But I kept trying, until I realized, I was fooled.

Submission:

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

Unfortunately, the following didn't work for G: 75134077

Fortunately, you can add converte parameter to the use statement and run locally. It outputs perl code that is almost valid.

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

    I had the same idea too

    Unfortunately it was the only problem I couldn't solve in the contest as I didn't have the setup to run Perl

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

    Yes, we checked that Codeforces doesn't have Perligata installed — that would've defeated the purpose of making you write a little code :-)

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

Someone please,explain H number problem...It is still unknown.

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

    I agree. With large numbers like 100, it seems unreasonable to calculate the double factorial of n when n is too large.

    The solutions that were given seem to be based on the assumption that, for any m > 0 and n > 2:

    n!! mod m = (n x ((n-2)!! mod m)) mod m

    and then calculate by recursion.

    However I am not quite certain about the mathematical truth behind this assumption?

    Edit: it seems the previously stated assumption is not actually true. However the algorithm still seems valid. Here is a readable version of the solution, courtesy of the winner, tourist:

    x = input()
    n = x / 1000
    md = x % 1000
    flag = 1
    res = 1
    
    while n > 0:
        if flag > 0:
            res = res * n
        flag = 1 - flag
        tmp = (res / md) * md
        res = res - tmp
        n = n - 1
    
    print res
    

    I'd simplify the algorithm as such:

    x = input()
    n = x / 1000
    md = x % 1000
    res = 1
    
    while n > 0:
        res = (res * n) % md
        n = n - 2
    
    print res
    

    It seems to work, but I can't figure the mathematical proof behind it. Feel free to comment.