Задача про лошадок

Один забег. Выпускай всех лошадей сразу, там полосы не отделены разделительной полосой, один фиг, самые быстрые и из конца в топы пробьются. Это как если Шумахер провалил квалификацию, и стартует из хвоста, один фиг, первым придёт.

Не, за раз можно всё-таки только пять лошадей максимум выпускать, иначе нет никакой гарантии.

Придумал за 11 забегов.

11?

Так тебе надо трех самых быстрых, а секундомера нет, то есть вероятность что три самых быстрых окажутся в одном забеге. То есть стратегия наверняка это выпускать по пять и отсеивать две худших, оставляя три лучших в каждом забеге.
Получается сначала 5 забегов. Потом 3 забега. Потом два и один. Всего 11.

Всех выпустить друг за другом. Самые быстрые будет видно, либо оторвутся, либо подожмутся к более медленным.

/thread

7 забегов. Достаточно простая алгоритмическая задача. Даже уже можно сказать каноническая :)

Кстати, вот есть очень хорошее объяснение.

[spoiler]https://www.youtube.com/watch?v=i-xqRDwpilM[/spoiler]

А еще можно пристрелить 22 из 25 :)

То есть не два и один. А то не так поймут. Когда осталось 9 лошадей, то в первом забеге отсеивается 2 и добавляется 2 из оставшихся 4. После второго отсева добавляются последние две. В 11 забеге участвуют 5.
Хотя можно сразу по этому принципу. Каждый раз отсеиваем 2 лошади и добавляем 2 из кучи. Получится все равно 11 забегов.

Расскажи как.

1. Провести 5 забегов по 5 лошадей. Получаем самых быстрых в подгруппах;

2. Устраиваем забег победителей - получаем точного #1 (самую быструю из 25);

3. Далее отбираем еще 5 лошадей (что-то типа «финала лузеров»):

- из «забега победителей» - 2 и 3 место (те кто проиграл во пп.2);

- претенденты из забегов п.1 в группе победителя «забега победителя» - 2 и 3 место;

- претендент из группы занявшего второе место в «забеге победителя» - 2 место.

Самый острый момент - это финал лузеров. Я выше дал ссылку на видео - там прямо все красиво в картинках показано.

Видео я только через час посмотрю.

Быстрее 11 не придумал. Если бы нужно было 2 лошади можно было бы уложиться в 7, а с одной в 6.

Начиная с третьего пункта не совсем понятно. Видео гляну позже. Например случай - в первой группе у тебя пять самых быстрых лошадей. Как в этом случае работает пункт три. У тебя только одна попытка.

Но ведь одна группа может быть просто абсолютно быстрее всех других лошадей и в этом случае алгоритм не работет.

Посмотри мои два варианта. Они за 11 забегов и точно работают.

Минимальное чисто перестановок для сортировки 5 чисел куда интереснее, если не гуглить.

Придумал за 8 забегов

Там в видосике все подробно расписано. Даже слишком подробно. Действительно сработает. Идея в том, что лошади из «забега победителей» дают оценку все своей подгруппе. В группе из которой лошадь пришла первой могут находится все три самых быстрых лошади. В группе со второй лошадью уже в принципе не может быть самой быстрой, максимум вторая и третья. В группе с третьей можно рассчитывать только на эту самую третью, а остальным группам ловить вообще нечего. Из первой группы берем вторую и третью, из второй — первую и вторую, из третьей — первую. Это наши претенденты, других быть не может.

Я понял вариант из видео, можно выкинуть из дополнительных забегов 2 группы, потому что если они в пятерке лучших не входят в топ 3, то в их группах тоже никто точно не входит. Тогда действительно остается 3 группы, из которых можно взять по 2 лошади.
Но из третьей нет смысла брать никого, потому что они всяко медленнее своего топа, вопрос только в том будет ли второй и третий номер первой или второй группы быстрее топа третей. Как раз набирается пять на забег, реально выходит 7 забегов.

