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

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

Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?

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

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

Расскажите СМС и Благовонное число, пожалуйста.

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

    В SMS я писал динамику. f[i][j] = какое минимальное количество раз мы нажмем, если i-ая буква последняя на j-ой клавише. После этого делал восстановление ответа по динамике. Вот код — http://pastebin.com/qkmNipSA

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

    В I (СМС) зашел простой перебор почти без отсечений.

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

    В G нужно сначала определить длину палиндрома: заметим что кол-во палиндромов соответствующей длины
    1 — 9
    2 — 9
    3 — 90
    4 — 90
    5 — 900
    i — 9*10^((i+1)/2)
    тогда будем идти и отнимать от числа кол-ва пока следующее можно отнять. Дальше получим номер числа нужной длины. Тут уже просто добавим к 10и в степени (длины+1)/2 номер и отнимем 1, а дальше просто скопируем в конец все что нужно, для получения длины.

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

Расскажите как Е в усложнённой решается?

Мы написали три разных решения и все падают на втором тесте!

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

    Сам догадался в чём ошибка. Забыли учесть, что после 4-0 не может быть 4-1.

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

В J основная идея такая: если мы умеем разбивать для n, то умеем и для (n + 8). Как точно делать, не помню, решал сокомандник, но подобрать не сложно, я думаю. Теперь для всех маленьких n (<= 25 например) просто переберем все все разбиения, где не нашли — ну скажем что No :) . Вроде у нас по коду получилось что решение есть для n % 8 == 0, n % 8 == 1, (n — 12) % 8 == 0, (n — 13) % 8 == 0.

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

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

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

Интересно, каково решение задачи F? На контесте не смогли побороть WA8.

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

    Задача сводиться к задаче поместить круг диаметром D в прямоугольник D*L А дальше каждая точка не даёт мячику находиться на отрезке, который считается по теореме Пифагора. Ну а там уже сканлайном пройти.

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

      То же самое делали! То есть получается, мы рассматриваем оба прямоугольника, и "плохие" отрезки помещаем на одну и ту же прямую, а потом находим сканлайном на ней свободную точку? Может, из-за точности проблемы?

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

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

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

А кто-нибудь знает идею на B?

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

    Авторская идея решения использует паросочетание :) Далее предлагаю подумать самим — если не получится, расскажу!

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

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

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

    Если я не ошибаюсь, то можно решать так: Переберем цвет левого верхнего угла. Теперь построем двудольный граф где вершины это диагонали. Один тип диагоналей будет в первой доле, второй соответственно во второй. Между вершинами будет ребро, если клетка в которой они пересекаются(если пересекаются) покрашена не в свой цвет. Ответом будет размер минимального вершинного покрытия, он вроде равен максимальному паросочетанию.