В общем, ко II этапу ВОШ я решил основательно подготовиться! И нашел такую задачу: Ее полное условие с интереснейшей предысторией (как это бывает практически на всех олимпиадах) достаточно длинно, так что я приведу его короткий аналог. Дано N отрезков. Можно ли составить хотя-бы один многоугольник из этих отрезков (количество используемых отрезков произвольно, многоугольник несамопересекающийся)
Вход: В первой строке входного файла лежит N (1 <= N <= 50) Затем в N строках находятся длины отрезков (все они целые, не превосходят по модулю 10000)
Выход: Вывести Yes если это возможно, No - если невозможно. ================================================================
Ну так вот, кроме как полным перебором, решить я ее не могу. Может есть более рациональное решение? [quote]Ничто не истина, всё дозволено[/quote]
Вот к примеру у нас есть три отрезка длиной 5,8,4 см. Из них можно составить многоульник.
Да, можно. А вот для 2, 5, 8, то уже это станет невозможным, но если к ним добавить еще например 6, то сможет получиться четырехугольник. Или треугольник со сторонами 5, 8, 6. [quote]Ничто не истина, всё дозволено[/quote]
Сообщение отредактировал Lord_F - Среда, 09 Ноября 2011, 19:38
Не представляю как можно обойтись без перебора. Единственный оптимизационный шаг который я вижу это сначала найти наибольший отрезок, а потом сумму остальных.
сначала найти наибольший отрезок, а потом сумму остальных.
уже облегчает алгоритм. Спасибо.
Добавлено (09.11.2011, 19:51) --------------------------------------------- А вот интересно, в худшем случае для данной задачи, такой алгоритм пройдет ли в 1 секунду?
Ну, вообще, мне учитель говорил, что паскаль делает 10^9 операций в секунду. Код позже напишу, если пройдет, отправлю конечно. [quote]Ничто не истина, всё дозволено[/quote]
Ну, вообще, мне учитель говорил, что паскаль делает 10^9 операций в секунду.
Quote (Lord_F)
А что смешного.
То что паскаль не может делать никаких операций, этим процессор занимается. Паскаль же, а точнее его компилятор, лишь преобразовывает программный код в машинный язык и уже этот машинный язык обрабатывает процессор. Колличество операций в секунду будет зависить от манины, а не от языка. Скорость выполнения самой программы может зависить от компилятора, в связи с генерацией более отпимального кода или с лучшей совместимостью с конкретной ЭВМ, но это уже другая история.
А-а, ну тогда ладно. Просто нам говорили при подсчете сложности алгоритма ориентироваться на максимум 10^9 операций
Добавлено (10.11.2011, 17:27) --------------------------------------------- О да! Я решил ее! Все тесты пройдены. Кому интересно, пишите в ЛС, отправлю. Только в конце концов мне удобнее стало писать ее на java, так что имейте в виду. Кстати, нужно было сделать еще одну вещь, о которой я забыл сначала. [quote]Ничто не истина, всё дозволено[/quote]
Сообщение отредактировал Lord_F - Четверг, 10 Ноября 2011, 17:28
