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) тоже выполняется. Поэтому с ним мы находим более позднюю точку.
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
double vmax, d;
scanf("%lf%lf%d", &vmax, &d, &n);
if(n==0)//частный случай - обрабатыватся отдельно
{
printf("00:00\n");
return 0;
}
vector<double> x(n,0.0);//массив расстояний
vector<double> t(n,0.0);//масив моментов времениint hh, mm;
//чтение данныхfor(int i=0; i<n; ++i) {
scanf("%lf %d:%d", &x[i], &hh, &mm);
t[i]=hh*60.0+mm;//преобразование в минуты
}
unsigned long cnt(0);//число съеденных цветов при движении от начала до последнего цветкаbool isN=false;
for(int i=0; i<n; i++) {//перебор цветов при движении от начала до последнего цветка if((x[i]/vmax+cnt)>=t[i])//если цветок уже вырос при достижении его черепахой
{
if(i==n-1) isN=true;//метка для последнего цветка
cnt+=d;
}
}
//если последний цветок съеден? двойное расстояние+время еды :
время до последнего цветка+время пути назад + время сЪедания цветов на обратном пути;
double time = isN? 2.0*x[n-1]/vmax+n*d : t[n-1]+x[n-1]/vmax+n*d-cnt;
int itime = ceil(time);
printf("%02d:%02d\n", itime/60, itime%60);
return 0;
}
Проблема: из 15 тестов для 8 — "Неправильный ответ". Подскажите, пожалуйста, что неправильно в алгоритме?
Здравствуйте, olimp_20, Вы писали:
_>Проблема: из 15 тестов для 8 — "Неправильный ответ". Подскажите, пожалуйста, что неправильно в алгоритме?
У твоей черепахи алгоритм
1) с максимальной скоростью проползти вперёд, съев столько, сколько получится
2) подождать у последнего цветка
3) с максимальной скоростью проползти назад, съев остальные
Кстати, (2) как-то неочевидно реализовано; нет ли ошибки в формуле? (Не хочу ломать голову, прости).
Так вот, может оказаться, что лучше было бы подождать у цветов на прямом пути, чтобы потом тратить время на съедение их на обратном.
Пример
vmax = 1; d = 5
цветок № положение время
0 1 00:02
1 2 00:09
2 3 00:15
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
int vmax, d;
scanf("%d%d%d", &vmax, &d, &n);
if(n==0)//частный случай
{
printf("00:00\n");
return 0;
}
//чтение данных
vector<int> x(n,0.0);
vector<int> t(n,0.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];//вся дистанцияfor(int i=1; i<n; i++) x[i] -= x[i-1];//ч[i] - дистанция между цветком "і-1" и "і"
//бинарный поиск int mi(0), ma(t[n-1]);//мин и макс зажержка пеерд стартом черепахиint time;//результатint cnt(0);//количество съеденных цветов: от начала до последнего цветкаwhile(ma!=mi){
int wait = (ma+mi)/2;
time = wait;
cnt=0;
for(int i=0; i<n; ++i)
if(time*vmax+x[i]>=t[i]*vmax){ //time+x[i]/vmax>=t[i] - успел ли вырасти цветок
++cnt;
time += d;
}
if(time>=t[n-1]) ma = wait;//изменить диапазон бинарного поискаelse mi = wait+1;
}
int iS = ceil(s*1.0/vmax);//время для преодоления расстояния назад
time += (n-cnt)*d+iS;
printf("%02d:%02d\n", time/60, time%60);
return 0;
}
Проблема: чем неправильный такой алгоритм — проходит всего 2 теста и как ускорить его работу?
Несколько странный алгоритм с моей точки зрения. Я бы решал задачу так:
1) при d=0 всё тривиально: в начале пути ждём t[N]-(x[N]/Vmax), а затем по пути съедаем всё что подходит по времени, а на обратном всё остальное: T=max(t[N],x[N]/Vmax) + x[N]/Vmax.
2) при d>0.
*)Запас времени T1 = t[N]-(x[N]/Vmax). *)Первый проход: последовательно перебираем цветы, подходящие (те, которые распустились к моменту подхода, без ожидания) едим до тех пор пока d*cnt < T1
*)Запас времени T2 = T1 — d*cnt
*)Второй проход: нужно съесть максимальное количество цветов с ожиданием, не превысив T2T1. Вообще это выглядит задачей на рекурсию с полным перебором.
*)Оставшиеся цветы съедаются на обратном проходе.
Условие что при d>0, N<=200 намекает на полный перебор.
UPD: искоючил первый шаг: можно представить конфигурацию когда это невыгодно.
Здравствуйте, Somescout, Вы писали:
S>Условие что при d>0, N<=200 намекает на полный перебор.
Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.
Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Somescout, Вы писали:
S>>Условие что при d>0, N<=200 намекает на полный перебор.
К>Если это NP-полная проблема, то 2^N как-то грустно обрабатывать...
Если брать худший случай (t[i] > x[i]/Vmax), то да, печаль полная. Но, возможно, имеет смысл сделать сначала наивный вариант, а если он не пройдёт то смотреть в сторону ограничения перебора и динамического программирования.
К>Скорее, задача логлинейная (поскольку находится в секции "поиск и сортировка"). Только надо подумать, как её спроецировать на сортировку.
Возможно.
К>Вообще, напрашивается какое-то динамическое программирование. Может, приоритетная очередь потребуется.
---------
Насчёт поиска и сортировки... есть идея, но описывать полный алгоритм текстом мучение, поэтому образно:
1) Вычтем из всех моментов времени время подхода черепахи:
t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1
2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
Вот я что подумал. Поскольку черепаха двигается строго в одну сторону (а затем обратно), то мы можем сократить время-расстояние, перенеся все цветы в точку старта.
ti := ti-v*xi
xi := 0
Тем самым, уберём лишние данные.
Разумеется, время на забег туда-обратно, T=v*xn*2 запомним отдельно.
Причём возможна ситуация, когда ti < 0 — это значит, что до i-го цветка черепаха при всём желании доползёт строго после того, как он зацвёл.
А вот дальше самое интересное.
Отсортируем набор пар (ti,i) по возрастанию.
И будем извлекать оттуда претендентов по достаточно хитрому условию... (Пока я думаю над точной формулировкой, попробуйте сами догадаться).
Здравствуйте, Somescout, Вы писали:
S>1) Вычтем из всех моментов времени время подхода черепахи: S>t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1
Опередил!
S>2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
Э, не понял.
Ну и к тому же, сортировка по убыванию (T2-t'[i])/d = (T2/d)-t'[i]/d — это сортировка по возрастанию t'[i]
S>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
Нет ли здесь претензии на всё тот же полный перебор?
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Somescout, Вы писали:
S>>1) Вычтем из всех моментов времени время подхода черепахи: S>>t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1
К>Опередил!
S>>2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.
К>Э, не понял.
Черепахе нужно минимум время d чтобы съесть цветок, T2 — это из предыдущего алгоритма время оставщееся после выбора очевидных вариантов, соответственно T2-(время ожидания цветения этого цветка)/(время поедания цветка) — сколько цветков черепаха сможет съесть максимум, если будет ожидать раскрытия этого цветка.
Fix: T2 = T1 = t[N]-x[N]/Vmax, т.к. всё же есть конфигурации когда выбор цветов с 0 временем ожидания менее выгоден.
К>Ну и к тому же, сортировка по убыванию (T2-t'[i])/d = (T2/d)-t'[i]/d — это сортировка по возрастанию t'[i]
В принципе да, значит сортировать достаточно отсортировать t' по возрастанию
S>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
К>Нет ли здесь претензии на всё тот же полный перебор?
В худшем случае да, но ведь мы проходим по убыванию максимально возможного числа съеденых цветов, соответственно в процессе практический max(съеденых) должен стать равным теоретическому, вот тут мы и прервёмся
S>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
К>Нет ли здесь претензии на всё тот же полный перебор?
А вот динамическое программирование тут появляется...
Для каждого цветка (#i) на прямом пути найдём
— минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов
— соответственно, минимальное время ухода от него
— — если черепаха не ела этот цветок, Q[i,m] = T[i,m]
— — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d
Для нулевого цветка, понятное дело, T[0,0] = 0.
Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)
Для последнего цветка # z=n-1 потратим время на обратный ход:
R[m] = Q[z,m] + d * (z-m)
Здравствуйте, Кодт, Вы писали:
S>>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.
К>А вот динамическое программирование тут появляется...
Вообще в полном алгоритме я предполагал обычную рекурсию: мы выбираем элементы, способные дать максимум цветов, затем повторяем поиск для подмножества (t'') из всех элементов справа от выбранного элемента (k), из времени которых вычли время этого элемента:
t''[i] = t'[i+k] — t[k], 0<i<=N-k
К>Для каждого цветка (#i) на прямом пути найдём К>- минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов К>- соответственно, минимальное время ухода от него К>- — если черепаха не ела этот цветок, Q[i,m] = T[i,m] К>- — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d
К>Для нулевого цветка, понятное дело, T[0,0] = 0. К>Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)
Разве min(Q[j,m]) не будет при m=0?
К>Для последнего цветка # z=n-1 потратим время на обратный ход: К>R[m] = Q[z,m] + d * (z-m)
R[m] = Q[z,m] + d * (z-m) + Q[z,0]
Если не ошибаюсь — надо учесть и время обратного хода, а не только поедание цветов.
К>Наилучшее время — это min(R[m] | 0<=m<n)
Здравствуйте, Somescout, Вы писали:
К>>Для каждого цветка (#i) на прямом пути найдём К>>- минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов К>>- соответственно, минимальное время ухода от него К>>- — если черепаха не ела этот цветок, Q[i,m] = T[i,m] К>>- — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d
К>>Для нулевого цветка, понятное дело, T[0,0] = 0. К>>Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i) S>Разве min(Q[j,m]) не будет при m=0?
Так мы же перебираем по j, а не по m. Для текущего i и каждого m найдём минимум по j.
Если думать вслух, как Винни-пух:
Допустим, я стою у пятого бочонка с мёдом.
Если бы я ничего не съел (m=0), я бы потратил 0 минут.
Если бы я съел один (m=1)... это мог быть нулевой, первый, ... четвёртый бочонок. И я бы выбрал тот, который открывается раньше всех.
Если бы я съел два (m=2)... Это значит, что я съел два, заканчивая нулевым (ой, такое невозможно), или два, заканчивая первым (Q[1,2]), или два, заканчивая вторым (Q[2,2]), или третьим (Q[3,2]), или четвёртым (Q[4,2]).
Если бы я съел три (m=3)... Я бы выбирал между Q[2,3], Q[3,3], Q[4,3]
...
Наконец, если бы я съел все четыре, то это было бы, без вариантов, Q[4,4].
Во всех этих случаях, я получу наилучшее время Q[5,0] (воздержусь от съедения на этот раз, отложу на потом), Q[5,1], ..., Q[5,5].
Кстати, да, я немного напутал в рекуррентной формуле.
T[i,m] = min(Q[j,m] | j<i) — на подходе в состоянии "съедено m" выбираем кратчайший вариант
Q[i,m] = min(Q_skip[i,m], Q_take[i,m]) — на выходе в состоянии "съедено m" выбираем — это мы воздержались или съели в этот раз
Q_skip[i,m] = T[i,m] — воздержались — это значит, с чем пришли, с тем ушли, и не потратили времени
Q_take[i,m] = max(T[i,m-1], t[i]) + d — поели — это значит, пришли чуть голодными (m-1), при необходимости дождались нужного момента, и потратили порцию времени.
К>>Для последнего цветка # z=n-1 потратим время на обратный ход: К>>R[m] = Q[z,m] + d * (z-m)
S>R[m] = Q[z,m] + d * (z-m) + Q[z,0] S>Если не ошибаюсь — надо учесть и время обратного хода, а не только поедание цветов.
Время на забег туда-обратно, разумеется. Мы же, когда вычитали t[i] := t[i]-x[i]*v, должны были заначить время на забег: x[z]*v*2.
Мой алгоритм, очевидно, квадратичный.
Можно ли его сделать логлинейным, — интересный вопрос.
Здравствуйте, Кодт, Вы писали:
К>А вот дальше самое интересное. К>Отсортируем набор пар (ti,i) по возрастанию. К>И будем извлекать оттуда претендентов по достаточно хитрому условию... (Пока я думаю над точной формулировкой, попробуйте сами догадаться).
Если разместить на числовой прямой все значения ti, то далее надо найти точку (возможно с действительной координатой), наибольшее расстояние от которой до всех точек будет минимальным?
Здравствуйте, Кодт, Вы писали:
К>Мой алгоритм, очевидно, квадратичный. К>Можно ли его сделать логлинейным, — интересный вопрос.
В разборе к этой задаче на сайте указано, что возможно применение бинарного поиска по ответу: бинарный поиск такого значения ожидания старта, при котором черепаха прибывает точно ко времени проростания последнего цветка. В таком случае время могло б быть log(N). Однако мои попытки реализовать я уже показал ранее и они не увенчались успехом. Вот если б бинарный поиск можно было б как-то применить....
Здравствуйте, olimp_20, Вы писали:
_>Если разместить на числовой прямой все значения ti, то далее надо найти точку (возможно с действительной координатой), наибольшее расстояние от которой до всех точек будет минимальным?
(min(t)+max(t))/2, казалось бы. Даже сортировать ничего не надо.
Здравствуйте, olimp_20, Вы писали:
_>В разборе к этой задаче на сайте указано, что возможно применение бинарного поиска по ответу: бинарный поиск такого значения ожидания старта, при котором черепаха прибывает точно ко времени проростания последнего цветка. В таком случае время могло б быть log(N). Однако мои попытки реализовать я уже показал ранее и они не увенчались успехом. Вот если б бинарный поиск можно было б как-то применить....
Прочитал авторский разбор.
У него следующая идея:
1) если черепаха ... ползёт, ждёт у k-го цветка какое-то время wk, ест, ползёт дальше ... то это время wk можно перенести в самое начало старта.
2) если черепаха проползает мимо уже зацвётшего цветка, то ей, очевидно, выгоднее съесть его сейчас, чем на обратном пути
Таким образом, стартовая задержка однозначно определяет полное время, затраченное черепахой.
То есть, мы можем написать функцию T(w) — которая вычисляется за линейное время, забегом по массиву моментов цветения.
Автор полагает, что у этой функции на интервале w=[0 ; max(t)] должен быть один минимум.
При w=0 мы меньше всего тупим на старте, зато меньше всего едим на первом проходе.
При w=max(t) — едим вообще всё, зато тупим по-полной.
Если минимум действительно один, то найти его можно методом Ньютона, что, собственно, автор и предлагает.
Но беда в том, что функция пилообразная... Тут нужно покумекать.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, olimp_20, Вы писали:
_>>Если разместить на числовой прямой все значения ti, то далее надо найти точку (возможно с действительной координатой), наибольшее расстояние от которой до всех точек будет минимальным?
К>(min(t)+max(t))/2, казалось бы. Даже сортировать ничего не надо.
К>Ну хорошо, нашли её, дальше что?
Мне кажется (если я правильно понимаю), что в таком случае задача будет ближе к задаче про АЗС
, которую ранее Вы успешно подсказали как решать: тоже динамическое программирование, но несколько иначе, чем Вы указывали ранее.
А дальше : сумма таких расстояний (по модулю) — время достижения всех цветов.
Здравствуйте, Кодт, Вы писали:
К>Если минимум действительно один, то найти его можно методом Ньютона, что, собственно, автор и предлагает. К>Но беда в том, что функция пилообразная... Тут нужно покумекать.
Про форму функции и не подумал: теперь ясно почему на тестах постоянно то чуть больше ответа, то чуть меньше...
Наша задача — как можно более рационально распорядиться временем до t[n-1].
Найти такую минимальную задержку на старте w, при которой черепаха достигает последнего цветка к моменту F(w) >= t[n-1].
Если F(w) < t[n-1], это значит, что она вынуждена ждать на финише. Почему бы это же самое не подождать на старте?
F(w) имеет косо-ступенчатый вид — примерно вот так
F
| /
| |
|________|________ t[n-1]
| |
| |
| |__________ нам нужно сюда
| /:
| / :
| | :
| | наткнулись ещё на 1 цветок, +1*d
| / :
| / до следующего цветка - опять финиш отодвигается со стартом
| | :
| | :
| | :
| | наткнулись на 2 цветка, сразу затормозили на них, +2*d
| / отодвигаем финиш синхронно со стартом... dF/dw = 1
|/ :
| :
| даже при нулевой задержке мы можем съесть пару цветков...
| :
| :
0--------+------ w
F(w)>=t[n-1] (недолёт-перелёт)
|
| +------
| |
0--------+------ w
Простой, хотя и медленный (O(n*log(t[n-1]))) способ найти нижнюю границу — это реализовать функцию F(w) и бисекцией подобрать.
minutes F(minutes w) {
for (int i=0; i<n; ++i) { // включая последний цветокif (t[i] < w)
w += t[i];
}
return w;
}
minutes solve() {
minutes tlast = t[n-1];
minutes wmin = 0, wmax = tlast; // верхняя граница выставлена с избытком
assert(F(wmax) >= tlast);
while(wmax-wmin > epsilon) {
minutes wmed = (wmin+wmax)/2;
if (F(wmed) >= tlast)
wmax = wmed;
else
wmin = wmed;
}
Очевидно, что при большом t[n-1] мы заставим черепаху мысленно побегать! Единственная радость, что в сутках только 1440 минут.
Здравствуйте, Кодт, Вы писали:
К>А можно как-нибудь разжиться тестами — хотя б и неполным набором? К>Чтобы не на их сервер грузить, а локально поиграться.
сайт
Раздел "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;
}
Здравствуйте, Кодт, Вы писали:
К>Наша задача — как можно более рационально распорядиться временем до 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 будет время возвращения в домик.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Перекуём баги на фичи!
Причём инкрементная, с бОльшей погрешностью, — считает лучше...
