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

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

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

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

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

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

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

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

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

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

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

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

    → Ответить