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

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

Увы, из 9 задач контеста никому не далось больше 7 штук. Хотя бы одну задачу решило 1289 человек — меньше, чем в прошлом году, но тоже неплохо. Главное — суммарное количество фана, полученное участниками :-)

409A - Большая игра

Самая Интеллектуальная Игра В Мире на поверку оказалась широко известной камень-ножницы-бумага. До этого можно было догадаться по примерам — допустим, камень () не очень похож на себя, но бумага [] и тем более ножницы 8< — как живые!

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

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

409B - Загадочный язык

При попытке запустить почти любой код на языке Mysterious Language выдавалась пачка ошибок, среди них — "Unclassifiable statement at (1)". Это сразу указывало на язык Fortran; но вот дальше начиналась область сомнений. Фортранов существует немало, компиляторов — еще больше, что именно надо было выводить? По моей задумке, компилятор должен был быть настроен так, чтобы принимать только фиксированный формат программ, а это — указание на FORTRAN 77 (в Fortran 90 появился свободный формат, не требующий отступа перед командами и верхнего регистра). Судя по комментариям, что-то пошло не так, и компилировались программы в свободном формате... В общем, ответ — "FORTRAN 77".

409C - Magnum Opus

Magnum Opus — алхимическое название процесса создания философского камня. Это (а также подпись "Николас Фламмел") намекает нам на то, что в задаче описывается рецепт философского камня, и наша задача — его создать. Если опознать условие как текст на латыни и обратиться к Google Translate за переводом, можно насладиться немалой художественной ценностью письма, в котором матерый алхимик просвещает своего юного коллегу в секретах ремесла. А можно пренебречь литературными нюансами и сразу заметить, что входные данные состоят из пяти чисел, а в рецепт входит пять ингредиентов в заданных пропорциях (пропорции — узнаваемые римские числа перед названиями ингредиентов).

Итого в задаче требовалось узнать, сколько философского камня можно создать, имея в распоряжении заданные количества ингредиентов и отлаженный технологический процесс. Ответ — min(a[0],a[1],a[2]/2,a[3]/7,a[4]/4).

409D - Большие данные

Много фактов с большими числами — еще не big data. Особенно если половина из них неправильные. В самом большом турнире по настольным играм участвовало 43 тысячи игроков в шахматы, в соревновании по математике — больше миллиона человек, а Полковник Мяу, хоть и роскошный кот (фотографии можно посмотреть на сайте Книги рекордов Гиннеса ), не щеголяет метровой шерстью.

В задаче как раз и надо было определить, насколько правдивы приведенные факты, и вывести 1 или 0 в зависимости от того, i-ый факт — правда или не совсем.

409E - Купол

Задача на геометрию (что само по себе уже неплохая шутка :-) ), заданная одной картинкой — полусферой, вписанной в пирамиду. Дополнительную прелесть задаче придает то, что она "обратная" — то есть нужно было не по параметрам пирамиды найти радиус полусферы, а наоборот — по радиусу найти ребро основания a и высоту пирамиды h. Параметры пирамиды принимали только целые значения от 1 до 10, и самым простым способом было перебрать все возможные комбинации a и h, вычислить радиус (как высоту в прямоугольном треугольнике с катетами h и a/2) и проверить, близок ли получившийся радиус к заданному. Некоторые радиусы можно было получить из нескольких пирамид.

409F - 000001

Подумать только, я хотела поставить первой задачу, которую решило меньше 30 человек :-) Мечта автора, задача без условия. По 4 примерам угадать функцию int -> int для 64 вариантов входных данных довольно сложно, особенно если более-менее очевидные варианты типа "наименьшая степень двойки, больше или равная a" оказываются неправильными (в комментариях к раунду приводятся еще несколько изящных, но увы, совершенно неверных гипотез).

На помощь приходят два эвристических правила: 1) даже если в задаче нет условия, у нее есть заголовок и 2) при встрече с любой непонятной функцией int -> int ее стоит поискать в Online Encyclopedia of Integer Sequences. Последовательно применив их, получим последовательность http://oeis.org/A000001. Для решения задачи даже не обязательно разбираться, что такое "группы порядка n" — первые 64 элемента последовательности даны в статье о последовательности.

409G - На плоскости

Эта задача принадлежит перу Skiminok; уж на что я большая затейница, но задавать условие примерами сама бы не догадалась. А здесь оно было не просто задано примерами; точки из каждого примера нужно было отметить на координатной плоскости, получить картинку типа такой

