Сообщение Re[3]: Время черепахи от 02.07.2015 12:51
Изменено 02.07.2015 15:37 Somescout
Здравствуйте, olimp_20, Вы писали:
Несколько странный алгоритм с моей точки зрения. Я бы решал задачу так:
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
*)Второй проход: нужно съесть максимальное количество цветов с ожиданием, не превысив T2. Вообще это выглядит задачей на рекурсию с полным перебором.
*)Оставшиеся цветы съедаются на обратном проходе.
Условие что при d>0, N<=200 намекает на полный перебор.
Несколько странный алгоритм с моей точки зрения. Я бы решал задачу так:
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
*)Второй проход: нужно съесть максимальное количество цветов с ожиданием, не превысив T2. Вообще это выглядит задачей на рекурсию с полным перебором.
*)Оставшиеся цветы съедаются на обратном проходе.
Условие что при d>0, N<=200 намекает на полный перебор.
Re[3]: Время черепахи
Здравствуйте, olimp_20, Вы писали:
Несколько странный алгоритм с моей точки зрения. Я бы решал задачу так:
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: искоючил первый шаг: можно представить конфигурацию когда это невыгодно.
Несколько странный алгоритм с моей точки зрения. Я бы решал задачу так:
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).
*)Запас времени T2 = T1 — d*cnt
*)Второй проход: нужно съесть максимальное количество цветов с ожиданием, не превысив
*)Оставшиеся цветы съедаются на обратном проходе.
Условие что при d>0, N<=200 намекает на полный перебор.
UPD: искоючил первый шаг: можно представить конфигурацию когда это невыгодно.