Предлагаю здесь обсудить задачи раунда. Интересует, как решалась задача А.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | atcoder_official | 149 |
6 | -is-this-fft- | 148 |
6 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
10 | cry | 142 |
Предлагаю здесь обсудить задачи раунда. Интересует, как решалась задача А.
Название |
---|
Пусть мы зашли в некоторое количество баров. Понятно, что во всех кроме одного мы должны купить столько бутылок, сколько там есть, а в одном — столько, чтобы в сумме было N. Понятно, что "докупать до N" мы должны в том баре, где цена за бутылку самая большая (среди тех, которые посетили).
Получаем такое решение. Отсортируем бары по цене за бутылку. Считаем динамику [посетили X баров][купили Y бутылок]. Причем из каждого состояния только два перехода: не заходим в текущий бар, покапаем min(b_i, n — currentSum) бутылок.
А как решать Д?
D — несложная динамика, эмулируем P шагов, из каждой клетки пробуем пойти во все стороны и пересчитываем вероятности. Из дома никуда не ходим! Ответ — сумма по всем шагам вероятностей нахождения чувака у себя дома.
Я не сдал, потому что не учитывал нулевой шаг, т.е. когда он сразу у себя дома.
Динамика в float'ах за O(T * P * N * M) ? У меня получает TLE на 5 тесте. Код
Как-то странно, у меня по сути все тоже самое, даже нет чередования слоёв, но не тлит.
Upd. Залил код, может разберетесь, где подтормаживает.
Видимо, вещественная арифметика подтормаживает, когда работает с 1.#INF. Если бы не TL, то получили бы ВА :)