Подскажите, пожалуйста, задачу на каком-нибудь из online judges, которая решается с помощью симплекс-метода. Недавно проходили его в университете и хочется проверить, правильно ли я пишу этот алгоритм.
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.04.2024 01:11:01 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Но там надо чуть соптимизировать. Подробности есть в обсуждении задачи.
На самом деле не надо там ничего оптимизировать. С теми ограничениями абсолютно любая вменаемая реализация проходит на ура. В разные времена "Триатлон" служит тестовой площадкой для разных по степени криворукости моих реализаций симплекс-метода :) И они все проходили за 0.016, если мне не изменяет память.
Что касается получаемых командами ТЛ-ей - на тестах этой задачки случается достаточно редкое явление - зацикливание СМ. В этом и есть причина. Один из способов борьбы - "Правило Бленда" (вроде так), описано в Кормене или гугл. Состоит в дописании примерно одной строчки к коду СМ...
http://www.codechef.com/problems/OVENTIME
Для тестирования, думаю, любая задача на поток подойдет.
Вроде как в чистом виде на Тимусе
На самом деле если посмотреть на матрицу в этой задаче можно предложить итеративное решение. Без Гаусса.
А вот вроде в этой этой задаче как раз надо решить СЛУ.
Первый способ.
Второй способ не такой универсальный, как первый, но в принципе очень удобный.
Как раз при нахождении формулы для какой-то последовательности, которая задаётся каким-то многочленом.
Пусть у нас есть значения многочлена в точках {0, 1, 2, ..., k} — P(0), P(1), ..., P(k).
Тогда обозначим a[0][0] = P(0), a[0][1] = P(1), ..., a[0][k] = P(k).
После этого вычислим a[1][0] = a[0][1] - a[0][0], a[1][1] = a[0][2] - a[0][1], ..., a[1][k - 1] = a[0][k] - a[0][k - 1].
Затем по такому же принципу a[i][j] = a[i - 1][j + 1] - a[i - 1][j] для 1 ≤ i ≤ k, 0 ≤ j ≤ k - i. То есть получаем треугольник из попарных разностей значений предыдущей строчки.
Далее возьмём первый столбец (c0 = a[0][0], c1 = a[1][0], ..., ck = a[k][0]).
Искомый многочлен имеет вид