победитель Опции

[passat]

В состязаниях участвуют N (N - до 100000) спортсменов. Каждому даются три попытки. Входной файл содержит 3 строки с положением участников в каждой попытке (ни в одной из попыток невозможно двум и более человекам разделить одно место).
Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его.
Найти и вывести в выходной файл количество лучших спортсменов.

Реализацию напишу сам, но подскажите алгоритм.
Пока просматривается следующее.
Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка, задача сводится к определению количества связных областей в начале координатной прямой.
Т.е. реализация в самом общем виде что-то типа такого:
- считать данные в массив, где каждому спортсмену отводится по 2 позиции: на первой лучшее место, на второй худшее место
- с первой позицией связываем +1, со второй - -1 (можно использовать либо пару массивов, либо один, но с несколько более сложной структурой элементов - в принципе, это сейчас не интересует)
- сортируем массив (второй - по результатам первого)
- осталось посчитать сумму первых +/-1 до получения первого нуля.
Количество +1 дает количество победителей.

Особо смущает факт, что сортировка должна быть стабильной. А это сразу увеличивает время, особенно на больших количествах. Это наталкивает на грустную мысль, что само решение неверное.

Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение.

[Lapp]

Найти и вывести в выходной файл количество лучших спортсменов.

Извиняюсь, но не вполне врубился в условие. Можешь привести пример?

[passat]

Извиняюсь, но не вполне врубился в условие. Можешь привести пример?

Тот, что есть, не помогает:

1 2 3
2 3 1
3 1 2

Ответ : 3


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

Единственный пример данных не отвечает на вопрос, заданный предыдущим оратором.

[Lapp]

Тот, что есть, не помогает:

1 2 3
2 3 1
3 1 2

Ответ : 3
...
Единственный пример данных не отвечает на вопрос, заданный предыдущим оратором.

Ну, положим, это был не вопрос, а просьба..)) И кое-что этот пример "поясняет". Поясняет, что я, оказывается, понимаю еще меньше, чем думал)). По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других. Например, 1 лучше всех в первой попытке, но хуже всех во второй и всего средний в третьей. И так про каждого можно сказать. Откуда 3?
Давненько я не чувствовал себя так тупо..

[TarasBer]

По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других. Например, 1 лучше всех в первой попытке, но хуже всех во второй и всего средний в третьей. И так про каждого можно сказать. Откуда 3?
Давненько я не чувствовал себя так тупо..

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


Добавлено через 3 мин.

Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка

Если я правильно понял, что вы имеете в виду, то боюсь, что это плохой вариант. Если один спортсмен занял 1, 2, 3 места, а другой - 2, 3, 4, то явно первый лучше второго, но при этом соответствующие им отрезки пересекаются.

[passat]

Если я правильно понял, что вы имеете в виду, то боюсь, что это плохой вариант. Если один спортсмен занял 1, 2, 3 места, а другой - 2, 3, 4, то явно первый лучше второго, но при этом соответствующие им отрезки пересекаются.

Поняли, видимо, правильно.
В Вашем примере Вы отбросили третьего и четвертого спорсменов, убдь они неладны. А этого делать нельзя.
Т.е. введя данные для этих неучтенных, Вы получите, что первый не будет лучше второго, т.к. появится хотя бы один третий (в Вашем примере еще и четветый), который будет лучше первого хоят бы в одной попытке.

А тогда моя идея сработает правильно? Проблема, что тесты писать для разных ситуаций, да еще и не зная направления - долго.

Господа, места не могут повторяться.