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

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

Изменено 08.07.2015 11:32 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;
}

Для теста
3 1 
1
100 00:01

от старта до цветка время 33.(3)мин. 1 мин — на поедание цветка и 33.(3)мин — назад. Ответ 1h:08m
Для теста:
123 0
1
10485 10:34

от старта до цветка время 1h:25m (85,24...), поэтому на старте ждет дополнительно wait мин. 0 мин — на поедание цветка и 1h:25m — назад. Ответ 12h:00m
Проблема: как считать скорость: 33.(3) — 33 или 34, 85,24 — 85 или 86? Например, если в первом случаэ 33, а во втором 85 — первый тест не проходит, а второй — правильно, и — наоборот.
Здравствуйте, Chorkov, Вы писали:

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

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

typedef int minutes;
minutes F( minutes w, bool& isN );
int cnt(0);
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 time;
    
    minutes tlast = t[n-1];
    minutes wmin = 0, wmax = tlast;
    minutes wait;
    while(wmax!=wmin) {
        wait = (wmin+wmax)/2;
        bool isN;
        int cnt = F(wait,isN);        
        if(isN && wait*vmax + x[n-1] + cnt*d*vmax>=tlast*vmax)
            wmax = wait;
        else
            wmin = wait+1;        
    }

    double dtime = wmax + n*d + s*2.0/vmax; 

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

    return 0;
}

minutes F( minutes w, bool& isN )
{
    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;
        }
    } 
    return cnt;
}

  Для теста
195 2
151
4 00:05
7 00:08
11 00:09
13 00:10
15 00:13
16 00:17
17 00:21
19 00:25
21 00:27
24 00:31
28 00:33
32 00:34
34 00:35
38 00:38
42 00:41
44 00:45
48 00:50
49 00:55
52 01:00
56 01:02
59 01:03
61 01:06
62 01:07
65 01:08
68 01:13
69 01:17
70 01:20
71 01:22
75 01:24
79 01:28
82 01:32
83 01:36
87 01:37
88 01:39
92 01:41
96 01:45
98 01:46
101 01:50
103 01:53
106 01:54
108 01:57
112 01:59
114 02:02
118 02:05
121 02:07
125 02:11
129 02:15
131 02:17
133 02:21
135 02:25
136 02:26
139 02:29
142 02:32
146 02:36
148 02:40
149 02:43
150 02:44
154 02:48
155 02:51
156 02:55
159 02:56
160 03:01
161 03:05
162 03:06
164 03:09
167 03:14
169 03:18
170 03:23
172 03:24
173 03:26
176 03:31
180 03:33
184 03:38
188 03:40
191 03:43
194 03:47
195 03:51
196 03:55
199 03:57
201 03:59
204 04:03
208 04:06
209 04:11
213 04:12
217 04:15
218 04:20
219 04:24
221 04:27
225 04:32
227 04:34
228 04:36
229 04:41
231 04:44
235 04:45
238 04:48
242 04:52
244 04:55
248 04:56
251 05:01
252 05:05
255 05:07
259 05:12
260 05:16
263 05:17
267 05:20
268 05:22
270 05:25
271 05:27
275 05:29
276 05:30
279 05:32
283 05:37
284 05:40
286 05:45
288 05:47
292 05:48
296 05:53
297 05:55
300 05:56
301 06:00
302 06:04
305 06:07
309 06:09
310 06:13
311 06:14
315 06:15
319 06:16
323 06:17
325 06:19
328 06:22
331 06:25
333 06:27
337 06:29
338 06:32
339 06:33
342 06:37
344 06:41
345 06:45
347 06:49
351 06:50
354 06:53
358 06:54
361 06:58
364 07:03
365 07:08
368 07:09
370 07:12
372 07:17
375 07:21
377 07:22
547 19:03

ответ 19:08, а выходит 19:09

Приведенный выше код не проходит всего 4 теста на сайте