Время черепахи
От: olimp_20  
Дата: 01.07.15 18:14
Оценка:
Условие задачи
  Мое решение
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n;
    double vmax, d;
    scanf("%lf%lf%d", &vmax, &d, &n);

    if(n==0)//частный случай - обрабатыватся отдельно
    {
        printf("00:00\n");
        return 0;
    }

    vector<double> x(n,0.0);//массив расстояний
    vector<double> t(n,0.0);//масив моментов времени
    int hh, mm;
        //чтение данных
    for(int i=0; i<n; ++i) {
        scanf("%lf %d:%d", &x[i], &hh, &mm);
        t[i]=hh*60.0+mm;//преобразование в минуты
    }

    unsigned long cnt(0);//число съеденных цветов при движении от начала до последнего цветка
    bool isN=false;
    for(int i=0; i<n; i++)    {//перебор цветов при движении от начала до последнего цветка 
        if((x[i]/vmax+cnt)>=t[i])//если цветок уже вырос при достижении его черепахой
        {
            if(i==n-1) isN=true;//метка для последнего цветка
            cnt+=d;
        }
    }

        //если последний цветок съеден? двойное расстояние+время еды : 
                                        время до последнего цветка+время пути назад + время сЪедания цветов на обратном пути;
    double time = isN? 2.0*x[n-1]/vmax+n*d : t[n-1]+x[n-1]/vmax+n*d-cnt;

    int itime = ceil(time);
    printf("%02d:%02d\n", itime/60, itime%60);

    return 0;
}

Проблема: из 15 тестов для 8 — "Неправильный ответ". Подскажите, пожалуйста, что неправильно в алгоритме?
Re: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 09:49
Оценка:
Здравствуйте, olimp_20, Вы писали:

_>Проблема: из 15 тестов для 8 — "Неправильный ответ". Подскажите, пожалуйста, что неправильно в алгоритме?


У твоей черепахи алгоритм
1) с максимальной скоростью проползти вперёд, съев столько, сколько получится
2) подождать у последнего цветка
3) с максимальной скоростью проползти назад, съев остальные

Кстати, (2) как-то неочевидно реализовано; нет ли ошибки в формуле? (Не хочу ломать голову, прости).

Так вот, может оказаться, что лучше было бы подождать у цветов на прямом пути, чтобы потом тратить время на съедение их на обратном.
Пример
vmax = 1; d = 5
цветок №  положение время
       0      1     00:02
       1      2     00:09
       2      3     00:15

Бегущая черепаха:
x=0 00:00
x=1 00:01 цветок ещё не зацвёл, бежит дальше
x=2 00:02 ---"---
x=3 00:03 стоит, тупит
x=3 00:15 ест цветок
x=3 00:20
x=2 00:21 ест цветок
x=2 00:26
x=1 00:27 ест цветок
x=1 00:32
x=0 00:33

Мудрая черепаха:
x=0 00:00
x=1 00:01 ждёт
x=1 00:02 ест
x=1 00:07
x=2 00:08 ждёт
x=2 00:09 ест
x=2 00:14
x=3 00:15 даже ждать не пришлось, ест
x=3 00:20
x=2 00:21
x=1 00:22
x=0 00:23
Перекуём баги на фичи!
Re[2]: Время черепахи
От: olimp_20  
Дата: 02.07.15 11:44
Оценка:
Здравствуйте, Кодт:

  Новый вариант алгоритма
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n;
    int vmax, d;
    scanf("%d%d%d", &vmax, &d, &n);

    if(n==0)//частный случай
    {
        printf("00:00\n");
        return 0;
    }

        //чтение данных
    vector<int> x(n,0.0);
    vector<int> t(n,0.0);
    int hh, mm;
    for(int i=0; i<n; ++i) {
        scanf("%d %d:%d", &x[i], &hh, &mm);
        t[i]=hh*60+mm;
    }


    int s = x[n-1];//вся дистанция
    for(int i=1; i<n; i++) x[i] -= x[i-1];//ч[i] - дистанция между цветком "і-1" и "і"

        //бинарный поиск 
    int mi(0), ma(t[n-1]);//мин и макс зажержка пеерд стартом черепахи
    int time;//результат
    int cnt(0);//количество съеденных цветов: от начала до последнего цветка

    while(ma!=mi){
        int wait = (ma+mi)/2;
        time = wait; 
        cnt=0;
        for(int i=0; i<n; ++i)
            if(time*vmax+x[i]>=t[i]*vmax){ //time+x[i]/vmax>=t[i] - успел ли вырасти цветок
                ++cnt;
                time += d;
            }
 
        if(time>=t[n-1]) ma = wait;//изменить диапазон бинарного поиска
        else mi = wait+1;
    }

    int iS = ceil(s*1.0/vmax);//время для преодоления расстояния назад
    time += (n-cnt)*d+iS;


    printf("%02d:%02d\n", time/60, time%60);

    return 0;
}

