Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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 мы нашли решение.