IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> победитель
passat
сообщение 17.03.2009 10:14
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

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

Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
Archon
сообщение 2.04.2009 8:30
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

Рассмотрим пример 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 8:32


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
passat
сообщение 3.04.2009 17:39
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


Цитата(Archon @ 2.04.2009 9:30) *

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

Интересная трактовка задачи. В такой постановке, Вы , возможно, правы.

Похоже, способа проверить, кроме как сдать, не существует. Т.к. возможны разные трактовки условия.

Интересно, а задача уже где-то встречалась? Есть живые тесты, чтобы разобраться?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
passat   победитель   17.03.2009 10:14
maksimla   если я правильно понял по строчкам Считается, что...   17.03.2009 10:35
Lapp   Найти и вывести в выходной файл количество лучших ...   17.03.2009 11:27
passat   Извиняюсь, но не вполне врубился в условие. Може...   17.03.2009 12:32
Lapp   Тот, что есть, не помогает: 1 2 3 2 3 1 3 1 2 От...   18.03.2009 4:09
TarasBer   По моему разумению, ответ к этим данным должен бы...   18.03.2009 15:37
Lapp   У Частично Упорядоченного Множества (а мы имеем де...   19.03.2009 3:20
passat   Если я правильно понял, что вы имеете в виду, то ...   27.03.2009 20:17
TarasBer   Поняли, видимо, правильно. В Вашем примере Вы отб...   29.03.2009 23:36
passat   А ну и что? Первый спортсмен - один из лучших, пр...   1.04.2009 15:48
maksimla   мне тогда кажется надо все серавно слапить три рез...   18.03.2009 10:28
passat   Это было бы слишком просто. Непонятно, в чем смыс...   18.03.2009 12:25
Lapp   А прояснить условие негде?   18.03.2009 13:06
passat   К сожалению, нет. Давайте исходить из того, что пр...   18.03.2009 14:13
TarasBer   Лучший - это не тот, который лучше всех остальных....   19.03.2009 13:05
volvo   В таком случае, зачем проводятся соревнования? Поп...   19.03.2009 13:38
TarasBer   В таком случае, зачем проводятся соревнования? По...   19.03.2009 13:48
Lapp   не верите, что он лучший - тогда назовите того, кт...   19.03.2009 14:12
TarasBer   O'kay, согласен. Возникла некоторая путаница...   19.03.2009 14:55
Archon   Интересная задачка, правда явно олимпиадная, поэто...   2.04.2009 8:30
passat   Другой пример Lapp'а. 3 4 2 1 2 3 4 1 1 2 4 3...   3.04.2009 17:39


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 21.06.2025 22:37
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"