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

SNWS 2013 Round 2
Автор Fcdkbear, 11 лет назад, По-русски

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

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

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

Пусть мы зашли в некоторое количество баров. Понятно, что во всех кроме одного мы должны купить столько бутылок, сколько там есть, а в одном — столько, чтобы в сумме было N. Понятно, что "докупать до N" мы должны в том баре, где цена за бутылку самая большая (среди тех, которые посетили).

Получаем такое решение. Отсортируем бары по цене за бутылку. Считаем динамику [посетили X баров][купили Y бутылок]. Причем из каждого состояния только два перехода: не заходим в текущий бар, покапаем min(b_i, n — currentSum) бутылок.

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

А как решать Д?

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

    D — несложная динамика, эмулируем P шагов, из каждой клетки пробуем пойти во все стороны и пересчитываем вероятности. Из дома никуда не ходим! Ответ — сумма по всем шагам вероятностей нахождения чувака у себя дома.

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

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

      Динамика в float'ах за O(T * P * N * M) ? У меня получает TLE на 5 тесте. Код

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

        Как-то странно, у меня по сути все тоже самое, даже нет чередования слоёв, но не тлит.

        Upd. Залил код, может разберетесь, где подтормаживает.

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

        Видимо, вещественная арифметика подтормаживает, когда работает с 1.#INF. Если бы не TL, то получили бы ВА :)

        → Ответить