Есть табунчик 25 коней.
Задача: при помощи минимально возможного количества заездов, в каждом из которых может принимать участие до 5 коней отобрать троих самых быстрых животных.
Условия конкретизируйте… Коней отобранных в предыдущих заездах можно включать в последующие заезды ???
Вообще, задачка чисто на динамическое программирование… Сейчас не скажу какими уравнениями описывается и каким алгоритмом решается… Но, точно из этого раздела…
Eugene_UKFU, в каждом забеге по 5 коней, отсюда 5 забегов, с каждого забега берем первую лошадь (самую быструю). Делаем шестой забег и выявляем первые три самые быстрые лошади.
Redbox, а что если при организации первого забега выйдет так что 3 самые быстрые из всех окажутся в одной из пятерок?
тогда 2 самых быстрых реально мы отбросим.
естественно он короткий, но неверный.
Когда играют ЧМ так команды по 4 делятся, а что если там англичане немцы французы и бразильцы например?
Ясен перь что двое вышедших из группы лузеров могут быть хуже вылетевших из такой.
Я потому фут и не смотрю… :)
Eugene_UKFU,
в любом случае нужно протестировать всех коней хотя бы 1 раз.
3 пути решения:
1) начать с независимых испытаний (как у alexv1975) — невозможно так как после 5го испытания не существует способа всего лишь одним испытанием выявить трех победителей
2) разбить на 2 или больше независимых групп и проводить зависимые испытания внутри них — бесполезно, так как группы независимы невозможно гарантировать что все сильнейшие не останутся внутри одной группы.
3) остается 1 путь — все испытания должны быть зависимы — то есть в каждом испытании должен участвовать конь, ранее участвовавший в другом испытании. При этом единственно возможный способ испытать всех коней за 6 заездов — это брать в каждый последующий заезд только одного коня из предыдущих заездов.
4) из того, что сравнивать между собой независимо протестированных коней невозможно следует что после каждого заезда должны быть ясны 3 сильнейших на текущий момент. Поэтому, если найдется хотя бы один способ разделения коней таким образом, что 3 сильнейших не будут ясны, то это будет означать что за 6 заездов протестировать невозможно.
После 1го заезда все ясно
Легко показывается, что если во втором заезде участвует любая из 5 лошадей 1го заезда (+4 случайных непротестированных), то возможен расклад, при котором 3 сильнейших после второго заезда неопределены.
Вроде ничего не перепутал :)
7м: 5 забегов, 1 забег победителей + еще 1 забег на проверку (номера 2,3 из забега победителей + номера 2,3 из забега лошади победительницы, номер 2 из забега лошади, пришедшей 2й в забеге победителей).
Mihail1970, Это уже было в мае, все подумали что ставку начнут снижать стали покупать ОФЗ и облигации, но кто заметил разворот на ММВБ в 20х числах мая вышли в кэш и до сентября сидели наблюдали, в...
Кто больше всего инвестировал в биткоин в 2024 году
Кто больше всего инвестировал в биткоин в 2024 годуBlackRock лидирует с инвестициями в размере $50 млрд, опережая MicroStrategy с долей в размере...
⛽️ЛУКОЙЛ: отработка с прибылью +4,2% 🚀 Наш прошлый анализ по ЛУКОЙЛу полностью оправдал себя! 📈 Уже сейчас позиция принесла +4,2% прибыли, что является отличным результатом.Что дальше? 🤔💡 Цена продолж...
Роснано 200 млрд р. Деньги выводили под видом покупки сомнительных технологий у аффилированных компаний по завышенной цене, лоббирования искусственных рынков сбыта, продажи долей по заниженным ценам У...
Облом с Распределениями цен, повторять их бессмысленно, они нестабильные Итак, моя гипотеза о том что имеет смысл изучить распределение цен конкретной компании за длительный период, скажем 30 лет, что...
Тесты китайских авто в российских погодных условиях.
В России провели исследование способности китайских автомобилей выдерживать местные погодные условия. Тесты проходили в 26 регионах, а участие в...
Вообще, задачка чисто на динамическое программирование… Сейчас не скажу какими уравнениями описывается и каким алгоритмом решается… Но, точно из этого раздела…
9 получается
но это самый красивый способ пока достигнутый
Время замерять никто не запрещал вроде?
тогда 2 самых быстрых реально мы отбросим.
Когда играют ЧМ так команды по 4 делятся, а что если там англичане немцы французы и бразильцы например?
Ясен перь что двое вышедших из группы лузеров могут быть хуже вылетевших из такой.
Я потому фут и не смотрю… :)
в любом случае нужно протестировать всех коней хотя бы 1 раз.
3 пути решения:
1) начать с независимых испытаний (как у alexv1975) — невозможно так как после 5го испытания не существует способа всего лишь одним испытанием выявить трех победителей
2) разбить на 2 или больше независимых групп и проводить зависимые испытания внутри них — бесполезно, так как группы независимы невозможно гарантировать что все сильнейшие не останутся внутри одной группы.
3) остается 1 путь — все испытания должны быть зависимы — то есть в каждом испытании должен участвовать конь, ранее участвовавший в другом испытании. При этом единственно возможный способ испытать всех коней за 6 заездов — это брать в каждый последующий заезд только одного коня из предыдущих заездов.
4) из того, что сравнивать между собой независимо протестированных коней невозможно следует что после каждого заезда должны быть ясны 3 сильнейших на текущий момент. Поэтому, если найдется хотя бы один способ разделения коней таким образом, что 3 сильнейших не будут ясны, то это будет означать что за 6 заездов протестировать невозможно.
После 1го заезда все ясно
Легко показывается, что если во втором заезде участвует любая из 5 лошадей 1го заезда (+4 случайных непротестированных), то возможен расклад, при котором 3 сильнейших после второго заезда неопределены.
Вроде ничего не перепутал :)