Timus, задача 1154

Нужно решить задачку про сражение магов (http://acm.timus.ru/problem.aspx?space=1&num=1154). Я уже описал класс моментов силы/слабости, но не представляю, как сделать простым способом интерполяцию силы магов по времени, чтобы высчитывать ее в заданный момент для обеих сторон. Попробовал распарсить временные строки и упаковать их в time_t:

Код (Text):

1. tmp->tm_hour = atoi(h1.c_str());
2. tmp->tm_min = atoi(m1.c_str());
3. tmp->tm_sec = atoi(s1.c_str());
4. strongtime = mktime(tmp);

но как теперь провести интерполяцию силы? Или я что-то неправильно понял в задании?

 

взял пример из статьи
24:00:00 = (24*60+0)*60=24*3600=86400 (количество секунд в дне)
18:00:00 = (18*60+0)*60=18*3600=64800 (количество секунд от начала дня до минимума силы)
10:00:00 = (10*60+0)*60=10*3600=36000 (количество секунд от начала дня до пика силы)
64800-36000=28800 (дельта время ослабевания)
86400-28800=57600 (дельта время набора силы)
130-40=90 (дельта силы)
90/28800=0,003125 (скорость ослабевания в секунду) dxd
90/57600=0,0015625 (скорость набора силы в секунду) dxu
т.е. начиная с 00:00:00 сила равна 40+dxu*(time+86400-64800)
а начиная с 10:00:00 сила равняется 130-dxd*(time-36000)
а начиная с 18:00:00 сила равна 40+dxu*(time-64800)

составляем структуру
struc power
{
uint a;//сила соответствующая меньшему времени
uint b;//сила соответствующая большему времени
uint time_lo;//меньшее время
uint time_hi;//большее время
float d1;//скорость прироста силы
float d2;//скорость упадка сил
}

составляем функцию
const time_24=24*3600;
uint getpower(power p, uint time)
{
if (time<p.time_lo)
{
return p.a+p.d1*(time-p.time_hi+time_24);
} else if (time<p.time_hi)
{
return p.b+p.d2*(time-p.time_lo);
} else {
return p.a+p.d1*(time-p.time_hi);
}
}

заполняем структуры
power getstruc(uint time_min, uint time_max, uint min_power, uint max_power)
{
power p
if (time_max<time_min)
{
p.a=max_power;
p.b=min_power;
p.time_lo=time_max;
p.time_hi=time_min;
} else {
p.a=min_power;
p.b=max_power;
p.time_lo=time_min;
p.time_hi=time_max;
}
p.d1=abs(p.a-p.b)/(p.time_hi-p.time_lo);
p.d2=abs(p.a-p.b)/(time_24-p.time_hi+p.time_lo);
return p;
}

 

остальное надеюсь понятно. (цикл поиска максимальной силы или превосходства с перебором по секундам)

решение в лоб. если подумаете, то возможно сможете найти закономерности

 

Очевидно, что сутки разбиваются точками минимальной и максимальной силы на 9 или менее отрезков. Чуть менее очевидно, что на каждом из отрезков разница сил между светлой и тёмной сторонами меняется линейно и считается довольно просто. Остаётся только найти максимальную положительную разницу на каждом из отрезков. У меня даже есть странное чувство, что решение нужно выбирать из этих 8 точек+начала и конца суток.

 

CyberManiac
Можно сначало посчитать разницу между составляющими темных и светлых

Например:
Темные: AWWW
Светлые: WWFE

Разница: AW vs FE и уже методом CyberManiac решить задачу