|
|
|
|
|
|
|
Вернуться
| 21 coder, 29 сентября 2010 г. 15:35:41 | |
|
Нет, в С я написал оптимизированный перебор и через 1 мин. после его запуска получил все 20 ответов. Затем оставалось их вставить в код программы и сдать задачу.
|
|
|
| 22 Герасимов Виталий Игоревич, 29 сентября 2010 г. 15:34:14 | |
> Могу отправить свое решение тебе на почту, если хочешь.
Был бы рад
WitaliyProg@mail.ru
|
|
|
| 23 Герасимов Виталий Игоревич, 29 сентября 2010 г. 15:33:19 | |
понятно, спасибо.
а в С вы писали динамическое програмиирование?
|
|
|
| 24 coder, 29 сентября 2010 г. 15:32:24 | |
|
Могу отправить свое решение тебе на почту, если хочешь.
|
|
|
| 25 coder, 29 сентября 2010 г. 15:28:56 | |
|
Да в принципе реализация не такая уж и сложная. Прямо сказать такие алгоритмы, как бинарный поиск и троичный поиск, весьма простые. Правда в этой задаче нужно было аккуратно найти баланс между точностью ответа и временем работы программы. Изначально мое решение работало 15 сек. на максимальном тесте. Удалось понизить время до 0.349 сек. под конец контеста.
|
|
|
| 26 Герасимов Виталий Игоревич, 29 сентября 2010 г. 15:26:30 | |
короче здал на 10 баллов :(
Твоя идея теоретически проста, но реализовать сложно.
Али я ошыбаюсь?
|
|
|
| 27 coder, 29 сентября 2010 г. 15:24:18 | |
|
Да, 100. Что значит сделал "лобовик"?
|
|
|
| 28 Герасимов Виталий Игоревич, 29 сентября 2010 г. 15:22:14 | |
Я и думал над бинарником, но, к сожелению, не догадался к другой части :(
А сделал лобовик.
У тебя 100?
|
|
|
| 29 coder, 29 сентября 2010 г. 15:14:17 | |
|
А ты как решал?
|
|
|
| 30 coder, 29 сентября 2010 г. 15:12:40 | |
|
Выполняется бинарный поиск по ответу задачи. Надо только уметь определять, подходит ли нам громоотвод определенной фиксированной высоты. Это будем делать так: переберем на крыше какого дома мы его устанавливаем. Для фиксированного дома определим оптимальное положение громоотвода на крыше, чтобы максимальный из углов до всех вершин всех домов был как можно меньше (это можно сделать двумя троичными поисками, т.е. по каждой из координат). Сравниваем найденный максимальный угол с данным в задаче. Если меньше или равен, то данная высота подходит.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
