Здравствуйте, Кодт, Вы писали:
К>А можно как-нибудь разжиться тестами — хотя б и неполным набором? К>Чтобы не на их сервер грузить, а локально поиграться.
сайт
Раздел "XIV Всероссийская олимпиада школьников по информатике" Тесты жюри
Написал на питончике, не заботясь о производительности, и сверил с эталонами.
Первая проблема, на которую налетел.
Когда вычисляю количество цветов, съеденных в прямом направлении, — погрешности вычисления выстреливают.
Тест номер 5.
Черепаха бежит "туда" за время 09:27.556, при том, что последний цветок распускается в 09:32.
Максимальная задержка на старте, таким образом, — 00:04.444.
Но из-за погрешностей, получается, что черепаха на прямом пути ест 0 цветов (т.е. даже последний цветок не ест), что противоречит определению максимальной задержки.
Квик-фикс: добавим к максимальной задержке "ещё немножко запасу", 0.1 минуты — всё равно же мы там занимаемся подбором, ничего страшного в небольшом расширении диапазона не случится.
Здравствуйте, olimp_20, Вы писали:
_>И насколько Ваш код отличается от моего? Я просто уже "потерялся", что там еще можно придумать...
Естественно, что очень сильно отличается, потому что я ставлю над ним всякие опыты.
Самый простой пример
v = ... # скорость
d = ... # задержка на еду
xts = [(x0,t0), (x1,t1), ...] # список координат цветов (без вычитания времени)
n = len(xts)
xz, tz = xts[-1] if xts else 0.,0. # координаты последнего цветкаdef eaten(t0) :
# сколько цветов съедено за проход туда, при данной начальной задержке
k = 0
for xi,ti in xts:
t = t0 + xi/v + k*d # момент прибытия черепахи к данному цветкуif t >= ti:
k += 1
return k
def eaten_incrementally(t0) :
k = 0
t, x = t0, 0
for xi,ti in xts:
t, x = t+(xi-x)/v, xi # продвигаем черепаху во времени и пространствеif t >= ti:
k += 1
t += d
return k
Две функции подсчёта. Делают одно и то же. Ошибки набегают по-разному. Это очень сильно влияет на результат Причём инкрементная, с бОльшей погрешностью, — считает лучше...
Думаю, что вообще надо от деления отказаться, и трансформировать все формулы, так, чтобы остаться в целых числах.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, olimp_20, Вы писали:
К>Написал на питончике, не заботясь о производительности, и сверил с эталонами.
К>Первая проблема, на которую налетел. К>Когда вычисляю количество цветов, съеденных в прямом направлении, — погрешности вычисления выстреливают.
Избежать ошибок округления, проще всего перейдя к целым числам.
Единица измерения времени равная 1/v минут, нам это обеспечит.
Здравствуйте, Chorkov, Вы писали:
C>Избежать ошибок округления, проще всего перейдя к целым числам. C>Единица измерения времени равная 1/v минут, нам это обеспечит.
Это само собой. Просто это — одна из граблей, которая в задаче существует.
Здравствуйте, 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;
}
0. Процедура забега: черепаха ползёт вперёд, останавливаясь только на тех цветках, которые распустились; затем тупит на последнем цветке (вообще-то, это запрещённый режим); затем ползёт назад и ест все оставшиеся цветки.
Напишем функцию fulltime(s), вычисляющую время полного забега туда-сюда, при условии стартовой задержки s.
1. Напишем предикат ok(s) показывающий, что при забеге вперёд черепаха не тупит.
Очевидно, что для sz = xz/v-tz, где xz,tz — координаты последнего цветка, ok(sz) заведомо истинно.
Очевидно, что если ok(s) выполняется, то fulltime(s) = s + n*d + 2*xz/v = s + D, где D — константа, D = n*d+2*xz/v
— тупим только на старте (во время забегов не тупим, на последнем цветке тоже не тупим)
— тратим время на съедение всех цветков, неважно, в первой или второй фазе
— тратим время собственно на забег туда-обратно
Если же ok(s) ложно, то fulltime(s) = s + D + stop(s)
т.е. у нас появляется некоторое время ожидания на последнем цветке, зависящее от стартовой задержки.
График stop(s) круче графика CONST-s — он состоит из ряда ступенек: проходя через каждый распустившийся цветок, stop(s) скачком уменьшается (т.к. черепаха сидит на этом цветке — и поэтому будет меньше тупить в конце).
Поэтому абсолютный минимум fulltime(s) наблюдается в точке smin = min [s for s in range(0,sz+1) if ok(s)]
— на участке not ok(s) функция ступенчато уменьшается
— на участке ok(s) линейно растёт
2. Функция ok(s) имеет форму ровно одной ступеньки, и именно поэтому точку smin можно найти бисекцией.
В таком виде у меня все тесты прошли.
Моя предыдущая ошибка состояла в том, что я искал не min s | ok(s), а min s | num(s)==num(sz), где num(s) — количество цветков, съеденных по направлению туда.
Очевидно, что этот предикат — более сильное условие, т.е. если он выполняется, то ok(s) тоже выполняется. Поэтому с ним мы находим более позднюю точку.
Здравствуйте, Кодт, Вы писали:
К>Наша задача — как можно более рационально распорядиться временем до t[n-1].
На самом деле задача чуть тоньше. Может так оказаться, что выгодно приползти к последнему цветку раньше, чем t[n-1]+d, если мы при этом съедим больше цветов, чем если приползём к t[n-1]... То есть перебор таки есть, но из двух вариантов.
Дальше, по идее нам всё равно какие именно цветы есть по пути "туда", главное скока есть.
Так что можно "запустить кино обратно", ползти назад по времени от момента t[n-1] и от момента t[n-1]+d и смотреть какие из цветов мы успеваем скушать.
По идее это один проход по массиву...
В смысле два. Если оба два дают одно количество цветов, то ясно, что ответ тривиален. Если второй вариант даёт +1, то среди тех цветов, кого не успеваем скушать при походе к t[n-1] находим тот, кого меньше всего ждать. Эта дельта t и даст ответ.
Но можно всё сделать и за один, конечно же.
Просто "крутим кино назад", и считаем
1) Сколько цветов успеваем при этом съесть, если ползём к t[n-1]
2) При какой минимальной задержке можем съесть ещё один.
Ну и если (1) меньше d, то считаем по формуле с лишним заранее съеденным, а если нет, о без него.
В принципе, если эту дельту с самого начала инициализировать в d, то формулы совпадут и всё ещё упростится...
Ergo: думаю, что можно написать формулу для нескольких столбикой ёкселя, такую, что если в A будут позиции цветов, а в B времена их расцвета, то в Z1 будет время возвращения в домик.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Перекуём баги на фичи!
Причём инкрементная, с бОльшей погрешностью, — считает лучше...
