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

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

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

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> победитель
сообщение
Сообщение #1


Новичок
*

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

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


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

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

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

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


Знаток
****

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

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


если я правильно понял по строчкам

Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его.
Найти и вывести в выходной файл количество лучших спортсменов.


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

может правильно а может нет не знаю я думай сам smile.gif


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(passat @ 17.03.2009 10:14) *
Найти и вывести в выходной файл количество лучших спортсменов.
Извиняюсь, но не вполне врубился в условие. Можешь привести пример?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

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

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


Цитата(Lapp @ 17.03.2009 12:27) *

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

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

1 2 3
2 3 1
3 1 2

Ответ : 3


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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(passat @ 17.03.2009 12:32) *
Тот, что есть, не помогает:

1 2 3
2 3 1
3 1 2

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Знаток
****

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

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


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


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

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

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


Цитата

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

Это было бы слишком просто. Непонятно, в чем смысл задачи. sad.gif
Выбор минимального (и подсчет) - тривиальная задача, выполняемая за линейное время. Единственный подводный камешек - опасность переполнения - обходится легким заведением дополнительного поля.

Цитата
По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других.

Это уже вопрос вкуса. smile.gif
Как в том анекдоте: из двух спорсменов один обязательно будет вторым, а другой - предпоследним. smile.gif

Говорю, что не объясняет, т.к. единственный пример допускает толкование условия задачи как банального суммирования мест.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


А прояснить условие негде?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

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

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


К сожалению, нет.
Давайте исходить из того, что правильно мое. Т.к. для суммы мест решение я знаю. Если надо, логику могу написать, но вроде она банальна. Единственный подводный камень описал: возможно переполнение. Т.е. надо иметь дополнительный байт/два байта для подсчета переполнений. Или увеличить размерность поля суммы, но тогда непроизводительно может расходоваться память.

Кстати, пока писал и пытался сформулировать задачу пришел к интересной идее: у победителя/ей худшее место должно быть лучше, чем у остальных лучшее. Нодо подумать, можно ли вытянуть из этого что-нибудь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Злостный любитель
*****

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

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


Цитата(Lapp @ 18.03.2009 4:09) *
По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других. Например, 1 лучше всех в первой попытке, но хуже всех во второй и всего средний в третьей. И так про каждого можно сказать. Откуда 3? blink.gif
Давненько я не чувствовал себя так тупо..


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


Добавлено через 3 мин.
Цитата(passat @ 17.03.2009 10:14) *

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


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(TarasBer @ 18.03.2009 15:37) *
У Частично Упорядоченного Множества (а мы имеем дело именно с ним) есть понятия "максимального элемента" и "наибольшего". "Максимальный" - это того, для которого нет элемента больше него. "Наибольший" - это тот, который больше всех других. В данном случает нужны максимальные элементы, в данно случае их три - для любого спортсмена нет того, который был бы лучше него, просто потому, что их в данном случае нельзя сравнивать.
Щаз завою.. жалко, луны нет..
TarasBer, правильно я понимаю, что ты имел в виду нестрогое (>=) и строгое (>) неравенства для определений максимального и наибольшего элемента соответственно? Я не против, хотя мне представляется несколько неуместной такая дискриминация русского языка по отношению к латыни (максимальный получается как бы главнее - шутка, конечно smile.gif)). Но при чем тут это? Я как не понимал, так и не понимаю, как в примере получилось 3. Честно, я не рисуюсь, поверьте, аж самому обидно.. Объясните для идиотов, плз. И вообще, пожалуйста, подкрепляйте ваши рассуждения примерами.

Я понимаю условие буквально (а как еще?). Вот пример, когда 2 лучше 1:

3 4 2 1
2 3 4 1
2 1 4 3

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

3 4 2 1
2 3 4 1
1 2 4 3

И вообще, понятие "лучший" определено только относительно кого-то еще. Абсолютно лучший (лучше всех остальных) может быть только один. Я готов принять без лишних разговоров, что в условии (в вопросе) идет речь о тех, кто лучше хоть кого-то. Но в примере passat'а таких нет совсем. Следовательно, ответ должен быть 0.
Вот мое понимание. Жду вашего..
Или, на худой конец, приведите пример, где ответ 0 (не в моем понимании). Или хотя бы 1. Ну, 2.. Но только не ВСЕ участники, как в этом примере.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Злостный любитель
*****

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

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


