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

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

Предлагаю здесь обсуждать задачи.

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

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

Задача A. Подскажите пожалуйста, в чём ошибка (WA5):

// код под спойлером

Общая идея: классическая задача отображения доски на всю плоскость; переберём все возможные доски, так, чтобы количество пересечений прямой (между первой точкой и отражением второй) с прямыми — границами доски было равно n. Ну и выберем из всем таких минимум.

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

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

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

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

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

    Нужно еще проверять, что вы не пересекли цель ранее, чем сделав n отражений. Тест: 4 4 2 2 3 3 2

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

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

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

Задача B. Кто-нибудь ловил WA13? (вопрос решён, мой косяк)

Вроде всё норм делаю: вначале скалываю все разряды, потом пробегаю от младших к старшим и если текущий (i) и предыдущий (i-1) разряды больше 0, то увеличиваю следующий (i+1) разряд и уменьшаю текущий (i) и предыдущий (i-1), передвигаю текущий счётчик на 3 назад (на всякий случай), если текущая (i) ячейка больше 1, то уменьшаю её на два, следующую (i+1) ячейку увеличиваю на 1 и увеличиваю предпредыдущую (i-2) на 1, при этом если i=0, то не делаю увеличение (i-2) ячейки, а если i=1, то увеличиваю предыдущую (i-1) ячейку, и в этом случае тоже передвигаю на 3 назад на всякий случай, ну и конечно проверяю, чтобы i не стало равно 0 (всё, тут и понятно стало.. далее цикл идёт и увеличивает i на 1, пропуская случай, когда 0-ая ячейка стала равна 2).

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

    Оказалось, что по TLE проходит такой алгоритм (by Slamur):

    1. Переводим числа в BigInteger
    2. Складываем их
    3. Переводим обратно
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А почему так плохо порешали задачу D? Она же вроде простая совсем. Конечно набор задач и шраф у меня в результате совсем дурацкий получился. За упавшую B обидно.

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

    Честно, не успел даже прочитать. Условие показалось мутным с этими действительными числами.

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

    А как решалась, расскажи пожалуйста.

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

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

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится
      1. Забить на вещественные числа. Чтобы убить нуба надо 27 выстрелов, чтобы убить крутого — 4. Стреляют они раз в 107 и 41 секунд соответственно. Про время полета — вообще какой-то треш. Просто считаем, что если стреляют одновременно, то оба успевают выстрелить.
      2. Храним суммарное HP.
      3. Из оптимальности-неоптимальности крутых осталось min(HPA,A), нубов осталось .
      4. Тупо моделируем. Кто сейчас стреляет считается, зная количества. Это работает явно не хуже, чем 4·109, причем очевидно, что оценка жестко не достигается, потому что если у обоих много XP, то они быстро дохнут.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E. Fleet of Byteland

Что-то совсем не могу найти баг в своем решении. Есть у кого идеи?

И такой вопрос — кто как обходил то, что 2 * k не влазит в unsigned long long или такого теста не было?

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

    Там, вроде, количество всегда меньше К.

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

      Да? А тест из 50 тире... есть 1, 2, 3 и 4 тире, то есть получается Фибоначчи с суммой последних четырех, а это точно не влезет...

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

        Да там-же 2^50 < 2^63, даже если взять все разбиения строки.

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

          Кажется это не совсем правильная логика, ибо по данному утверждению строк вида ?? будет 4, а при условии что ещё могут быть отдельные двойные символы, таких строк будет 8

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

            Разве общее кол-во разбиений(не важно какой длины) не будет меньше-равно 2^50? Ведь мы либо клеим символ к предыдущему, либо создаем новую строку. Это в любом случае кол-во не меньше чем то, что нам нужно, вроде.

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

            Не вижу ничего плохого в этой логике. 2^50 — количество способов разбить строку длины 51 на подстроки.

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

          хм, действительно, что-то меня понесло...

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

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

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

          На Java с long тоже зашло, хотя там 2^63 не влезает. Такого теста не было.

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

    Тест: "...." 2

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

      EEI, нет?

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

        Ой.. Блин, верно. Какой-то косяк. Ща подберу.. я просто сверяю со своим AC.

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

        Во: .--. 8 Ответ: "WE", а у тебя 0

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

          Ну и косяк в этом пробеле

          m['W'] = ".-- ";
          
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        И ещё вопрос: почему ты f не memset`ишь? Когда массив глобально объявляется, он сам обязательно нулями заполняется?

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

          Я живу с мыслью что сам)

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

          конечно сам, даже если у вас есть структура и в ней массив, и вы объявляете элемент структуры глобально, этот массив обнуляется

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

      Спасибо за тест, нашёл баг и в своём решении.

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

    Если значение динамки на каком-то этапе становилось больше чем 2^63, я делал его равным 2^63 и больше ничего не прибавлял. Таким образом, в сложении учавствовало два числа, одно из кторых строго меньше чем 2^63, а второе — не больше чем 2^63, значит сумма <=2^64-1. Кажется, так можно делать.