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

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

Разбор задач

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

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

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

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

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

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

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

Думаю, Железо победит...

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

    Когда я также пошутил, у моего комментария было +200 :о)

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

      никто еще прочитать не успел, это его железо заминусовал)

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

      Видимо количество плюсов не всегда зависит от содержимого поста :)

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

Необычные условия это как в 167D, т.е. не сразу понятно, чего вообще от участника хотят?
Меня этот контест уже радует

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

Я заинтргован =)

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

Какбэ ничего, что первого апреля отключат интернет?

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

    Правильно. Anonymous ведь обещали отключить интернет всему миру, проведя атаку на 13 корневых DNS-серверов мира в знак протеста против SOPA.

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

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

      Кэш DNS спасёт мир :)
      Жаль никто не узнает, что интернет упал :) Все будут думать, что это у них что-то сломалось, а рассказать об этом в интернете и узнать, что эта проблема глобальна, не получится :)

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

Помню меня порадовал первоапрельский контест [user::snarknews]. Там все буквы в условиях были заменены на знаки вопроса, и я понял все шесть задач, а уж сколько сдал не помню, но 4 точно :). Отличная практика. Спасибо за подготовленный контест.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Решения можно сдавать на любом языке, поддерживаемом Codeforces — если, конечно, иное не оговорено в условии задачи :-)

Т.е. некоторые задачи придется писать только на одном языке?

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

    Nickolas только не делайте этого, прошу вас, поймите, не всем нравятся SLR...

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

      Что-то мне подсказывает, что чтобы там не было, кому-то подобный вариант не понравится. А учитывая намек что не все задачи можно будет сдавать на любом языке, и то что контест составляет Nickolas, есть ощущение что на разные задачи — разные языки будут.

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

        Изкчить 5 языков за 2 часа... Интересная перспектива. Я за :-)

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

        "Для разнообразия я решила раскрыть дуальную тему — необычных условий."

        Будет тот же SLR, только surprise language будет не в решениях, а в условиях.

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

    Или это шутка к первому апреля?

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

Awesome !

Thanks.

Good luck everyone. ;)

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

Good luck everyone~

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

I registered for the contest and was surprised to see 'Enter' button immediately. I was able to see problems A, B and after that it gave error. Seems its corrected now.

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

    I am sorry to say..but may be you have been fooled ..After all its the April Fool Day contest :)

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

Я думал будет что-то типа 100 контеста :)

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

    Конечно, можно было бы объявить, что сотня лучших участников получит именные футболки, а после контеста признаться, что это была шутка... Но это была бы какая-то неправильная и невеселая шутка.

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

      Но можно было бы объявить, что сотня лучших участников получит именные футболки, а после контеста признаться, что это была шутка... И раздать две сотни именных футболок!

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

где же кнопка "Мне нравиться"?

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

Here are the tasks -> http://bit.ly/H66EsD

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

So many people want to see tasks before contest begins :)

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

Спустя 4 часа...: "Контеста не будет! Это была шутка, с 1 апреля!" xD

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

You make me curious :D

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

Алгоритмы!

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

прикольные задачи:) особенно задача F!!!

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

С и G взорвали мне мозг.

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

Сейчас окажется, что это была шутка и раунд рейтинговый :D P.S. Спасибо отличный контест! Хоть и опоздал...

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

Интересно, а что курит Nickolas?

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

Как решать С, G и H ?

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

    C: cin>>n; ll sum = 0; for (i=1;i<=n;i++) { cin>>a; sum += a * i; } cout<<sum;

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

    G — фибоначчи-подобная последовательность, H — просто рекурсивно фрактал порядка a строится и ищется координата точки с номером b, C — это это сумма частичных сумм в суффиксах.

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

Спасибо за прекрасный контест!

Ждем разбор=)

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

Я тупой, как решать А?
И да, спасибо за прекрасную F! Жаль, что ровно на секунду опоздал с отправкой >.<

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

