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

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

Вроде ещё не было создано темы. Предлагаю здесь обсудить задачи.

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

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

Меня интересует задача C. Какой ответ будет для теста?

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

    -1 я так понимаю.

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

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

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

        Я задал клар жюри по этому поводу (уже после своего отыгрыша, где мне повезло угадать). Никто так и не ответил.

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

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

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

        Ошибся, я, видимо, тоже правильно угадал.

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

Как решать D,E?

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

    Я не решил E, но кажется это просто взлом RSA.

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

    D — отсортируем точки по углу и динамика — какие 2 последние точки являются вершинами, в итоге куб

    Е — разложим на множетели, найдем private key, возведем в степень

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

      А как в задачах типа D "замыкать" эту динамику? Нам же первая точка вроде бы тоже важна? Или мы ее просто перебираем?

      UPD. Расскажите все равно, как надо это правильно кодить, если бы у точек были возможны любые координаты.

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

        Там y ≥ 1, а точка 0, 0 — вершина

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

        Если я не ошибаюсь, то неважна. Там Y во входных данных строго положительный, так что все выбранные точки лежат в одной полуплоскости. Так как нам еще обязательно надо взять (0, 0), то стоимость взятия конечных точек не зависят от взятия первой, только от последней взятой.

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

      Можете выложить код по Д или поподробнее рассказать, как делать переход, если не сложно?

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

        Подробнее: отсортируем точки по углу относительно (0, 0). Динамика dp[i][j] (j < i) — максимальная стоимость, которую можно получить, если взяты i-ая точка, j-ая точка, какие-то из точек до j и не взята никакая точка между i и j. То есть i и j — две последние взятые точки. Внешний цикл — перебираем i. Обозначим i-ую точку как А. Внутри этого цикла есть два варианта:

        1. Точка А — первая из взятых точек. За предыдущую точку можно взять начало координат. Тогда dp[А][O] = стоимости точки А.
        2. До А была взята какая-то другая вершина, обозначим эту другую вершину как B и попробуем ее перебрать, это второй цикл. Тогда dp[A][B] = cost[A] + bestDpValueForB + sumCostInBetween. bestDpValueForB — это max(dp[B][K]), которое можно взять так, чтобы многоугольник OKBA был выпуклым. sumCostInBetween = сумма стоимостей точек, лежащих в треугольнике OAB. Подсчет этой суммы и перебор вершины K — это третий цикл.

        Ответом будет max(dp[i][j])

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

Насчет задачи C. Точно такая же задача идет на VIII Открытой олимпиаде школьников по программированию. Может не следует её обсуждать?

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

    Когда она закончится?

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

      15 января, если не продлят. Могу, кто захочет, решение в личку рассказать.

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

        Да решение я вроде могу придумать. Просто для меня С — одна сплошная неоднозначность, что спрашивали-то? Фраза "действуют оптимально" при непонятных целях мне непонятна.

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

          Мне интересно, а ты можешь придумать два различных (разумных) понимания фразы "действуют оптимально" таких, что для некоторого теста ответы будут отличаться?

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

            Для диверсанта:

            Оптимально 1: Если пройти не можешь, то бегать как можно дольше Оптимально 2: Просто бежать к выходу любым из кратчайших путей.

            Уровень — замкнутая окружность достаточной длины. Единственный охранник начинает на выходе, диверсант — на противоположной точке круга.

            Гарантированно пройти диверсант не может, потому что охранник уже у выхода и может просто ждать там. Охранник форсированно поймать диверсанта тоже не может, потому что можно бегать по кругу.

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

              Действительно, надо было в условии вместо "Выведите одно целое число: -1, если активист будет пойман, и минимальное время, за которое активист выйдет с завода, в противном случае." написать что-нибудь в таком духе "Если активист сможет сбежать, выведите минимальное время, за которое активист выйдет с завода, в противном случае выведите -1."

              Тогда вроде бы уже будет однозначно.

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

                Спасибо за разъяснение, так действительно понятней, что спрашивали и как решать.

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

А почему же анонс никто не написал?:( Я вот забыл про раунд:(