Re[3]: Время черепахи
От: olimp_20  
Дата: 07.07.15 19:05
Оценка:
Здравствуйте, Chorkov, Вы писали:

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

Понятно, например так:
  код
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

typedef double minutes;//тип double необходим для поиска задержки на старте и правильного вычисления результата!!!
bool F( minutes w );//возвращает количество пройденных цветов и значений true, если черепаха дошла до цветка N и съела его

int n;
int vmax, d;
vector<int> x;
vector<int> 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);
    t.assign(n,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];//длина пути в одну сторону

    minutes tlast = t[n-1];//время последнего цветка

        //алгоритм бинар. поиска: мин. задержка на старте wmin, чтобы успеть к проростанию цветка N
    minutes wmin = 0, wmax = tlast;
    minutes wait;
    while(wmax-wmin>0.1) {//условие для действительных чисел
        wait = (wmin+wmax)/2;    
        if(F(wait))
            wmax = wait;
        else
            wmin = wait;        
    }

    //Важно: в формуле использовать wmin - не wait, и не wmax - все-таки вычисляется мин. значение для задачи
    double dtime = wmin + n*d + s*2.0/vmax; //сума чисел типа double увеличивает дробную часть так, что позволяет правильно выполнить ceil(dtime)

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

    return 0;
}

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

Всем спасибо за помощь
Отредактировано 08.07.2015 14:49 olimp_20 . Предыдущая версия . Еще …
Отредактировано 08.07.2015 11:32 olimp_20 . Предыдущая версия .
Отредактировано 08.07.2015 6:15 olimp_20 . Предыдущая версия .
Отредактировано 08.07.2015 6:12 olimp_20 . Предыдущая версия .
Отредактировано 07.07.2015 21:16 olimp_20 . Предыдущая версия .
Отредактировано 07.07.2015 21:13 olimp_20 . Предыдущая версия .
Отредактировано 07.07.2015 21:10 olimp_20 . Предыдущая версия .
Отредактировано 07.07.2015 21:09 olimp_20 . Предыдущая версия .
Отредактировано 07.07.2015 19:08 olimp_20 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.