и прочитать условие как 5 + AVG Y (каждый пример задавал одну букву)

409H - A + B наносит ответный удар

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

409I - Накорми голорпа

А эту задачу написал kit1980.

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

Задача — найти лексикографически минимальный набор значений переменных, которые удовлетворяют заданным условиям. По сути, нужно сделать топологическую сортировку. Самый простой способ — в бесконечном цикле перебирать неравенства, выбирать то, которое еще не удовлетворено, и увеличивать ту переменную, которая в этом неравенстве должна быть больше другой. Как только какая-то из переменных вырастает до 10, вернуть false, иначе — останавливаться, когда все неравенства удовлетворены. При данных ограничениях это решение работает быстро.

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

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

В F могло завести не туда эвристическое правило 3: даже если в задаче нет условия, у неё могут быть ограничения. А ограничение в 64 в купе с "бинарным" названием уводило в сторону чего-то близкому к 2^N.

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

Спасибо за разбор всё понятно и точно изложено обязательно дорешаю

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

В F, если честно вбить в поиск OEIS то, что есть, нужная последовательность — третья в выдаче. И тут что-то может щёлкнуть... Я успел ещё пару страниц проскроллить, после этого дошло, что же я увидел :) .

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

Больше всего понравилась задача с неуступчивым чекером. Отдельное спасибо за неё! Кстати, до последнего был уверен, что Nickolas мужского пола.

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

Объясните, почему в последнем примере ответ 0101? Там же в инпуте _>, то есть третья переменная должна быть больше второй.

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

    Переменные, имеющие одинаковое кол-во _ должны иметь одинаковые значения, назовем это кол-во _ "типом". В правой части заданы неравенства именно по типам переменных, а не по их номерам.

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

    Переменная с именем "3 подчеркивания" должна иметь значение больше, чем переменная с именем "2 подчеркивания".

    В пасти переменные в порядке "2 подчеркивания", "3 подчеркивания", "2 подчеркивания", "3 подчеркивания" : 0101

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

for problem D, i noticed that every fact had a number along with it. i thought that these would somehow be related to the answer, but i was wrong! :D

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

    This was our original intention (to have people output number from i-th correct fact), but this problem was the last to be prepared (less than 10 hours before the contest), and I had only 16 facts total — using only half of them for tests would have left us with only 8 test cases, which seemed too little.

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

Can we declare March 1st as Fool Programmers Day and have a contest like this again... :) we all have got a lot of fun trying to solve those problems...

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

    March 1 is already past, why not make it May 1 instead :)

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

      Sorry I forget which one comes after april.... thats why i am a big fool.. May 1 then... :D

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

For problem B, did you change the grader in the middle of the contest? In the beginning, the filename in the compilation output is "program.f". However, after I solved other problems and then went back to this problem, the filename changed into "program.ext".

That was a (slight) advantage for me that noticed this fact :)

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

    I myself noticed folder named g95 (fortran compiler) and some other great hints too. And similarly some time later the same error wouldn't include the path : ))

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

How to add a friend?

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

    Open this person's profile, there will be a star next to his name, press it, it will turn yellow, which mean you added him. but dont post comments that have nothing to do with the topic.

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

409H - A + B Strikes Back

When solving this I knew the answer will be evaluated on attempt 6 because "Emperor strikes back" was episode 5. I hope that was the rationale to choose number 5 or was it not?

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

    It wasn't :-) 5 was chosen as a reasonable compromise between few attempts which could be done unintentionally, and a lot of attempts which are irritating.

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

    actually, i feel that in such type of contests, problem name should be chosen with something to do with the answer, rather than the other way around. basically, i mean that Strikes Back could have been chosen because of 5 attempts, rather than what u suggested. :)
    for example, i think this was the rationale behind the name of the problem 409F - 000001. am i right Nickolas? ;)

    P.S. i see that the problem 409H - A + B Strikes Back contains the tag 2-sat. any idea why?

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

      In some problems name just has to be strongly related with the solution — for example, if the problem doesn't have a statement. This, of course, is the case with 000001. In other problems name can be anything funny, like in A + B strikes back — I find the idea of A + B taking revenge on humans for treating it without proper respect pretty funny.

      P.S. No clue; either a bug or a joke from a co-author :-)

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

        I find the idea of A + B taking revenge on humans for treating it without proper respect pretty funny.

        seconded! :D