[Условия задач] [Список тренировок]
11A. Последовательность
[seq]
Довольно любопытная задача на выявление закономерности в последовательностях. Первый раз всплывает принцип Дирихле.
11B. Провода
[cable]
Классический пример задач на “Бинарный поиск по ответу”. Эта тема хорошо описана в 3 лекции курса Михаила Густокашина
11C. Палиндромы
[palindr]
Двумерное ДП. Один из тех удачных примеров, доказывающий, что ДП много не бывает. Придется немножко подумать.
11D. Круговая площадь
[circarea]
Если все грамотно написать, предварительно подумав, то можно получить очень красивый и компактный код. Сама по себе задача из базового курса геометрии, но нужно быть внимательным, чтобы не сделать досадную опечатку, т.к. такую программу дебажить практически бесполезно.
11E. Гомер Симпсон
[homer]
Эту задачу можно свести к “Рюкзаку”, с той лишь разницей, что в рюкзаке максимизировалась стоимость вещей, а здесь нужно минимизировать остаток. Если в ходе решения возникли трудности, то можно еще раз прорешать задачу “3С – Копилка”. Текущая задача делает по аналогии.
11F. Дробная арифметика
[frac-ar]
Задача, в которой ввод и вывод представляют куда большую сложность, чем решение. Когда я учился на втором курсе в родной Альма-матер, работа с дробями была одним из вариантов семестрового курса лабораторных по ООП.
[Все решения]
Задачу 11E можно решить за сложность O(T / gcd(N, M)) (в худшем случае O(T)) с помощью диофантовых уравнений первой степени с двумя неизвестными, подкрепившись теорией в Википедии и воспользовавшись расширенным алгоритмом Евклида. Вот что получилось у меня: http://www.everfall.com/paste/id.php?vtl1d7hcxo8v
ОтветитьУдалить