Лучший - это не тот, который лучше всех остальных. Это тот, для которого нет никого лучше него.
Чувствуете разницу?
То есть он лучше всех, с кем его можно сравнавить. А если его сравнивать ни с кем нельзя - значит нет никого лучше него. Значит он лучший.

Что касается определений, то это 1 курс, дискретная математика, теория множеств.

Например, на множестве из 5 элементов введём частичный порядок на графе так - один элемент считаем "больше" другого, если от первого ко второму можно провести путь, при движении по которому мы идём всё время вниз.
На графе, изображённом на рисунке - элементы 1 и 2 максимальные, но не наибольшие.
Элемент 5 - наименьший. И минимальный тоже, соответственно.
В случае с 3 спортсменами мы имеем 3 несвязанных точки. Каждая из них, конечно же, максимальна и минимальна. Но не наибольшая и не наименьшая.

> Или, на худой конец, приведите пример, где ответ 0 (не в моем понимании).
> Или хотя бы 1. Ну, 2.. Но только не ВСЕ участники, как в этом примере.

Ответ бывает 0 - только если спортсменов нет. В любом непустом конечном ЧУМе есть максимальный элемент.
Один лучший спортсмен - это когда во всех состязаниях один и тот же победитель.
Двое лучших - вот как я тут привёл.

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


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






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

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

Добавлено через 1 мин.
Цитата
Двое лучших - вот как я тут привёл.
Чего ты привел? Рисунок этот? Ты таблицу приведи...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Злостный любитель
*****

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

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


Цитата(volvo @ 19.03.2009 13:38) *

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

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

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


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(TarasBer @ 19.03.2009 13:48) *
не верите, что он лучший - тогда назовите того, кто лучше него. Нет таких? Нету. Значит он лучший.
Господи, 1 курс, теория множеств.
O'kay, согласен. Возникла некоторая путаница в терминах "лучший" и "лучший среди всех". Если есть многословные термины ("А является лучшим среди всех, если нет никого лучше его"), то надо их употреблять аккуратнее. А в вопросе стоит: "Найти и вывести в выходной файл количество лучших спортсменов". И разбирайся, какой именно термин имелся в виду..

Цитата(TarasBer @ 19.03.2009 13:48) *
Упырьте мел.
- это как? blink.gif не понимаю..

Цитата(TarasBer @ 19.03.2009 13:48) *
Господи, 1 курс, теория множеств.
Господи тут ни при чем. Условие писать нужно четче.



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Злостный любитель
*****

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

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


Цитата(Lapp @ 19.03.2009 14:12) *

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

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

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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

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

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


Цитата(TarasBer @ 18.03.2009 16:37) *

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

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

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

Господа, места не могут повторяться.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Злостный любитель
*****

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

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


Цитата(passat @ 27.03.2009 21:17) *

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


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

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

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


Цитата(TarasBer @ 30.03.2009 0:36) *

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

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

Теперь касательно Вашего замечания. В том и дело, что худшими (если брать критерий от противного) будут те спортсмены, у которых лучшее место будет хуже, чем у остальных. Иначе говоря, лучшие по условию задачи спортсмены должны образовать замкнутую группу. Т.е. группу связанных отрезков. Отношения между отрезками в этой группе нам по условию не интересны. Или в терминах спортсменов: пусть даже первый будет хоть трижды лучше второго. Но найдется хотя бы одна попытка, в которой некто четвертый или пятый будет лучше первого, проиграв первому (и даже второму) в остальных. Это единственное лучшее место четвертого включает его в число победителей.
Таким образом, победителями становятся: первый, второй и четвертый.

Ну и т.д.

Хотелось бы критики решения. Т.к. готовых тестов (и решения задачи) у меня нет. А пойти неверным путем не хочется.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Профи
****

Группа: Пользователи
Сообщений: 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 -


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 29.03.2024 7:37
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name