Воскресенье, 29 Марта 2020, 12:25

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Форум игроделов » Программирование » Delphi/Pascal/Object Pascal » Помогите решить простую геометрическую задачу (Пожалуйста))
Помогите решить простую геометрическую задачу
Lord_FДата: Среда, 09 Ноября 2011, 19:04 | Сообщение # 1
Любопытный Игродел
Сейчас нет на сайте
В общем, ко II этапу ВОШ я решил основательно подготовиться!
И нашел такую задачу:
Ее полное условие с интереснейшей предысторией (как это бывает практически на всех олимпиадах) достаточно длинно, так что я приведу его короткий аналог.
Дано N отрезков. Можно ли составить хотя-бы один многоугольник из этих отрезков (количество используемых отрезков произвольно, многоугольник несамопересекающийся)

Вход:
В первой строке входного файла лежит N (1 <= N <= 50)
Затем в N строках находятся длины отрезков (все они целые, не превосходят по модулю 10000)

Выход:
Вывести Yes если это возможно, No - если невозможно.
================================================================

Ну так вот, кроме как полным перебором, решить я ее не могу.
Может есть более рациональное решение?


[quote]Ничто не истина, всё дозволено[/quote]
0x90Дата: Среда, 09 Ноября 2011, 19:16 | Сообщение # 2
участник
Сейчас нет на сайте
Quote (Lord_F)
Дано N отрезков. Можно ли составить хотя-бы один многоугольник из этих отрезков

deleted


Сообщение отредактировал 0x90 - Среда, 09 Ноября 2011, 19:25
Lord_FДата: Среда, 09 Ноября 2011, 19:24 | Сообщение # 3
Любопытный Игродел
Сейчас нет на сайте
Quote (Lord_F)
количество используемых отрезков произвольно

То есть, грубо говоря, можно использовать любые из этих N отрезков.


[quote]Ничто не истина, всё дозволено[/quote]

Сообщение отредактировал Lord_F - Среда, 09 Ноября 2011, 19:26
0x90Дата: Среда, 09 Ноября 2011, 19:27 | Сообщение # 4
участник
Сейчас нет на сайте
Все равно никак не могу понять условие задачи. Вот к примеру у нас есть три отрезка длиной 5,8,4 см. Из них можно составить многоульник?

Сообщение отредактировал 0x90 - Среда, 09 Ноября 2011, 19:28
Lord_FДата: Среда, 09 Ноября 2011, 19:32 | Сообщение # 5
Любопытный Игродел
Сейчас нет на сайте
Quote (0x90)
Вот к примеру у нас есть три отрезка длиной 5,8,4 см. Из них можно составить многоульник.

Да, можно.
А вот для 2, 5, 8, то уже это станет невозможным, но если к ним добавить еще например 6, то сможет получиться четырехугольник.
Или треугольник со сторонами 5, 8, 6.


[quote]Ничто не истина, всё дозволено[/quote]

Сообщение отредактировал Lord_F - Среда, 09 Ноября 2011, 19:38
Max_GamedevДата: Среда, 09 Ноября 2011, 19:34 | Сообщение # 6
почетный гость
Сейчас нет на сайте
0x90, нет, нельзя

Добавлено (09.11.2011, 19:34)
---------------------------------------------
Я думаю так: длина каждого из отрезков больше, чем сумма остальных

MatouДата: Среда, 09 Ноября 2011, 19:39 | Сообщение # 7
Исходный коТ
Сейчас нет на сайте
Не представляю как можно обойтись без перебора. Единственный оптимизационный шаг который я вижу это сначала найти наибольший отрезок, а потом сумму остальных.


Lord_FДата: Среда, 09 Ноября 2011, 19:39 | Сообщение # 8
Любопытный Игродел
Сейчас нет на сайте
Quote (Max_Gamedev)
Я думаю так: длина каждого из отрезков больше, чем сумма остальных

Эм, ТАКОЕ невозможно никогда))
Хотя бы "метод крайнего" применить, или уж здравый смысл.


[quote]Ничто не истина, всё дозволено[/quote]
Max_GamedevДата: Среда, 09 Ноября 2011, 19:40 | Сообщение # 9
почетный гость
Сейчас нет на сайте
Lord_F, тьфу, наоборот - меньше
Lord_FДата: Среда, 09 Ноября 2011, 19:51 | Сообщение # 10
Любопытный Игродел
Сейчас нет на сайте
Quote (Matou)
Не представляю как можно обойтись без перебора.

