Информация об изменениях

Сообщение Re[3]: Время черепахи от 07.07.2015 19:05

Изменено 07.07.2015 21:16 olimp_20

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

C>Избежать ошибок округления, проще всего перейдя к целым числам.
Понятно, например так:
  код 
typedef int minutes;
minutes F(minutes w);

int n;
int vmax, d;
vector<int> x;
vector<int> t;
...
int s = x[n-1];

    minutes time;
    
    minutes tlast = t[n-1];
    minutes wmin = 0, wmax = tlast;
    minutes wait;
    while(wmax!=wmin) {
        wait = (wmin+wmax)/2;
        int cnt = F(wait);        
        if(cnt==n || wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait;
        else
            wmin = wait+1;
        
    }

    time = wait*vmax + n*d*vmax + 2*s;  

    int itime = ceil(time*1.0/vmax);
    int x2=itime/60;
    int y2=itime%60;
    printf("%02d:%02d\n", x2, y2);
//-------------------------------------------------------------------------------------------------
minutes F(minutes w) {
    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++;
    } 
    return cnt;
}

при этом меняется прохождение тестов если:
while(wmax!=wmin) {
        wait = (wmin+wmax)/2;
        int cnt = F(wait);        
        if(cnt==n && wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait;
        else
            wmin = wait+1;
        
    }

или
while(wmax!=wmin) {
        wait = (wmin+wmax+1)/2;
        int cnt = F(wait);        
        if(cnt==n && wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait-1;
        else
            wmin = wait;
        
    }

практически на противоположный: хотя в обоих случаях больше 6 тестов не проходит, но за то всегда другие
Здравствуйте, Chorkov, Вы писали:

C>Избежать ошибок округления, проще всего перейдя к целым числам.
Понятно, например так:
  код 
typedef int minutes;
minutes F(minutes w);

int n;
int vmax, d;
vector<int> x;
vector<int> t;
...
int s = x[n-1];

    minutes time;
    
    minutes tlast = t[n-1];
    minutes wmin = 0, wmax = tlast;
    minutes wait;
    while(wmax!=wmin) {
        wait = (wmin+wmax)/2;
        int cnt = F(wait);        
        if(cnt==n || wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait;
        else
            wmin = wait+1;
        
    }

    time = wait*vmax + n*d*vmax + 2*s;  

    int itime = ceil(time*1.0/vmax);
    int x2=itime/60;
    int y2=itime%60;
    printf("%02d:%02d\n", x2, y2);
//-------------------------------------------------------------------------------------------------
minutes F(minutes w) {
    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++;
    } 
    return cnt;
}

при этом меняется прохождение тестов если:
while(wmax!=wmin) {
        wait = (wmin+wmax)/2;
        int cnt = F(wait);        
        if(cnt==n || wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait;
        else
            wmin = wait+1;
        
    }

или
while(wmax!=wmin) {
        wait = (wmin+wmax+1)/2;
        int cnt = F(wait);        
        if(cnt==n || wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait-1;
        else
            wmin = wait;
        
    }

практически на противоположный: хотя в обоих случаях больше 6 тестов не проходит, но за то всегда другие