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

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

Мои поздравления KADR, который первым решил все 8 задач!

171A - Загадочные числа - 1

Самый простой способ сделать условие необычным — это не писать его вообще. В таком подходе масса преимуществ — не нужно переводить условие на английский, беспокоиться о том, все ли в нем понятно единственным способом, или о том, что участник может испугаться задачи, не осилив прочитать ее условие. Судя по тому, что эту задачу без проблем решило 690 человек, этот метод можно смело брать на вооружение и в регулярных соревнованиях :-)

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

171B - Звезда

Говорят, лучше один раз увидеть, чем десять раз услышать или сто раз прочитать. В этой задаче мы решили это проверить и заменить традиционное текстовое условие одной-единственной картинкой. Как и в предыдущей задаче, такой формат условия не вызвал затруднений — как минимум 645 участников узнало звездные числа (последовательность http://oeis.org/A003154 в OEIS), то есть количества шариков, из которых можно сложить шестиугольную звезду определенного размера. После этого оставалось только закодировать формулу их вычисления — Sn = 6n(n−1) + 1.

171D - Сломанный чекер

Что делать, если условие неизвестно, и единственным источником информации о задаче является чекер? Правильно — перебрать все варианты функций, преобразующих 5 вариантов входных данных в 3 варианта выходных данных, один из них точно подойдет :-)

171F - фювбюая

В этой задаче условие наконец-то есть! Один минус — оно зашифровано. К счастью, мы решили отличиться гуманностью и не использовать слишком заумных шифров, а взять самый простой — шифр Цезаря (каждая буква сдвигается на одно и то же количество позиций в алфавите). При большом желании и достаточном времени его можно раскодировать вручную — проанализировать часто встречающиеся буквы и короткие слова, получить отсюда возможное значение сдвига, применить его к остальным символам и проверить, насколько осмысленный получился результат. При чуть меньшем желании это делать можно было нагуглить удобнейший инструмент http://planetcalc.ru/1434/ или похожий, который по тексту выводил бы все возможные результаты его кодирования, и выбрать единственный осмысленный вариант. Кстати, само условие генерилось именно так :-)

После преодоления формата условия оставалась легкая часть решения — собственно найти простое число, чьи цифры, прочитанные в обратном порядке, давали бы другое простое число (последовательность http://oeis.org/A006567). 11184-ое такое число равно 999983, поэтому решать можно было "в лоб" — перебирать все числа, проверять их на простоту и простоту их зеркального отражения и продолжать так, пока не наберется нужное количество искомых чисел.

171E - ЗАГАДОЧНЫЙ ЯЗЫК

Затейливый контест моего авторства и ни одного затейливого языка программирования? Такого не бывает! Но я взяла себя в руки, и в этом контесте задач на эзотерику было всего 25%, то есть две. Должно было быть три, но интерпретатор третьего языка наотрез отказался сотрудничать, и я с позором изгнала его из списка задач. Может, когда-нибудь в следующий раз...

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

На этом этапе поклонников моего авторского таланта ждал небольшой бонус: в Codeforces-раунде #96 я давала задачу 133C - Лента Тьюринга, в которой объяснялся механизм вывода строк в INTERCAL и требовалось написать программу, которая бы преобразовывала строку в массив чисел, который эту строку выведет. Скрестив это знание с кодом Hello, World!, можно было легко получить искомую программу. Собственно, именно так я и поступила для написания эталонного решения.

PLEASE DO ,1 <- #8
DO ,1 SUB #1 <- #110
PLEASE DO ,1 SUB #2 <- #32
DO ,1 SUB #3 <- #72
DO ,1 SUB #4 <- #136
DO ,1 SUB #5 <- #88
DO ,1 SUB #6 <- #136
DO ,1 SUB #7 <- #64
DO ,1 SUB #8 <- #80
PLEASE READ OUT ,1
PLEASE GIVE UP

171C - A Piece of Cake

Во второй из задач на эзотерику условие было программой на Chef. Кстати, этот язык на Codeforces тоже уже фигурировал — он играл роль "неизвестного" в индийском ULR Chaos. Нужно было разобраться, что она делает, и продублировать это на любом нормальном языке. Как оказалось, она считывала вначале число N, затем N чисел a1, a2, ..., aN и вычисляла сумму i * ai.

171G - Загадочные числа - 2

Тут догадаться было гораздо сложнее, зато закодить — гораздо проще. По первым двум числам строилась последовательность типа Фибоначчи, третье число было номером искомого числа в этой последовательности.

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

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

а что в G?

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

Другое решение F Ручками находим ответ для 2,3,4,5 и замечаем закономерность :)

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

