победитель |
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 дает количество победителей. Особо смущает факт, что сортировка должна быть стабильной. А это сразу увеличивает время, особенно на больших количествах. Это наталкивает на грустную мысль, что само решение неверное. Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение. |
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Найти и вывести в выходной файл количество лучших спортсменов. Извиняюсь, но не вполне врубился в условие. Можешь привести пример?-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
passat |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
Извиняюсь, но не вполне врубился в условие. Можешь привести пример? Тот, что есть, не помогает: 1 2 3 2 3 1 3 1 2 Ответ : 3 Если бы нужно было всего лишь просуммировать места, то было бы слишком просто. Единственная засада - переполнение - решается на полсчета. Единственный пример данных не отвечает на вопрос, заданный предыдущим оратором. |
Lapp |
Сообщение
#4
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Тот, что есть, не помогает: Ну, положим, это был не вопрос, а просьба..)) И кое-что этот пример "поясняет". Поясняет, что я, оказывается, понимаю еще меньше, чем думал)). По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других. Например, 1 лучше всех в первой попытке, но хуже всех во второй и всего средний в третьей. И так про каждого можно сказать. Откуда 3? 1 2 3 2 3 1 3 1 2 Ответ : 3 ... Единственный пример данных не отвечает на вопрос, заданный предыдущим оратором. Давненько я не чувствовал себя так тупо.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
Сообщение
#5
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других. Например, 1 лучше всех в первой попытке, но хуже всех во второй и всего средний в третьей. И так про каждого можно сказать. Откуда 3? Давненько я не чувствовал себя так тупо.. У Частично Упорядоченного Множества (а мы имеем дело именно с ним) есть понятия "максимального элемента" и "наибольшего". "Максимальный" - это того, для которого нет элемента больше него. "Наибольший" - это тот, который больше всех других. В данном случает нужны максимальные элементы, в данно случае их три - для любого спортсмена нет того, который был бы лучше него, просто потому, что их в данном случае нельзя сравнивать. Добавлено через 3 мин. Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка Если я правильно понял, что вы имеете в виду, то боюсь, что это плохой вариант. Если один спортсмен занял 1, 2, 3 места, а другой - 2, 3, 4, то явно первый лучше второго, но при этом соответствующие им отрезки пересекаются. -------------------- |
Текстовая версия | 4.05.2024 18:59 |