Автор |
Сообщение |
16.10.2006 17:58:57
Тема: ALIBB
|
Михаил Еськов
Темы: 5
Сообщений: 17
Мой профиль
|
Sp292 Alibaba Rus
Eng
code:ALIBB
На прямой заданы N точек с положительными координатами (N<10000)
Для каждой точки задано время до которого её надо посетить. Мы можем начать движение с ЛЮБОЙ точки. 1 единицу расстояния проходим за 1 единицу времени. Мы должны посетить ВСЕ точки, причём каждую точку надо посетить до истечения её срока.
Требуется определить наименьшее время требуемое для посещения всех точек. ( No solution если не существует такого маршрута).
(в файле до 10 тестов)
Понятно, что на любом шаге посещённые точки описываются отрезком
(L,R). т.е. все x такие что L<=x<=R мы уже посетили . Понятно что закончим посещение отрезка (L,R) в одной из двух точек L или R.
(Точно также весь путь мы закончим либо в самой левой точке либо в самой правой точке)
Самое быстрое решение которое приходит в голову это динамика
F(L,R,Flag)-Минимальное время за которое мы посетим отрезок (L,R) если начнём путь где-нибудь внутри отрезка а закончим в L (если Flag=0) или в R(Если Flag=1). Просчитывать эту динамику можно, но в любом случае это как минимум N^2
а это много (да ещё и 10 тестов!).
В общем кто знает решение быстрее чем за за N^2 отзовитесь.
______________________
=====
|
20.10.2006 16:49:22
Тема: Re:ALIBB
|
Геннадий Короткевич
Темы: 6
Сообщений: 37
Мой профиль
|
http://www.spoj.pl/status/michael,ALIBB/
Время на тест - 5 секунд.
Скорее всего, это был какой-нибудь оптимизированный N^2...
______________________
Nothing is impossible; impossible itself says: "I m possible"...
|
21.10.2006 09:17:07
Тема: Re:ALIBB
|
Михаил Долинский
Темы: 1982
Сообщений: 47186
Мой профиль
|
Гена - пожалуйста, разверни (обоснуй) свою тезу об оптимизированном N^2 при времени на тест 5 секунд. А то получается, что Миша правильно решил задачу, а думает что не решил. И так про все 10 задач, на которыми ему поручили работать.
Миша - пиши свои мысли по-поводу ОСТАЛЬНЫХ задач поскорее!
|
|