Я тоже так подумал, но нет, работает.

1. Делаем пять забегов по пять лошадей - получаем 5 групп с победителем в каждой.
2. Делаем забег из победителей пяти групп - получаем абсолютного победителя.
3. Выкидываем две самые медленные группы, потому что если и есть где три самых быстрых лошади, так это в трёх самых быстрых группах.
Осталось три группы.
Формируем последний забег. Т.к. абсолютный победитель известен, то мы про него пока забываем. Второе место принадлежит второй лошади из самой быстрой группы или первой из второй по быстроте группы. Третье место принадлежит либо третьей лошади из самой быстрой группы, либо второй лошади из второй по скорости группы, либо первой лошади из третьей по скорости группы. Итого пять лошадей. Забег.
Берём абсолютного победителя и две самые быстрые из последнего забега - профит.

Я считаю данный пост не соблюдением Code of Conduct, обозначантем жестокого обращения с животными и так далее.

Хотя тоже 11 насчитал, но чую, что не оптимально.

Я, после того, как моя девушка, кстати генетик по образованию с пятым размером бюста и осиной талией, но не подумайте, что я хвастаюсь, хотя нет подумайте и завидуйте.
Так вот, когда я в порыве словоблудия начал с ней обсуждать за алгоритм word2vec она так непринужденно сказала «а, ну всё понятно, просто список Сводеша случайным образом распределяем по трехмерной сфере и далее по семантическому расстоянию между словами распределяем весь словарь используя матметоды из ОТО насчет искривления пространства», непринужденно помешивая поварешкой борщ.
Оказывается вокруг столько умных людей блин.

5 заездов по 5 лошадей, из каждого 5 самых быстрых лошадей на 6й заезд.

Что это и зачем это здесь?

ЧТо это и зачем это здесь?

Я, когда в зеркало смотрюсь, задаю себе тот же вопрос.

Лучше не стало, правда. Я просто попытался более-менее коротко и ясно описать решение :(

Видео не смотрел, но пока шел ел пороженку и думал как сократить до семи придумал, что после забега победителей можно таки получить победителя и пять претендентов на два места сразу. Если записать матрицей результаты групп после 6 забега и отобрать 6 левых верхних лошадей по диагонали.

Так я тоже в комменте до тебя попытался это сделать. Просто удивился, что столько людей поняло решение с первого раза, кто-то раньше чем я и без видяхи, и захотел поделиться опытом, что вокруг оказывается много дохрена умных людей.

Спасибо тс за задачу и тебе, что не поленился объяснить для ъ. :)

Какое минимальное число забегов вам понадобится, чтобы выбрать трёх самых быстрых лошадей?

использовать результаты прошлых забегов

// ваш К.О.

6 забегов:

3min(min(a1..a5), min(a6..a10), min(a11..a15), min(a16..a20), min(a21..a25))

Wrong. Второе место в первом забеге может быть быстрее первых мест в остальных.

Если все три быстрые лошади оказались в одной группе, то:

первая лошадь этой группы определится как победитель «забега победителей».

а вторая и третьи лошади - придут первой и второй в забеге «лузеров».

Давай-то глянем иначе.

Первым забегом (точнее пятью) мы определяем:

• лидера в группе (которая уйдет в «забег победителей»);
• двух аутсайдеров (4 и 5 место - они точно нам больше не интересны);
• двух «претендентов» (2 и 3 место. Они возможно входят в тройку лучших, если в других группах лошади хуже).

Шестым забегом («забег победителей») мы определяем несколько важных фактов:

