ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1159. Fence

upper bound for binary search? why n*(sum of lengths) work?
Послано muhammad 10 апр 2011 13:53
i used 1e8 first and got wa14
latter used n*(sum of edge lengths) and got ac.

i found that for test 14 the curve goes up and at r=200.75 touches x axis then goes up until
x=around 450 then down again with asymptote as x axis. so i tried to use tenary search to find upper bound but it does not always work. why n*sum of lengths work? is it weak tests or can somebody prove optimal upper bound?

please, help me understand.
thanks in advance.