Напоминаю, что сегодня (10.11.2012) в 18:00 по Москве состоится второй контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!
Напоминаю, что сегодня (10.11.2012) в 18:00 по Москве состоится второй контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
| Название |
|---|



Как решать 4ую?
Отсортируем все блюда по неубыванию обычной цены (**B**). Предподсчитаем 3 массива:
Рассмотрим 2 случая:
sum[k] - maxD[k]sum[k-1] + minA[k]Выберем минимум из этих вариантов — это и будет ответом для текущего k.
Третья уже была :)
Anyone has idea for problem 6? It looks like we have to maintain a set of slopes to calculate the queries, but I can't find an effective way to add a new slope since the profit values are not monotonous.
The trick is to find a way to reduce number of times you have to rebuild the hull.
Как решать 5ую задачу?
Сделаем паросочетания цифра — место. Каждое наблюдение делает 2 вещи. Если мы знает что на одном отрезке минимальное число Х, то во-первых, на этом отрезке числа могут быть только от X до N-1, а во-вторых число X может быть только на этом отрезке. Получаем матрицу из 1 и 0. Дальше можно делать всё, что угодно — макс. паросочетания, Венгерка и.т.п.
Матрицу можно получить следующим образом: будем считать "во-первых" и "во-вторых" отдельно. "Во-первых": сначала пробежимся по наблюдениям, и посчитаем, какие числа могут на этим месте быть. Заметим, что это отрезок. Соответственно, обновлять можем за O(M*N) — для каждого наблюдения пробежаться по каждому месту. Потом обновим матрицу "во-вторых": для каждого наблюдения возьмём "пограничное" число и обнулим его вне допустимого отрезка. O(M*N). Итого, получили матрицу.
Just published Results.