Форум

Сергей Чистович: Ага, вариант. // 21 ноября 2007, 15:11

Только зачем три? Хватит и двух, кажется.

Григорий Ярославцев: [без темы] // 21 ноября 2007, 23:11

Я не искал меньшую константу из идеологических соображений: пусть нам предложили ответ - тогда на его проверку необходимо 2 * (N - 1) операций, а успеть найти кандидата в ответы быстрее, чем за O(N) в худшем случае довольно странно. При этом эти две задачи скорее всего не перекрываются, так что 3 показалось мне похожим на нижнюю оценку для константы. В общем, интересно было бы в пятницу услышать решение за 2 * N