Задача H

Нужно было найти координаты точки, которая находится от начала кривой Гильберта заданого порядка на заданном расстоянии. Известно, что длина кривой Гильберта порядка n22 * n - 1. Можно было просто перебирать порядок кривой сверху вниз, и если длина, которая нам осталась, больше или равна длине кривой текущего порядка, то сдвигаться по этой самой кривой. Все, что осталось — это уметь находить, где же мы окажемся, если из данной точки нарисуем кривую заданого порядка, повернутую на заданый кратный 90 градусов угол. Это описано, с примерами кода, в Википедии.

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

Во второй из задач на эзотерику условие было программой на Chef

Ничего себе. Думал, текст приведён для отвлечения внимания, а закономерность находится и без него.

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

Немножко неприятно, что "неизвестные" языки раньше уже фигурировали непосредственно на Codeforces. Получается сюрприз только для тех, кто регулярно не участвует в SLR, не следит за прогопедией и вообще за деятельностью Nickolas.

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

У меня была странная проблема с INTERCAL: пока я не перенес один из PLEASE на другую строку, программа, выводящая INTERCAL не компилировалась, при этом компилировалась программа выводящая использующая вместо последнего числа массива не 80 а, например, 79. Интересно, с чем бы это могло быть связано. И времени, чтоб это понять, порядочно убил...

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

    Просто ты недостаточно вежлив :)
    Ну или что-то в этом роде :D

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

      Да нет, я был одинаково вежлив. Просто в одном положении компилятор выдавал "RANDOM COMPILER ERROR", а в другом — нет :)

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

        На самом деле эта ошибка возникает действительно рандомно на одном и том же тексте программы. Проблема в том, что в Codeforces результаты тестирования кода кешируются, и если эта ошибка возникла в первый раз, последующие разы она будет браться из кеша. Достаточно было добавить где-нибудь пробел или перенос строки, чтобы с точки зрения кеша код изменился, и программа запустилась заново. Я думала, как с этим можно бороться, но отключать кеш было нельзя, писать об этом в условии — раскрывать язык, а что-то еще не придумалось.

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

          А, вот оно как. Этот язык еще позитивнее, чем я думал:) В любом случае было весело, спасибо за контест!

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

          У меня в задаче D, когда в коде менял только числа, из-за этого пару раз вылезало "вы уже отправляли этот код", приходилось пробелы ставить.

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

            Подскажите люди добрые. :) У меня большинство задач не проходят из-за превышения временив каком-то тесте. По логике решение верное. Более короткое на ум не приходит. Это я торможу или проблема в том, что пишу на pascal?

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

              Проблема в том, что у вас решение плохое по асимптотике.

              UPD : в некоторых задачах у вас маленькие массивы, а в некоторых плохая асимптотика.

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

                То есть все дело в самом решении???

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

                  Дело в самой идее решения.

                  UPD : насчет вашей посылки по задаче про спички : у вас маленький массив. странно, что у вас TLE...по идее должно быть RE

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

                  а так бывает частенько. по-моему, если не слишком далеко за пределы заходит. у меня по криворукости бывало такое.

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

    Will there be an editorial for problem H?

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

      Sorry, I left a comment in Russian and forgot to leave the same in English interface. Here it goes:

      Problem H

      You had to find the coordinates of a point that is situated on a given distance from the beginning of Hilbert curve of given order. It is known that length of Hilbert curve of order n is 22 * n - 1. You could iterate through all orders of the curve from the biggest to the smallest and if the distance we still have to go is more than or equal to the length of a curve of a given order, we had to draw a curve of a given order and relocate from the beginning to the end. The only thing left is to learn how to find where will we be if we draw a curve of a given order rotated by some angle of 90 * k degrees. It is described, as well as the whole solution, in the Wikipedia.

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

Maybe people like to read this tonight xD