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

Автор Anton_Lunyov, 14 лет назад, По-русски
Приглашаю всех поучаствовать в январском коротком контесте на CodeChef.
Контест продлится 2,5 часа. Начало в воскресенье 23 января в 19:00 по московскому времени.
В этот раз автором задач буду я.
Контест будет состоять из 5 задач различного уровня сложности.
Первые 10 участников не из Индии получат призы от организаторов.

P.S. Если кто помнит гран-при Харькова VII Открытого Кубка (весна 2010), то я был автором половины задач оттуда (S-Grundy game, Product of coprimes, Divisibility of binomial coffecients, Factorial and fourth degree, Sum of two squares, Pairwise different distances, Indivisibility of binomial coecients, Irrational pairwise distances, Number of quadratic residues). Но на этом контесте таких гробов, как большинство задач из этого списка, точно не ожидается. :)
  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
С ссылкой лажа какая-то...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему не из Индии???:)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Насколько я понимаю ето сайт индийский, и потому зачёт отдельно для индейцев и для всех остальных )
    • 14 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      Да , и индусам там отдельно призы обычно дают. Ну во всяком случае на марафонах.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
      Мне кажется правильно индийцам, а не индузам.
      Подтверждает KDE'шный Spell Check и Google
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
        почему-то я всегда думал, что индусам...

        вообще не так и не так :D
        • 14 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится
          Индусы или индийцы? "Индус" - это слово, указывающее прежде всего на религиозную принадлежность. Индус - устаревшее название индийцев, которое в современном русском языке выглядит как анахронизм. Индус - это последователь индуизма. Но даже в этом смысле слово "индус" давно устарело. В современном русском языке есть слово "индуист", его и используйте, когда хотите обозначить последователей индуизма. И знайте, что, кроме индуистов в Индии проживают еще миллионы мусульман, сикхов, христиан, буддистов и приверженцев других религий. 

          Правильно называть жителей Индии словом "индиец". Для обозначения индийских женщин нужно использовать слово "индианка", а не "индуска" и не "индийка".

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

            Ерунда эти все ссылки. Меня Русскому Языку учила моя бабушка, которая 40 лет была преподавателем русского языка и литературы в первой половине прошлого века. А теперь внезапно оказывается, что правильно говорить не «программное обеспечЕние», а «программное обеспЕченье».

            А, если правильно «индианка», то куда девать всего Фенимора Купера? Там что теперь «индеец» и «индейка»? Поскольку «индианка» несколько из другого полушария…

             

            • 14 лет назад, # ^ |
              Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
              Там обсуждается именно людьми, которые побывали в Индии и знакомы с местными традициями; они говорят именно так как этого хотят индийцы.

              P.S. А индейка-это же вроде как было блюдо для праздничного стола. Или я от жизни отстал?
              • 14 лет назад, # ^ |
                  Проголосовать: нравится +6 Проголосовать: не нравится

                Так и я о том же. Если «индианка» теперь – это жительница Индии, то, как назвать жену индейца. Конечно, есть вариант «индеец и его скво», но это уже из Джека Лондона-)

                Однако, погуглив (новое слово), я понял, что не прав. Действительно, теперь «индианка» живет в Индии, а жену индейца предлагается политкорректно называть «представительницей коренного населения Северной Америки». Но можно и «индианка», теперь у этого слова два значения. В общем, велик и могуч…   

                 

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Вы забываете о том, что Купер - американский писатель, и "индианки" в его книгах - это перевод с английского. В английском языке ещё большая путаница: Indian может обозначать как индийца, так и индейца. И ничего тут странного нет, вспомните, куда Колумб сначала хотел приплыть?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Отличные новости:)
Никто случайно не знает, как у них с доставкой футболок? Мне должна была еще за ноябрьский прийти, но до сих пор нету, что обидно(
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    У меня уже 5 футболок. (Среди них только три разных :) )
    За октябрьский Cook-Off мне пришла давно.
    Так что должна прийти.
    Я сам сейчас жду шестую за декабрьский.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
      А сколько первых получают футболки? (в cook и mounth контестах)
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Оно у них все время меняется. В начале первые 20 получали за короткие (за длинные там первой десятке раньше давали деньги). Я во втором коротком занял всего лишь 15-е место, но футболку получил. Теперь дают 10-ти первым и за короткие и за длинные (Отдельно идет зачет среди индусов и остального мира, то есть первые 10 из остального мира получают футболки). За длинные теперь дают деньги только первым двум.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Эх... Точно не вар мне :( Я зарегался там давно, но что-то мне там не понравилось и я забил, надо было поучаствовать :)

          Кстати кажется когда-то там не было ограничений на переменные в задачах... может поэтому я и забил

