История изменений
Исправление MKuznetsov, (текущая версия) :
совершая забеги по Москве и время от времени заглядывая на ЛОР :
про то как гарантировано решить за 7 забегов уже выяснено, но
в лучшем случае 6 :-) существует решение когда есть вероятность получить искомое на 6 забеге.
случайным образом разбиваем лошадей на 5 групп и проводим первые 5 заездов. (прим.после этих заездов кандидатов на 1-2-3 места 15 штук). На 6-м заезде соревнуются 4(четыре) победителя и один гнедой занявший 3-е место в последней группе.
если этот гнедой в 6-м заезде приходит первым, то гонка завершена, фанфары и награждение победителей.
если приходит вторым, то 7-й заезд необходим, мы выясним победителей с точностью до места.
если приходит третьим, то можем выявить тройку победителей, но не решить кто из них них промеж собой быстрее.
если гнедой придёт на 4,5 место, вот тут надо подумать, но похоже на случай с 3-м местом...
PS/ в теории, алгоритм (не тот что приведён, а вообще оптимальное решение) должен давать асимптоматику меньше чем 7.
Исходная версия MKuznetsov, :
совершая забеги по Москве и время от времени заглядывая на ЛОР :
[cite] про то как гарантировано решить за 7 забегов уже выяснено, но
в лучшем случае 6 :-) существует решение когда есть вероятность получить искомое на 6 забеге. [/cite]
случайным образом разбиваем лошадей на 5 групп и проводим первые 5 заездов. (прим.после этих заездов кандидатов на 1-2-3 места 15 штук). На 6-м заезде соревнуются 4(четыре) победителя и один гнедой занявший 3-е место в последней группе.
если этот гнедой в 6-м заезде приходит первым, то гонка завершена, фанфары и награждение победителей.
если приходит вторым, то 7-й заезд необходим, мы выясним победителей с точностью до места.
если приходит третьим, то можем выявить тройку победителей, но не решить кто из них них промеж собой быстрее.
если гнедой придёт на 4,5 место, вот тут надо подумать, но похоже на случай с 3-м местом...
PS/ в теории, алгоритм (не тот что приведён, а вообще оптимальное решение) должен давать асимптоматику меньше чем 7.