Проблема: чем неправильный такой алгоритм — проходит всего 2 теста и как ускорить его работу?
Отредактировано 02.07.2015 12:03 olimp_20 . Предыдущая версия .
Re[3]: Время черепахи
От: Somescout  
Дата: 02.07.15 12:51
Оценка:
Здравствуйте, olimp_20, Вы писали:

Несколько странный алгоритм с моей точки зрения. Я бы решал задачу так:
1) при d=0 всё тривиально: в начале пути ждём t[N]-(x[N]/Vmax), а затем по пути съедаем всё что подходит по времени, а на обратном всё остальное: T=max(t[N],x[N]/Vmax) + x[N]/Vmax.
2) при d>0.
*)Запас времени T1 = t[N]-(x[N]/Vmax).
*)Первый проход: последовательно перебираем цветы, подходящие (те, которые распустились к моменту подхода, без ожидания) едим до тех пор пока d*cnt < T1
*)Запас времени T2 = T1 — d*cnt

*)Второй проход: нужно съесть максимальное количество цветов с ожиданием, не превысив T2T1. Вообще это выглядит задачей на рекурсию с полным перебором.
*)Оставшиеся цветы съедаются на обратном проходе.

Условие что при d>0, N<=200 намекает на полный перебор.

UPD: искоючил первый шаг: можно представить конфигурацию когда это невыгодно.
ARI ARI ARI... Arrivederci!
Отредактировано 02.07.2015 15:37 Somescout . Предыдущая версия . Еще …
Отредактировано 02.07.2015 13:09 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 13:07 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 13:06 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 13:02 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 12:58 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 12:56 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 12:55 Somescout . Предыдущая версия .
Re[4]: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 13:24
Оценка:
Здравствуйте, Somescout, Вы писали:

S>Условие что при d>0, N<=200 намекает на полный перебор.


Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.

Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
Перекуём баги на фичи!
Re[5]: Время черепахи
От: Somescout  
Дата: 02.07.15 13:45
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Somescout, Вы писали:


S>>Условие что при d>0, N<=200 намекает на полный перебор.


К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...

Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.

К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.

Возможно.

К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.


---------

Насчёт поиска и сортировки... есть идея, но описывать полный алгоритм текстом мучение, поэтому образно:
1) Вычтем из всех моментов времени время подхода черепахи:
t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1
2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
ARI ARI ARI... Arrivederci!
Отредактировано 02.07.2015 14:46 Somescout . Предыдущая версия . Еще …
Отредактировано 02.07.2015 14:44 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 14:36 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 14:35 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 14:34 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 14:22 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 13:52 Somescout . Предыдущая версия .
Отредактировано 02.07.2015 13:51 Somescout . Предыдущая версия .
Re: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 14:47
Оценка:
Здравствуйте, olimp_20, Вы писали:

Спасибо за головоломку.

Вот я что подумал. Поскольку черепаха двигается строго в одну сторону (а затем обратно), то мы можем сократить время-расстояние, перенеся все цветы в точку старта.
ti := ti-v*xi
xi := 0
Тем самым, уберём лишние данные.
Разумеется, время на забег туда-обратно, T=v*xn*2 запомним отдельно.

