победитель |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
победитель |
passat |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
В состязаниях участвуют N (N - до 100000) спортсменов. Каждому даются три попытки. Входной файл содержит 3 строки с положением участников в каждой попытке (ни в одной из попыток невозможно двум и более человекам разделить одно место).
Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его. Найти и вывести в выходной файл количество лучших спортсменов. Реализацию напишу сам, но подскажите алгоритм. Пока просматривается следующее. Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка, задача сводится к определению количества связных областей в начале координатной прямой. Т.е. реализация в самом общем виде что-то типа такого: - считать данные в массив, где каждому спортсмену отводится по 2 позиции: на первой лучшее место, на второй худшее место - с первой позицией связываем +1, со второй - -1 (можно использовать либо пару массивов, либо один, но с несколько более сложной структурой элементов - в принципе, это сейчас не интересует) - сортируем массив (второй - по результатам первого) - осталось посчитать сумму первых +/-1 до получения первого нуля. Количество +1 дает количество победителей. Особо смущает факт, что сортировка должна быть стабильной. А это сразу увеличивает время, особенно на больших количествах. Это наталкивает на грустную мысль, что само решение неверное. Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение. |
volvo |
Сообщение
#2
|
Гость |
Цитата в данно случае их три - для любого спортсмена нет того, который был бы лучше него, просто потому, что их в данном случае нельзя сравнивать. В таком случае, зачем проводятся соревнования? Попытки, в которых спортсмены соревнуются друг с другом - это что, так, для галочки, а совсем не сравнения, да? Всем троим выдать золото, ибо, оказывается, никого ни с кем нельзя сравнивать? Это теперь так делается?Спортсмен №1 проиграл всем во второй попытке. Но все-таки, он ЛУЧШИЙ??? При каких условиях он будет ХУДШИМ, интересно? Добавлено через 1 мин. Цитата Двое лучших - вот как я тут привёл. Чего ты привел? Рисунок этот? Ты таблицу приведи... |
TarasBer |
Сообщение
#3
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
В таком случае, зачем проводятся соревнования? Попытки, в которых спортсмены соревнуются друг с другом - это что, так, для галочки, а совсем не сравнения, да? Всем троим выдать золото, ибо, оказывается, никого ни с кем нельзя сравнивать? Это теперь так делается? Упырьте мел. В рамках задачи это именно так делается. Спортсменов можно сравнивать, только если один прогирал другому ВО ВСЕХ состязаниях. Цитата Спортсмен №1 проиграл всем во второй попытке. Но все-таки, он ЛУЧШИЙ??? При каких условиях он будет ХУДШИМ, интересно? А он и худший тоже. И лучший, и худший. Каждый. Что вас удивляет? Вы не верите, что он лучший - тогда назовите того, кто лучше него. Нет таких? Нету. Значит он лучший. Господи, 1 курс, теория множеств. Сообщение отредактировано: TarasBer - -------------------- |
Текстовая версия | 7.05.2024 19:09 |