Подскажите, пожалуйста, задачу на каком-нибудь из online judges, которая решается с помощью симплекс-метода. Недавно проходили его в университете и хочется проверить, правильно ли я пишу этот алгоритм.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 02:17:57 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Но там надо чуть соптимизировать. Подробности есть в обсуждении задачи.
На самом деле не надо там ничего оптимизировать. С теми ограничениями абсолютно любая вменаемая реализация проходит на ура. В разные времена "Триатлон" служит тестовой площадкой для разных по степени криворукости моих реализаций симплекс-метода :) И они все проходили за 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]).
Искомый многочлен имеет вид