какой язык был секретным?

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

    INTERCAL

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

      ВОТ КАК ЭТО МОЖНО БЫЛО ПОНЯТЬ!???

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

        По ошибкам компиляции =)

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

        Очевидно, вбиваем в запуске любую строку, получаем вывод RANDOM COMPILER BUG ON MY WAY HOME. Дальше гугл... Но вывести намного сложнее чем понять по-моему

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

        1) Ввести рандомный текст в запуск.

        2) Загуглить ошибку компилятора.

        3) ???

        4) PROFIT!

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

        Я понял это раньше, чем дошел до этой задачи, увидев странный язык, отправив в него случайный код и увидев ошибку компиляции. Ошибки INTERCAL ни с чем не спутать)

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

Стало лень думать... Хочется разбора!

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

very veRY VERY FUN CONTEST :)

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

Может кто объяснить 2 вещи : 1) Как на Intercal'e вывести Intercal? 2) Как прочитать условие F?

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

Классно получилось! +71 на F, но в конце АС.

Какой язык был под secret ?

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

I love this contest. but when I arrived the contest is almostly finished. :(

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

Thanks for the contest,it was great fun. I am keen to know what was the secret language and how you figured it out? reading problem C i though it could be chef but it didn't work.

Also how you solve D without brute force submitting?

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

    Binary search submitting?

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

      Try to compile something, google the error message. EDIT: I didn't figure this out during the contest :P

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

        Thats amazing!! I thought codeforces placed this error massage so that we cant find what the language is seeing the error. Double thanks to problemsetter,that was a great idea!!

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

    Basically, for E, you have to put INTERCAL into binary, and then you can copy hello world programs off google and change the values. EDIT: sorry, you wrote E For D, you can just randomly submit stuff

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

    As for the figuring out part, just send anything. The compiler output from the compilation error will tell you what language it is.

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

    I've just tried a greedy algorithm to determine a "good" strategy to solve D. My result (based on 3^5 cases) is 11 submissions in worst case (but only 1 case) while average 5-7 submissions in about 60% cases.

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

Horrible contest! And the author is really mean>_<

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

Что за язык-то был? Я проверил си и Ook. ... Дальше понял, что бинарный поиск тут не работает :(

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

    INTERCAL, только вывести на нём что-то веселее, чем угадать, что за язык :)

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

F я смог расшифровать только в английском варианте, немного нечестно :)

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

    Мне сразу почудилось нечто вроде шифра Цезаря, зашел на сайт СПбГУ, расшифровал :)

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

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

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

    фювбюая — мвю

    когда я увидел первые слово — повторение заголовка (т.е, скорее всего, некоторое название), сразу подумал, что второе слово "это" ...Дальше — немного медитации над русским алфавитом — и всё становится понятно :)

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

    Ну теоретически чтобы расшифровать, достаточно было только предположить,что используется подстановочный шифр(Отображение букв текст -шифр 1 к 1),и даже не обязательно сдвиг, и совсем не обязательно знать какую-либо часть текста. Можно посчитать частоты букв и слогов в каком нибудь нормальном тексте и в заданном шифре и заменить каждую букву в шифре на наиболее соотвествующую в тексте по частоте.

    Часто это работает даже для нескольких предложений, правда времени ушло бы полконтеста.

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

Вопрос про Intercal: там играло роль, в каком регистре выводится название языка?

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

    Как вообще можно было понять вывод на этом языке? Прочитал все доступные материалы, все равно не понял. А, еще настоящее название INTERCAL — "Compiler Language With No Pronounceable Acronym". Те, кто сдал, поделитесь — что нужно выписать?

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

    да. Язык INTERCAL, да и название "НЕИЗВЕСТНЫЙ ЯЗЫК" как бы должно было намекать:Р

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

    Да,правда чтобы поменять регистр всех букв сразу достаточно поменять первый сдвиг:)

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

А, ок, увидел ответ)

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

Дорешка будет? ;-)

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

Можно забанить турков в топе которые все как один в D выводили с первой попытки захардкожденные значения, как под копирку, да еще и почти одновременно

upd: Ах да, контест понравился :)

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

Классный контест! С INTERCAL вышло жестоко — по ошибке компиляции гуглится сразу, а вот вывести "INTERCAL" — задача совсем нетривиальная. 40 минут думал, что уже почти ее решил и остался только вывод :)

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

A few of exotic problems. However, I like them. Thanks, Nickolas.

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

