| #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;
}
|