Причём возможна ситуация, когда ti < 0 — это значит, что до i-го цветка черепаха при всём желании доползёт строго после того, как он зацвёл.

А вот дальше самое интересное.
Отсортируем набор пар (ti,i) по возрастанию.
И будем извлекать оттуда претендентов по достаточно хитрому условию... (Пока я думаю над точной формулировкой, попробуйте сами догадаться).
Перекуём баги на фичи!
Re[6]: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 14:55
Оценка:
Здравствуйте, Somescout, Вы писали:

S>1) Вычтем из всех моментов времени время подхода черепахи:

S>t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1

Опередил!

S>2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.


Э, не понял.
Ну и к тому же, сортировка по убыванию (T2-t'[i])/d = (T2/d)-t'[i]/d — это сортировка по возрастанию t'[i]

S>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.


Нет ли здесь претензии на всё тот же полный перебор?
Перекуём баги на фичи!
Re[7]: Время черепахи
От: Somescout  
Дата: 02.07.15 15:16
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Somescout, Вы писали:


S>>1) Вычтем из всех моментов времени время подхода черепахи:

S>>t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1

К>Опередил!


S>>2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.


К>Э, не понял.

Черепахе нужно минимум время d чтобы съесть цветок, T2 — это из предыдущего алгоритма время оставщееся после выбора очевидных вариантов, соответственно T2-(время ожидания цветения этого цветка)/(время поедания цветка) — сколько цветков черепаха сможет съесть максимум, если будет ожидать раскрытия этого цветка.

Fix: T2 = T1 = t[N]-x[N]/Vmax, т.к. всё же есть конфигурации когда выбор цветов с 0 временем ожидания менее выгоден.

