[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Обсуждение Sphere-задач
Автор Сообщение
Михаил Еськов

Темы: 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 отзовитесь.

______________________
=====
Геннадий Короткевич

Темы: 6
Сообщений: 37

Мой профиль
http://www.spoj.pl/status/michael,ALIBB/

Время на тест - 5 секунд.
Скорее всего, это был какой-нибудь оптимизированный N^2...
______________________
Nothing is impossible; impossible itself says: "I m possible"...
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
Гена - пожалуйста, разверни (обоснуй) свою тезу об оптимизированном N^2 при времени на тест 5 секунд. А то получается, что Миша правильно решил задачу, а думает что не решил. И так про все 10 задач, на которыми ему поручили работать.

Миша - пиши свои мысли по-поводу ОСТАЛЬНЫХ задач поскорее!
 
Индекс форума ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,045