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

[passat]

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

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

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

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

[volvo]

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

В таком случае, зачем проводятся соревнования? Попытки, в которых спортсмены соревнуются друг с другом - это что, так, для галочки, а совсем не сравнения, да? Всем троим выдать золото, ибо, оказывается, никого ни с кем нельзя сравнивать? Это теперь так делается?

Спортсмен №1 проиграл всем во второй попытке. Но все-таки, он ЛУЧШИЙ??? При каких условиях он будет ХУДШИМ, интересно?

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

Двое лучших - вот как я тут привёл.

Чего ты привел? Рисунок этот? Ты таблицу приведи...

[TarasBer]

В таком случае, зачем проводятся соревнования? Попытки, в которых спортсмены соревнуются друг с другом - это что, так, для галочки, а совсем не сравнения, да? Всем троим выдать золото, ибо, оказывается, никого ни с кем нельзя сравнивать? Это теперь так делается?

Упырьте мел. В рамках задачи это именно так делается. Спортсменов можно сравнивать, только если один прогирал другому ВО ВСЕХ состязаниях.

Спортсмен №1 проиграл всем во второй попытке. Но все-таки, он ЛУЧШИЙ??? При каких условиях он будет ХУДШИМ, интересно?

А он и худший тоже. И лучший, и худший. Каждый. Что вас удивляет?
Вы не верите, что он лучший - тогда назовите того, кто лучше него. Нет таких? Нету. Значит он лучший.
Господи, 1 курс, теория множеств.

Сообщение отредактировано: TarasBer - 19.03.2009 13:50

[Lapp]

не верите, что он лучший - тогда назовите того, кто лучше него. Нет таких? Нету. Значит он лучший.
Господи, 1 курс, теория множеств.

O'kay, согласен. Возникла некоторая путаница в терминах "лучший" и "лучший среди всех". Если есть многословные термины ("А является лучшим среди всех, если нет никого лучше его"), то надо их употреблять аккуратнее. А в вопросе стоит: "Найти и вывести в выходной файл количество лучших спортсменов". И разбирайся, какой именно термин имелся в виду..

Упырьте мел.

- это как? не понимаю..

Господи, 1 курс, теория множеств.

Господи тут ни при чем. Условие писать нужно четче.

[TarasBer]

O'kay, согласен. Возникла некоторая путаница в терминах "лучший" и "лучший среди всех". Если есть многословные термины ("А является лучшим среди всех, если нет никого лучше его"), то надо их употреблять аккуратнее. А в вопросе стоит: "Найти и вывести в выходной файл количество лучших спортсменов". И разбирайся, какой именно термин имелся в виду..

Тогда да - слово "среди всех" тут лишнее. Но пример призван был прояснить эту неточность.

- это как? не понимаю..

Это такая шуточная перестановка фразы "умерьте пыл".