Сообщение Re[13]: Время черепахи от 15.08.2015 21:13
Изменено 15.08.2015 23:59 Erop
Здравствуйте, Кодт, Вы писали:
К>Наша задача — как можно более рационально распорядиться временем до t[n-1].
На самом деле задача чуть тоньше. Может так казаться, что выгодно приползти к последнему цветку раньше, чем t[n-1]+d, если мы при этом съедим боьше цветов, чем если приползём к t[n-1]... То есть перебор таки есть, но из двух вариантов.
Дальше, по идее нам всё равно какие именно цветы есть по пути "туда", главное скока есть.
Так что можно "запустить кино обратно", ползти назад по времени от момента t[n-1] и от момента t[n-1]+d и смотреть какие из цветов мы успеваем скушать.
По идее это один проход по массиву...
В смысле два. Если оба два дают одно количество цветов, то ясно, что ответ тривиален. Если второй вариант даёт +1, то среди тех цветов, кого не успеваем скушать при походе к t[n-1] находим тот, кого меньше всего ждать. Эта дельта t и даст ответ.
К>Наша задача — как можно более рационально распорядиться временем до t[n-1].
На самом деле задача чуть тоньше. Может так казаться, что выгодно приползти к последнему цветку раньше, чем t[n-1]+d, если мы при этом съедим боьше цветов, чем если приползём к t[n-1]... То есть перебор таки есть, но из двух вариантов.
Дальше, по идее нам всё равно какие именно цветы есть по пути "туда", главное скока есть.
Так что можно "запустить кино обратно", ползти назад по времени от момента t[n-1] и от момента t[n-1]+d и смотреть какие из цветов мы успеваем скушать.
По идее это один проход по массиву...
В смысле два. Если оба два дают одно количество цветов, то ясно, что ответ тривиален. Если второй вариант даёт +1, то среди тех цветов, кого не успеваем скушать при походе к t[n-1] находим тот, кого меньше всего ждать. Эта дельта t и даст ответ.
Re[13]: Время черепахи
Здравствуйте, Кодт, Вы писали:
К>Наша задача — как можно более рационально распорядиться временем до 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 будет время возвращения в домик.
К>Наша задача — как можно более рационально распорядиться временем до 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 будет время возвращения в домик.