Яндекс.Метрика
    Поиск по тегу

    забег


    Найдено: 1 запись

    Головоломки

    Скачки

    Задача известная (решение нагуглить можно), но, как мне кажется, достаточно интересная.

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

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