14 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
It's amazing that the problem setter is you.
I admire your perfect performance at ProjectEuler.
Maybe there will be much more participant because this article.
I'm waiting for this contest!
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Должен заметить, что эти короткие контесты иногда пишут очень знатные программисты
1-й и 3-й контесты выиграл tourist
http://www.codechef.com/rankings/COOK01
http://www.codechef.com/rankings/COOK03
2-й контест выиграл tomek.
http://www.codechef.com/rankings/COOK02
4-й контест выиграл cgy4ever.
http://www.codechef.com/rankings/COOK04
Вот результаты 5-го
http://www.codechef.com/rankings/COOK05
Этот контест будет 6-м.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Видимо, теперь на CodeChef потянутся с CodeForces, и я перестану получать оттуда халявную футболку каждый месяц :) Пока там недостаток сильных участников.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Халявную футболку оттуда-это чтобы не стирать? xD
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
надо не забыть, спасибо =)

контест я помню харьковский, надо срочно учить матчасть :D
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ребят, а там участие в контестах проходит без регистрации на контест?

P.S. просто не нашел рега на контест
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Не надо. Чтобы участвовать в Cook-off и Month Challenge достаточно быть просто зарегистрированным на сайте. Иногда там проводятся другие контесты. Тогда надо специально регистрироваться.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very nice, looking forward to it!

The interface of CodeChef is kind of bad and I couldn't find the info: does one have to register for the contest beforehand? If so, how?

14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Где там стендингс?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Zdravstvuite ya reshil odnu zadachu s cook-off-a i poluchil po nei zelyonuu galochku, chto eto znachit? prinyato ili proshlo vse testy? Sry za tochto na english, toroplus'
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
у них всегда в контестах столько *кхм*... математики? или это ты, Антон, постарался? =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так разве здесь много математики?
    Тут только одна чистая. Остальное я бы назвал программированием.
    Но обычно математики меньше, конечно.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а я что то никак не появляюсь в ранк листе, или через какое то время?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    обновление каждые две минуты, а на деле почему-то еще больше.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а разбор задач по окончанию сделаете?)
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
меня постоянно пугает фраза "Help India win the ACM ICPC World Finals" на главной странице

осталось сделать демотиватор скрина с подписью: "одумайся! участвуя на codechef ты помогаешь врагу!" =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спокойно, Саша! Им ничем не поможешь! :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      а вдруг там развёрнутая система {индусских, индейских, индийских, индианских, индеющих, индусящих, индусующих, индясных, индуснутых, иднинеющих, индосных} шпиёнов, которые гипнотизируют участником 25-м кадром и халявными футболками? =)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо Антону за задачи. Я не знаю почему я так затупил и не сдал 4 задачи. В задаче про шарики у меня упорно появлялся Wrong Answer после долгого тестинга. Видимо где-то набажил в коде. Идея примитивная и старая как мир. При столкновении можно считать, что с шариками ничего не происходит. Видимо там что-то не так с 64-разрядным типом. Там ответ всегда влазит в 64-разрядный тип?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Чето у меня на первую задачу все время неверные ответы.
    Где посмотреть решения других игроков?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По крайней мере в беззнаковый точно влазит. Там же знаменатель не превышает НОК чисел от 1 до 40.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1) Ответ не всегда влазит в 64 разрядный тип (писал на джаве с длинкой)

    2) Если я верно понял то может быть ответ INF, когда 2 шарика в одинаковой точке движутся с одной скоростью.

    Словил TL.

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если верить условию, то:
      All start coordinates are different.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хм. Ладно не заметил. Просто я после первого WA, начал думать что у меня не так, и это было 1 из возможностей.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      не могут быть они вроде в 1 точке - там все Х разные
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А вот про 64 тип, наверное вы правы, жаль, если баг в этом :(
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А дорешивание там есть?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не могу найти - а там есть дорешивание?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
в архиве будут задачи
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Я так и не понял почему мое решение первой задачи неверное((
Я вычислял рекурсивно по формуле: Cn,k = Cn-1,k-1 + Cn-1,k

На огромных числах не могу проверить, но т.к. в данной формуле фигурирует только сложение - очевидно, что если Сn,k не превышают 2^64, то и на каждом шаге превышения не будет. Глубина рекурсии тоже не сильно глубокая получается. Но тем не менее - решение не проходит.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    при k=2 и k=3 будет глубокая рекурсия
    5983999427 2
    4777873 3
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, что-то я не так обдумывал)) Ну а тогда почему у меня было написано неверный результат, а не переполнение стека или ещё что-нибудь?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Посмотрел последний твой сабмит. Оно выдало все нули.
        Во-первых надо использовать беззнаковый тип unsigned long long
        В помощь второй тест в файле
        18446744073709551613 18446744073709551615
        Он не влазит в long long.
        Но вообще я не понял как оно выдало все нули.
        Видимо оно проглючило при считывании этого теста и дальше все пошло наперекосяк.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      я так решил: брал max = max(k, n-k), min = (k, n-k) и выводил (n)*(n-1)*...*(max+1)/min!.
      т.е. при n=5983999427 и k=2 ответ=5983999427*5983999426/2=17904124568176164451.
       
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Check out the contest editorial here