ROI-2011 - Почта

Задача D. Почта ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Жюри ROI-2011	Ограничение времени:	5 сек
Входной файл:	post.in	Ограничение памяти:	256 Мб
Выходной файл:	post.out
Максимальный балл:	100

Условие

Внимание! Используется лишь часть тестов из оригинального набора!

В городе P планируется проведение реформы доставки почты. Вместо большого количества устаревших автомобилей приобретён специализированный Е-мобиль, задача которого — развозить всю корреспонденцию по почтовым отделениям города.

IT-отдел городской почты разработал кольцевой маршрут, проходящий через все почтовые отделения. Все улицы в городе P с односторонним движением. Необходимо выбрать почтовое отделение для размещения логистического центра, куда будет поступать вся городская корреспонденция перед её отправкой на Е-мобиле по маршруту. Из-за пробок скорость движения на участках маршрута между почтовыми отделениями зависит от времени суток. Размещение логистического центра считается оптимальным, если после отъезда из него в нулевой момент времени Е-мобиль развезёт корреспонденцию и возвратится в логистический центр как можно раньше. Время разгрузки корреспонденции пренебрежимо мало.

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

Формат входного файла

В первой строке задаётся целое положительное число N — количество почтовых отделений в городе P. Почтовые отделения нумеруются в порядке их следования по маршруту, начиная с единицы.

В следующих строках описаны N участков маршрута между почтовыми отделениями. Каждое описание содержит три строки:

в первой строке описания задаётся целое положительное число d_i — длина данного участка (d_i ≤ 10⁹), а также целое неотрицательное число E_i — количество отрезков времени, в течение каждого из которых скорость движения Е-мобиля постоянна;
во второй строке даны целые положительные числа t_i,j (1 ≤ j ≤ E_i, 0 < t_i,1 < … < t_{i,E_i} ≤ 10⁹) — значения моментов времени, в которые изменяется скорость движения. Если соответствующее E_i равно нулю, то эта строка — пустая;
в третьей строке целые положительные числа v_j – скорости на полуинтервале времени [t_i,j−1, t_i,j), где 1 ≤ j ≤ E_i+1, считается, что t_i,0 = 0, t_{i,E_i+1} = +inf.

Все числа в строках разделяются одним пробелом.

Формат выходного файла

В единственной строке необходимо вывести номер почтового отделения, в котором нужно разместить логистический центр, а также время проезда Е-мобиля по маршруту. Ответ должен иметь абсолютную или относительную погрешность не более 10⁻⁹, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения |x − y| / max(1, |y|); не превышает 10⁻⁹.

Примеры тестов

№	Входной файл (`post.in`)	Выходной файл (`post.out`)
1	`2 3 2 1 1 2 4 2 2 3 1`	`2 2.833333`
2	`2 2 1 2 2 1 2`	`1 2.000000`