задача дня-17

[falcao]

Не так давно встретилась задача -- скорее всего, она известная. Слишком уж естественная у неё формулировка. В таких случаях кому-то может быть известно "авторское" решение, которое мне было бы интересно узнать

Comments

[f137]

Сумма от n-1 (если перебраны все, кроме одного, последний заведомо подойдет) до 1.

[falcao]

Да, для n(n-1)/2 имеется пример, и суть задачи в получении оценки, то есть надо доказать, что меньшего числа проб в общем случае не хватает.

[akm762]

Стесняюсь спросить: а что-ж тут доказывать, когда "гарантированно" означает, что реализуется наихудший вариант, к-рый уже озвучен?..

[falcao]

Есть план, как гарантированно всё выяснить за n(n-1)/2. Доказывать надо то, что не существует более хитрого плана, позволяющего добиться цели за меньшее число проб. Это обычная для такого рода задач ситуация.

[akm762]

А, теперь понятно. =)