К>Ну и к тому же, сортировка по убыванию (T2-t'[i])/d = (T2/d)-t'[i]/d — это сортировка по возрастанию t'[i]

В принципе да, значит сортировать достаточно отсортировать t' по возрастанию


S>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.


К>Нет ли здесь претензии на всё тот же полный перебор?

В худшем случае да, но ведь мы проходим по убыванию максимально возможного числа съеденых цветов, соответственно в процессе практический max(съеденых) должен стать равным теоретическому, вот тут мы и прервёмся
ARI ARI ARI... Arrivederci!
Отредактировано 02.07.2015 15:35 Somescout . Предыдущая версия .
Re[7]: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 15:16
Оценка:
S>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.

К>Нет ли здесь претензии на всё тот же полный перебор?


А вот динамическое программирование тут появляется...

Для каждого цветка (#i) на прямом пути найдём
— минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов
— соответственно, минимальное время ухода от него
— — если черепаха не ела этот цветок, Q[i,m] = T[i,m]
— — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d

Для нулевого цветка, понятное дело, T[0,0] = 0.
Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)

Для последнего цветка # z=n-1 потратим время на обратный ход:
R[m] = Q[z,m] + d * (z-m)

Наилучшее время — это min(R[m] | 0<=m<n)
Перекуём баги на фичи!
Отредактировано 02.07.2015 15:17 Кодт . Предыдущая версия .
Re[8]: Время черепахи
От: Somescout  
Дата: 02.07.15 15:27
Оценка:
Здравствуйте, Кодт, Вы писали:

S>>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.


К>А вот динамическое программирование тут появляется...


Вообще в полном алгоритме я предполагал обычную рекурсию: мы выбираем элементы, способные дать максимум цветов, затем повторяем поиск для подмножества (t'') из всех элементов справа от выбранного элемента (k), из времени которых вычли время этого элемента:
t''[i] = t'[i+k] — t[k], 0<i<=N-k

К>Для каждого цветка (#i) на прямом пути найдём

К>- минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов
К>- соответственно, минимальное время ухода от него
К>- — если черепаха не ела этот цветок, Q[i,m] = T[i,m]
К>- — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d

К>Для нулевого цветка, понятное дело, T[0,0] = 0.

К>Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)
Разве min(Q[j,m]) не будет при m=0?

К>Для последнего цветка # z=n-1 потратим время на обратный ход:

К>R[m] = Q[z,m] + d * (z-m)

R[m] = Q[z,m] + d * (z-m) + Q[z,0]
Если не ошибаюсь — надо учесть и время обратного хода, а не только поедание цветов.

К>Наилучшее время — это min(R[m] | 0<=m<n)
ARI ARI ARI... Arrivederci!
Отредактировано 02.07.2015 15:28 Somescout . Предыдущая версия .
Re[9]: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 15:56
Оценка:
Здравствуйте, Somescout, Вы писали:

К>>Для каждого цветка (#i) на прямом пути найдём

К>>- минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов
К>>- соответственно, минимальное время ухода от него
К>>- — если черепаха не ела этот цветок, Q[i,m] = T[i,m]
К>>- — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d

К>>Для нулевого цветка, понятное дело, T[0,0] = 0.

К>>Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)
S>Разве min(Q[j,m]) не будет при m=0?

Так мы же перебираем по j, а не по m. Для текущего i и каждого m найдём минимум по j.

Если думать вслух, как Винни-пух:
Допустим, я стою у пятого бочонка с мёдом.
Если бы я ничего не съел (m=0), я бы потратил 0 минут.
Если бы я съел один (m=1)... это мог быть нулевой, первый, ... четвёртый бочонок. И я бы выбрал тот, который открывается раньше всех.
Если бы я съел два (m=2)... Это значит, что я съел два, заканчивая нулевым (ой, такое невозможно), или два, заканчивая первым (Q[1,2]), или два, заканчивая вторым (Q[2,2]), или третьим (Q[3,2]), или четвёртым (Q[4,2]).
Если бы я съел три (m=3)... Я бы выбирал между Q[2,3], Q[3,3], Q[4,3]
...
Наконец, если бы я съел все четыре, то это было бы, без вариантов, Q[4,4].

Во всех этих случаях, я получу наилучшее время Q[5,0] (воздержусь от съедения на этот раз, отложу на потом), Q[5,1], ..., Q[5,5].


Кстати, да, я немного напутал в рекуррентной формуле.
T[i,m] = min(Q[j,m] | j<i) — на подходе в состоянии "съедено m" выбираем кратчайший вариант

Q[i,m] = min(Q_skip[i,m], Q_take[i,m]) — на выходе в состоянии "съедено m" выбираем — это мы воздержались или съели в этот раз
Q_skip[i,m] = T[i,m] — воздержались — это значит, с чем пришли, с тем ушли, и не потратили времени
Q_take[i,m] = max(T[i,m-1], t[i]) + d — поели — это значит, пришли чуть голодными (m-1), при необходимости дождались нужного момента, и потратили порцию времени.


К>>Для последнего цветка # z=n-1 потратим время на обратный ход:

К>>R[m] = Q[z,m] + d * (z-m)

S>R[m] = Q[z,m] + d * (z-m) + Q[z,0]

S>Если не ошибаюсь — надо учесть и время обратного хода, а не только поедание цветов.

Время на забег туда-обратно, разумеется. Мы же, когда вычитали t[i] := t[i]-x[i]*v, должны были заначить время на забег: x[z]*v*2.


Мой алгоритм, очевидно, квадратичный.
Можно ли его сделать логлинейным, — интересный вопрос.
Перекуём баги на фичи!
Re[2]: Время черепахи
От: olimp_20  
Дата: 02.07.15 20:06
Оценка:
Здравствуйте, Кодт, Вы писали:

К>А вот дальше самое интересное.

К>Отсортируем набор пар (ti,i) по возрастанию.
К>И будем извлекать оттуда претендентов по достаточно хитрому условию... (Пока я думаю над точной формулировкой, попробуйте сами догадаться).

Если разместить на числовой прямой все значения ti, то далее надо найти точку (возможно с действительной координатой), наибольшее расстояние от которой до всех точек будет минимальным?
Re[10]: Время черепахи
От: olimp_20  
Дата: 02.07.15 21:40
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Мой алгоритм, очевидно, квадратичный.

К>Можно ли его сделать логлинейным, — интересный вопрос.

В разборе к этой задаче на сайте указано, что возможно применение бинарного поиска по ответу: бинарный поиск такого значения ожидания старта, при котором черепаха прибывает точно ко времени проростания последнего цветка. В таком случае время могло б быть log(N). Однако мои попытки реализовать я уже показал ранее и они не увенчались успехом. Вот если б бинарный поиск можно было б как-то применить....
Re[3]: Время черепахи
От: Кодт Россия  
Дата: 02.07.15 21:54
Оценка:
Здравствуйте, olimp_20, Вы писали:

_>Если разместить на числовой прямой все значения ti, то далее надо найти точку (возможно с действительной координатой), наибольшее расстояние от которой до всех точек будет минимальным?


(min(t)+max(t))/2, казалось бы. Даже сортировать ничего не надо.

Ну хорошо, нашли её, дальше что?
Перекуём баги на фичи!
Re[11]: Время черепахи
От: Кодт Россия  
Дата: 03.07.15 00:01
Оценка:
Здравствуйте, olimp_20, Вы писали:

_>В разборе к этой задаче на сайте указано, что возможно применение бинарного поиска по ответу: бинарный поиск такого значения ожидания старта, при котором черепаха прибывает точно ко времени проростания последнего цветка. В таком случае время могло б быть log(N). Однако мои попытки реализовать я уже показал ранее и они не увенчались успехом. Вот если б бинарный поиск можно было б как-то применить....


Прочитал авторский разбор.
У него следующая идея:
1) если черепаха ... ползёт, ждёт у k-го цветка какое-то время wk, ест, ползёт дальше ... то это время wk можно перенести в самое начало старта.
2) если черепаха проползает мимо уже зацвётшего цветка, то ей, очевидно, выгоднее съесть его сейчас, чем на обратном пути

