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

[passat]

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

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

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

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

[Archon]

Интересная задачка, правда явно олимпиадная, поэтому место ей в другом разделе. Вот как я понял:

Рассмотрим пример Lapp'а.
3 4 2 1
2 3 4 1
2 1 4 3
Для первого и второго спортсменов нет никого, кто был бы "лучше" их. Поэтому они добавляются в число "лучших среди всех". Для третьего спортсмена есть другой спортсмен (четвёртый), который "лучше", потому что четвертый лучше третьего во всех попытках. Для 4-ого опять нет никого, кто был бы лучше. Ответ 3.

Другой пример Lapp'а.
3 4 2 1
2 3 4 1
1 2 4 3
Тут из числа лучших выбывают спортсмены 2 и 3. Так как есть первый, который во всех попытках лучше второго и четвёртый, который во всех попытках лучше третьего. Ответ 2.

То есть если спортсмена описать так:

Sportsman = record
	c1, c2, c3: Integer;
end;

То функция определения, лучше ли один спортсмен другого, будет выглядеть так:

function Better(s1, s2: Sportsman): Boolean;
begin
	result := (s1.c1 < s2.c1) and (s1.c2 < s2.c2) and (s1.c3 < s2.c3)
end;

Решать, думаю, надо так:
Введём массив "лучших" переменной длины. Изначально этот массив пустой. Добавим туда первого спортсмена. Далее, перебираем всех спортсменов начиная со второго и сравниваем их со всеми из массива "лучших". Если текущий спортсмен оказывается "лучше", чем какой-нибудь из массива, то ставим текущего спортсмена в массив на это место (то есть заменяем того, кто "хуже" на того, кто "лучше"). Если мы не нашли в массиве элемент, для которого текущий спортсмен был бы "лучше", добавляем текущего спортсмена как новый элемент.

Сообщение отредактировано: Archon - 2.04.2009 12:32