This contest is very interesting.

In Problem E, we get very angry CE message: "DO YOU EXPECT ME TO FIGURE THIS OUT?", and it took me about half an hour to modify the "Hello world" into "INTERCAL".

In Problem H, it's much difficult than I think. I try to solve this by writing the code in Herbert (http://herbert.tealang.info/) then simulate it. But I can't solve it until the end of contest.

By the way, is there the editorial to this contest?

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

    I used divide & conquer but got WA4 too. I downloaded KADR's solution & run all possible test cases (to compare output) but still can't find mistake T_T

    Edit: It looks like the orientation of the polyline change when we change a... what an unexpected behaviour :(

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

    It will be here, working on translation now.

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

      Thank you!

      Oh my god, now I know that the statement in Problem C is a programming language named Chef. I think people without knowing this language nearly can't solve this problem.

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

Как не криво делается H? Я написал функцию draw(k, a[][]), которая по порядку фрактала и матрице перехода рисует очередную линию и за O(b) находит нужную координату, но получил WA4. Да и выводил переходы долго, но это уже мой тупняк.

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

Very Nice Contest. I think it was Something like IQ test Thank you and looking forward for another one...

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

the best contest ever :) , thank you all

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

Ешка клевая) 1. Гугл по ошибке компилинга — узнаете язык. 2. Гугл по прогопедии Николас) — узнаете как написать Hello, World! и то, что надо юзать ленту Тьюринга. 3. Вспоминаете кф раунд 96) http://codeforces.me/contest/132/problem/A и тупо копируете код генератора)

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

Very Nice Contest. I think it was something like IQ test. Thank you and looking forward for another one...

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

Really fun :D I love it :D

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

Системное тестирование? Мне кажется, или нас обманывают? :D

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

The real programming problem is only on problem H

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

Сегодняшний контест напомнил мне про rankk.org

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

Разбор в студию! Контест вообще норм, мне понравилось) Правда, несмешно было, но всё равно) Мы сегодня с утра с друзьями говорили что-то вроде: "О, сегодня шутки шутить будут на КФ, наверняка будут задачи вроде "Дан инпут, выведите аутпут" или "дфлывпралд лдфрывалдо фолдыв рфдвролдра фодвар."" Угадали, чо)

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

In problem D it is possible to guess the input number by inserting something like:

Sleep(N * 200); // Wait for 200 * N ms

And looking into running time during wrong attempts. That should decrease the number of attempts.

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

April fools contest, problem A-B-D-E-F

I liked this contest. It was very fun, and sort of practice for the strange part of ISPC.

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

Nice tasks

A. a1 + reverse(a2)

B. 1 + 6 * a * (a — 1)

C. sum(i=1 .. a_0) i * a_(a0 — i + 1)

D. if (input == 5) print 1 else print (input % 3) + 1

E. write "INTERCAL" in the language INTERCAL (use wikipedia to find 'Hello world' program and learn how to write strings using INTERCAL)

F. finding 'an', 'a', 'the', 'number', 'output' in the text deduce the code -> task: output n-th prime number pn which reverse is also prime (and different from pn)

G. repeat { a1, a2 <- a2, a1 + a2 } a3 times, output a1

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

А можно включить дорешивание?

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

still system testing 100%, no final results ;)

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

Спасибо за контест. Получилось круто)

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

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

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

Жаль в H не было разумного семпла с нечетным первым числом...

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

Заметил баг в таблице результатов:

Если во время контеста участник по какой-нибудь задаче (кроме E) отправил решение на каком-нибудь обычном языке (например, C++), но забыл изменить в чекбоксе язык программирования (при отправке) с "Secret" на "GNU C++ 4.6", то, естественно, получал Compilation Error. Когда он этот же код отправлял снова, указав "GNU C++ 4.6", и получал Accepted, то в таблице результатов появляется "+", но при наведении мышкой появляется всплывающая подсказка "Secret" вместо "GNU C++".

Например, 6 место, cmd задача F.

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

Думаю, на такие контесты (и схожие с ними SLR от Nickolas) должно быть ограничение по возрасту 18 лет. Нельзя травмировать психику детей такими языками, как INTERCAL :O

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

will there be something similar this year?