Pull to refresh

Скачки

Reading time 1 min
Views 1.5K
Задача известная (решение нагуглить можно), но, как мне кажется, достаточно интересная.

У нас есть 25 лошадей, мы должны выбрать из них 3х лучших. Для этого мы можем устроить несколько забегов. В каждом забеге могут участвовать не более 5 лошадей.
Все лошади разные (т.е. никакие две не бегут с одной и той же скоростью), скорость лошади от забега к забегу не меняется.
Требуется минимизировать число забегов.
UPDATE: Время измерять мы не умеем, после забега мы узнаем только порядок участвовавших в нем лошадей.

Формальное описание: есть множество из 25 элементов, на котором задан линейный порядок. За один запрос мы можем узнать часть этого порядка на выбранных нами 5 элементах. Требуется найти 3 минимальных элемента за минимально возможное число запросов.
Tags:
Hubs:
+2
Comments 34
Comments Comments 34

Articles