Ну, в принципе, да.
А вот
Quote (Matou)
сначала найти наибольший отрезок, а потом сумму остальных.

уже облегчает алгоритм.
Спасибо.

Добавлено (09.11.2011, 19:51)
---------------------------------------------
А вот интересно, в худшем случае для данной задачи, такой алгоритм пройдет ли в 1 секунду?


[quote]Ничто не истина, всё дозволено[/quote]
Max_GamedevДата: Среда, 09 Ноября 2011, 20:03 | Сообщение # 11
почетный гость
Сейчас нет на сайте
Смотря на чем
0x90Дата: Среда, 09 Ноября 2011, 20:15 | Сообщение # 12
участник
Сейчас нет на сайте
Quote (Lord_F)
А вот интересно, в худшем случае для данной задачи, такой алгоритм пройдет ли в 1 секунду?

На паскале? Вобщем если у них там не ископаемые компьютеры должен пойти без проблем. Кстати, ты мне код потом покажи, ок? Интересно просто smile


Сообщение отредактировал 0x90 - Среда, 09 Ноября 2011, 20:16
Lord_FДата: Среда, 09 Ноября 2011, 20:21 | Сообщение # 13
Любопытный Игродел
Сейчас нет на сайте
Ну, вообще, мне учитель говорил, что паскаль делает 10^9 операций в секунду.
Код позже напишу, если пройдет, отправлю конечно.


[quote]Ничто не истина, всё дозволено[/quote]
0x90Дата: Среда, 09 Ноября 2011, 20:26 | Сообщение # 14
участник
Сейчас нет на сайте
Quote (Lord_F)
Ну, вообще, мне учитель говорил, что паскаль делает 10^9 операций в секунду.

Улыбнуло. Веселый у вас учитель) Сорри за оффтоп.
Max_GamedevДата: Среда, 09 Ноября 2011, 21:09 | Сообщение # 15
почетный гость
Сейчас нет на сайте
У нас учитель получил орден за заслуги перед Отечеством 2ой степени, так что не надо
anton-garДата: Среда, 09 Ноября 2011, 21:53 | Сообщение # 16
WEBmaster
Сейчас нет на сайте
Длина каждого из отрезков меньше, чем сумма остальных.

Lord_FДата: Четверг, 10 Ноября 2011, 12:28 | Сообщение # 17
Любопытный Игродел
Сейчас нет на сайте
Quote (Lord_F)
Ну, вообще, мне учитель говорил, что паскаль делает 10^9 операций в секунду.

Ну то есть ориентироваться надо на такое число операций.
А что смешного.
И вообще,
Quote (Max_Gamedev)
У нас учитель получил орден за заслуги перед Отечеством 2ой степени, так что не надо



[quote]Ничто не истина, всё дозволено[/quote]
MatouДата: Четверг, 10 Ноября 2011, 15:01 | Сообщение # 18
Исходный коТ
Сейчас нет на сайте
Quote (Lord_F)
Ну, вообще, мне учитель говорил, что паскаль делает 10^9 операций в секунду.

Quote (Lord_F)
А что смешного.

То что паскаль не может делать никаких операций, этим процессор занимается. Паскаль же, а точнее его компилятор, лишь преобразовывает программный код в машинный язык и уже этот машинный язык обрабатывает процессор. Колличество операций в секунду будет зависить от манины, а не от языка. Скорость выполнения самой программы может зависить от компилятора, в связи с генерацией более отпимального кода или с лучшей совместимостью с конкретной ЭВМ, но это уже другая история.

Ваш кэп!



Lord_FДата: Четверг, 10 Ноября 2011, 17:27 | Сообщение # 19
Любопытный Игродел
Сейчас нет на сайте
А-а, ну тогда ладно. Просто нам говорили при подсчете сложности алгоритма ориентироваться на максимум 10^9 операций

Добавлено (10.11.2011, 17:27)
---------------------------------------------
О да! Я решил ее! Все тесты пройдены.
Кому интересно, пишите в ЛС, отправлю.
Только в конце концов мне удобнее стало писать ее на java, так что имейте в виду.
Кстати, нужно было сделать еще одну вещь, о которой я забыл сначала.


[quote]Ничто не истина, всё дозволено[/quote]

Сообщение отредактировал Lord_F - Четверг, 10 Ноября 2011, 17:28
Форум игроделов » Программирование » Delphi/Pascal/Object Pascal » Помогите решить простую геометрическую задачу (Пожалуйста))
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2020 Рейтинг