Викиучебник

Московская олимпиада по информатике - 2005: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Строка 247:
Можно грубо оценить длину наибольшей строки и понять, что памяти на такую реализацию хватит. В действительности, самая длинная строка при данных в условии ограничениях получается при ''N''=9358, ''K''=1: ее длина всего лишь 83 символа.
 
Оказывается, что приведенную динамическую схему можно упростить. Достаточно для каждого числа m хранить информацию лишь о самом коротком выражениевыражении, независимо от его типа. При этом, если для данного числа самое короткое выражение может быть как выражением типа 1, так и выражением типа 2, то нужно выбирать произведение, а не сумму. Обоснование правильности этого алгоритма оставим читателю.
 
===Задача D. Восстанови многоугольник===
Источник — https://ru.wikibooks.org/wiki/Московская_олимпиада_по_информатике_-_2005