У вас 25 лошадей. В каждой скачке может участвовать не больше 5 лошадей. Требуется определить первую, вторую, третью по скорости лошадь. Найдите минимальное количество скачек, позволяющих решить эту задачу.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 22:09:21 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
7 [:||||||||||||||||||||:]
Если интересно решать такие задачи могу посоветовать сайт braingames.ru там всегда есть новые задачки.
я просто хочу узнать ответы других
у меня получилось 12, объясню: пусть 1 — лошадь, которая в игре, 0 — выбывшая лошадь.
1)
11111
11111
11111
11111
11111
2)
00000
00000
11111
11111
11111
Ans=5
3)
00000
00000
00111
00111
00111 Ans=5+3=8
4)
00000
00000
00000
00111
00111 Ans=8+2=10
5)
возьмем произвольно 5 лошадей, 2 из них выбыло, получилось следующее --> 00000
00000
00000
00001
00111 Ans=10+1=11
6) у нас осталось 4 лошади, и еще за один раз мы найдем тройку победителей Ans=11+1=**12**
Смотри, нам нужно найти:
-лошадь, которая быстрее каждой из 24 остальных лошадей;
-лошадь, которая быстрее каждой из оставшихся 23;
-лошадь, которая быстрее каждой из оставшихся 22.
Тогда нам нужно получить 24+23+22 ребр в графе, где ребро означает что i-ая лошадь быстрее чем j-ая.
1 заезд нам дает (5X(5-1))/2 ребр.
Тогда нам нужно провести (24+23+22)/((5X(5-1))/2) заездов, тоесть 6.9=7.
Вроде неправда же. Лошадь X быстрее Y <=> есть путь из X в Y, а не просто ребро.
В худшем случаи у нас никогда не будет пути из X в Y, поэтому нужно их соединять на прямую.
Тогда, чтобы решение было полное, нужно доказать, что такой случай всегда будет.
5 раз делаем скачки, каждый раз выбирая новых лошадей (1-5, 6-10, 11-15, 16-20, 21-25).
В 6 раз проводим скачки между победителями первых 5 заездов. Здесь мы определили лучшую лошадь. Также мы отсекли лошадей, пришедших 4 и 5 в 6-ом заезде.
Теперь кто может претендовать на 2 и 3 место — лошади, занявшие 2 и 3 место в заезде с победителем (заезд среди первых 5), лошадь на 2 месте из 6 заезда, лошадь, занявшая 2 место в заезде с предыдущей лошадью, лошадь на третьем месте в 6 заезде. Ровно 5.
Проводим 7 скачки и выявляем 2 и 3 место.
Например, пусть к 6 заезду лидеры (2, 8, 11, 20, 24). В 6 заезде места распределились как (11, 8, 20, 24, 2). Отсюда лошадь 11 — самая быстрая, а лошади 24 и 2 — точно не 2 и 3 по скорости.
Тогда в 7 заезд возьмем 2 и 3 место из заезда 11-15, лошадь 8, лошадь на 2 месте из заезда 6-10, лошадь 20.
"лошадь на месте из заезда 6-10"
Возможно, вы имели ввиду лошадь на втором месте из заезда 6-10.
Да, действительно, это решение намного понятнее чем то, которое предложил я.
ну это не работает, если победитель гонки 3 бежит медленнее последнего места гонки 1.
Почему? Последнее место гонки 3 никогда не будет 3 по скорости среди всех, так как в своей группе он уже 5.
ну, к примеру пусть каждая лошадь пришла к финишу за время i, то есть первая за 1 секунду и тд. тогда очевидно, что любая лошадь первого забега ( даже пятая в нем) быстрее любой лошади из других забегов.
Пусть первые 5 забегов обозначим как группы, тогда 1-я группа 1-5, 2-ая 6-10 и тд.
Обозначения:
-победитель — пришел первый в 6 забеге;
-серебряный призер — пришел вторым в 6 забеге;
-бронзовый призер — пришел третьим в 6 забеге.
Нам нужно найти только 3 лучшие.
Для последнего забеге мы берем:
-из группы победителя 2 и 3 по скорости;
-из группы серебряного призера 1 и 2 по скорости;
-из группы бронзового призера 1 по скорости.
В последний забег мы добавили всех кто может претендовать быть вторим или третьим по скорости.
оу, я ступил, нам же только первых 3 надо