• Двух аутсайдеров (4 и 5 место). Причем мы «выкидываем» как эти лошади, так и их первоначальные группы. Раз самая быстрая не вошла в тройку - значит и вся группа нас не интересует.
• Самую быструю лошадь. Она уже точно #1. Но мы должны учесть момент того, что 2 и 3 лошади в её группе могут быть нашим ответом. Значит этих двух лошадей ставим в последний забег («забег лузеров»)
• Вторая быстрая лошадь «забега победителей». Но мы должны учесть, что в первой группе лошади 2,3 могут быть быстрее её. Значит добавляем её в «забег лузеров». Так же учитываем, что если та лошадь действительно будет 2-ой среди 25 лошадей, то у второй лошади в забеге её группы есть шансы оказаться третьей среди 25. Поэтому добавляем и её.
• Третья быстрая лошадь «забега победителей». Её мы тоже должны сравнить с претендентами. Добавляем в «забег лузеров».

Итого у нас в «забеге лузеров» принимают участие:

• второе место «забега победителей»
• третье место «забега победителей»
• второе место в подгруппе победителя «забега победителей»
• третье место в подгруппе победителя «забега победителей»
• второе место в подгруппе лошади, занявшей второе место в «забеге победителей»

5 заездов по 5 лошадей, из каждого 5 самых быстрых лошадей на 6й заезд.

Так выбирают только лидеров групп. В отдельных группах могут быть лошади, которые пришли за лидером своей группы, но они могут быть сильнее лидеров других групп - просто они с ними ни разу не соревновались. Алгоритм требует ранжирования по силе между всем списком особей, только тогда можно выбрать первых трёх действительно самых сильных, не опираясь на групповую градацию силы. Кто помнит алгоритм сортировки большого списка с ограничением на память/стек? Так вот, количество лошадей - длина этого списка, размер памяти для сортировки или число ячеек на стеке - количество беговых дорожек. Число забегов до определения первых трёх самых быстрых лошадей - вычислительная сложность алгоритма сортировки.

Вносите Vit с медианами!

Да, спасибо, я уже ранее догадался сам.

Это как если Шумахер провалил квалификацию, и стартует из хвоста, один фиг, первым придёт

Его даже я обгоню.

Когда он сейчас с дырой в голове, и ходит под себя, разумеется, обгонишь

1 забег. Первых трех пришедших объявляешь победителями, остальных на мясо.

5 размер бюста не нужен-будешь снизу задушит ненароком.

Я тоже так думал, оказалось на женщине которая надев каблуки становится моего роста, 5 размер весьма органично смотрится, рост у меня 190 см, современная школота смотрит сверху и тихо посмеивается.
Если женщине не 60+ лет, не рожала и не совсем не повезло с грудью оно ж смотрится как второй только в объеме существенно больше.

Минимальное чисто перестановок для сортировки 5 чисел куда интереснее, если не гуглить.

можно сортировать без перестановок

Ты и в жизни всегда так, когда ставят условия, пытаешься их обходить?

В отдельных группах могут быть лошади, которые пришли за лидером своей группы

Почему? Здесь нету этапов гонок, это одна гонка и основной критерий тут - время и скорость, если 1 лошадь быстрее остальных 4х, значит у нее величина скорости = Х, тогда как у остальных 4х < X, означает, что если эту лошадь оббежит любая другая, её скорость = > X. и соответственно > чем все те 4 лошади из пары этого лидера.

На беговой дорожке только для 5 лошадей место.

Потому что все три быстрые лошади могут оказаться в одной и той же группе. В других группах будут лидеры, которые слабее этих трёх. По-твоему выходит, что выбирать нужно только лидеров групп, а остальных на мясо. 6 забегов приведут к потерям по крайней мере двух ценных кадров, останутся «середнячки» с одним безусловным лидером гонки.

Нет же, почему? Мы 25 лошадей делим на 5 групп, по 5 лошадей, и из каждой группы свой объективный лидер, быстрее всех остальных лошадей, 5 лошадей > 1 лошадь быстрее остальных 4х, соответственно остальные 4 лошади априори слабее этой лошади, и так с каждой группой, затем забег всех 5 лидеров. Соответственно каждый лидер в себе содержит объективное преимущество над всеми в своей группе и таким образом если кто-то быстрее этого лидера, равно тому, что он автоматически быстрее и всех лошадей в группе этого лидера.