Таким образом, стартовая задержка однозначно определяет полное время, затраченное черепахой.
То есть, мы можем написать функцию T(w) — которая вычисляется за линейное время, забегом по массиву моментов цветения.

Автор полагает, что у этой функции на интервале w=[0 ; max(t)] должен быть один минимум.
При w=0 мы меньше всего тупим на старте, зато меньше всего едим на первом проходе.
При w=max(t) — едим вообще всё, зато тупим по-полной.

Если минимум действительно один, то найти его можно методом Ньютона, что, собственно, автор и предлагает.
Но беда в том, что функция пилообразная... Тут нужно покумекать.
Перекуём баги на фичи!
Re[4]: Время черепахи
От: olimp_20  
Дата: 03.07.15 08:22
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, olimp_20, Вы писали:


_>>Если разместить на числовой прямой все значения ti, то далее надо найти точку (возможно с действительной координатой), наибольшее расстояние от которой до всех точек будет минимальным?


К>(min(t)+max(t))/2, казалось бы. Даже сортировать ничего не надо.


К>Ну хорошо, нашли её, дальше что?

Мне кажется (если я правильно понимаю), что в таком случае задача будет ближе к задаче про АЗС
Автор: olimp200
Дата: 10.11.14
, которую ранее Вы успешно подсказали как решать: тоже динамическое программирование, но несколько иначе, чем Вы указывали ранее.
А дальше : сумма таких расстояний (по модулю) — время достижения всех цветов.
Отредактировано 03.07.2015 9:47 olimp_20 . Предыдущая версия .
Re[12]: Время черепахи
От: olimp_20  
Дата: 03.07.15 09:52
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Если минимум действительно один, то найти его можно методом Ньютона, что, собственно, автор и предлагает.

К>Но беда в том, что функция пилообразная... Тут нужно покумекать.

Про форму функции и не подумал: теперь ясно почему на тестах постоянно то чуть больше ответа, то чуть меньше...
Re[12]: Время черепахи
От: Кодт Россия  
Дата: 03.07.15 09:54
Оценка:
А, кажется, сообразил, в чём фокус.

