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

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

Всем привет!

9 ноября состоится интернет-тур Всероссийской Командной Олимпиады Школьников по Программированию.

Пробный тур проводится с 18-00, 5 ноября 2014 года до 18-00, 8 ноября 2014 года.

Больше информации

Правила олимпиады

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

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

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

Всё-таки это отборочный интернет-тур к ВКОШП

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

http://neerc.ifmo.ru/school/information/problems-spb-2014.pdf

ссылка на условия.

как решать С и К?

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

      Спасибо. И еще, я один наркоман писал на F разложение на множители и 2 в степени количества множителей?

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

        Нет.) Доказыватся, что делителей будет O(log N), а именно — по десять на число (2 * 3 * 5 * 7...)

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

          Мы так прикинули, их всего 15 в сумме может быть, просто многие сдавали, при чем так-то не с неплохой скоростью сдавали, вот мы и подумали, мб есть решение полегче

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

        (Делитель A) * (Делитель B) = (Делитель A * B)

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

    А почему бы в К не написать нечто следующее.

    1)Рассмотрим позиции, в которые может пойти второй игрок и победить. Если их хотя бы 2, то мы проиграли, если одна, то ходим туда, если их 0, то перебираем клетку, куда ходим.

    2)Перебираем ход второго игрока, считая, что он ходит в некоторой окрестности позиции, куда мы поставили крестик.

    3)Перебираем наш второй ход, опять же, в небольшой окрестности позиции, куда мы походили.

    В качестве окрестности можно, видимо, взять квадратик 11*11, должно уложиться в ТЛ. Можно еще, пожалуй, соптимизировать так — перебирать только те позиции первым ходом, походив в которые мы сможем победить, если второй нам не будет мешать(делаем два хода подряд). Таких позиций не может быть уж слишком много

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

      Если их хотя бы 2, то мы проиграли

      Почему? Мы ведь можем первым ходом походить и выиграть.

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

    К. Добавляем по несколько клеток слева, справа, сверху и снизу (я добавил 20 клеток) и отмечаем их '.'.

    Напишем функцию win(ch) => количество позиций что если в них поставить ch (X или 0), то можно выиграть.

    Если win('X') > 0 то первый игрок может выиграть сразу, следовательно ответ равен win('X').

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

    Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.

    Иначе, перебираем клетку куда мы ставим 'X'. Если после того, как мы поставили Х на эту клетку, на поле выигрышных клеток стало больше одного, то увеличиваем ответ.

    P.S. Функию win(ch) надо реализовать не на всем поле, а на каком то подпрямоугольнике.

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

      Эх...

      Была такая идея, только все пытался решить "полегче" — динамикой, оказалось нифига не легче и нифига не правильно.

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

      К 2 часам решили 7 задач, и остальные 3 часа пытался запихать такое решение. "WA 60". И почему-то сайт работал только через анонимайзер.

      Вывод 1: Не зацикливаться на одной задаче. Вывод 2: Убогий интернет до добра не доводит.

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

      Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.

      Если win('0') равен одному, ответ-то единица: мы считаем первые ходы, а не вторые.

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

А как насчет результатов , кто куда прошел ????

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

    Из Санкт-Петербурга прошло 11 команд (9 команд решили 7 задач (результаты Спб)). Логично предположить, что из интернет-тура прошли команды с 7 задачами, возможно несколько команд с 6.