Наша задача — как можно более рационально распорядиться временем до t[n-1].
Найти такую минимальную задержку на старте w, при которой черепаха достигает последнего цветка к моменту F(w) >= t[n-1].
Если F(w) < t[n-1], это значит, что она вынуждена ждать на финише. Почему бы это же самое не подождать на старте?

F(w) имеет косо-ступенчатый вид — примерно вот так
F
|         /
|        |
|________|________ t[n-1]
|        |
|        |
|        |__________ нам нужно сюда
|       /:
|      / :
|     |  :
|     | наткнулись ещё на 1 цветок, +1*d
|    /   :
|   / до следующего цветка - опять финиш отодвигается со стартом
|  |     :
|  |     :
|  |     :
|  | наткнулись на 2 цветка, сразу затормозили на них, +2*d
| / отодвигаем финиш синхронно со стартом... dF/dw = 1
|/       :
|        :
| даже при нулевой задержке мы можем съесть пару цветков...
|        :
|        :
0--------+------ w

F(w)>=t[n-1] (недолёт-перелёт)
|
|        +------
|        |
0--------+------ w


Простой, хотя и медленный (O(n*log(t[n-1]))) способ найти нижнюю границу — это реализовать функцию F(w) и бисекцией подобрать.
minutes F(minutes w) {
  for (int i=0; i<n; ++i) { // включая последний цветок
    if (t[i] < w)
      w += t[i];
  }
  return w;
}

minutes solve() {
  minutes tlast = t[n-1];
  minutes wmin = 0, wmax = tlast; // верхняя граница выставлена с избытком
  assert(F(wmax) >= tlast);
  while(wmax-wmin > epsilon) {
    minutes wmed = (wmin+wmax)/2;
    if (F(wmed) >= tlast)
      wmax = wmed;
    else
      wmin = wmed;
}


Очевидно, что при большом t[n-1] мы заставим черепаху мысленно побегать! Единственная радость, что в сутках только 1440 минут.
Перекуём баги на фичи!
Re[13]: Время черепахи
От: olimp_20  
Дата: 03.07.15 12:43
Оценка:
Здравствуйте, Кодт:

  Еще одна попытка
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

typedef double minutes;
minutes F(minutes w);

int cnt(0);
int n;
int vmax, d;

vector<double> x;
vector<double> t;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    
    scanf("%d%d%d", &vmax, &d, &n);

    if(n==0)
    {
        printf("00:00\n");
        return 0;
    }

    x.assign(n,0.0);
    t.assign(n,0.0);
    int hh, mm;
    for(int i=0; i<n; ++i) {
        scanf("%lf %d:%d", &x[i], &hh, &mm);
        t[i]=hh*60.0+mm;
    }



    int s = x[n-1];
    for(int i=1; i<n; i++) x[i] -= x[i-1];//x[i] - расстояния между цветами

    minutes time;
    
    minutes tlast = t[n-1];
    minutes wmin = 0.0, wmax = tlast;
    const minutes epsilon = 0.1;
    while(wmax-wmin > epsilon) {
        minutes wmed = (wmin+wmax)/2.0;
        time = F(wmed);
        if (time >= tlast)
            wmax = wmed;
        else
            wmin = wmed;
    }


    int iS = ceil(s*1.0/vmax);
    time += (n-cnt-1)*d+iS;

    int itime = ceil(time);
    int x2=itime/60;
    int y2=itime%60;
    printf("%02d:%02d\n", x2, y2);

    return 0;
}

minutes F(minutes w) {
    cnt=0;//количество съеденных цветов для попытки w
    for (int i=0; i<n; ++i) { 
        if (t[i] < w+x[i]/vmax){
            w += x[i]/vmax+d;// = время марш-броска до цветка + время поедания цветка
            cnt++;
        }
    }
    return w;
}

Всё так же "Неправильный ответ" за исключением 2ух тестов (предполагаю, что для єтих двух тестов n=0)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.