Застревание кода Google: резак печенья

Question

Есть ли закрытое решение для проблемы с печеньем? Для справки: страница Google

*Обновлено, чтобы включить формулировку проблемы

проблема

В этой задаче вы начинаете с 0 куки. Вы получаете куки со скоростью 2 куки в секунду, нажимая на гигантские куки. Каждый раз, когда у вас есть хотя бы C куки, вы можете купить ферму куки. Каждый раз, когда вы покупаете ферму cookie, она стоит вам C cookie и дает вам дополнительно F cookie в секунду.

Если у вас есть X куки, которые вы не потратили на фермы, вы выигрываете! Выясните, сколько времени вам потребуется, чтобы выиграть, если вы используете наилучшую возможную стратегию.

пример

Предположим, что C=500,0, F=4,0 и X=2000,0. Вот как действует наилучшая из возможных стратегий:

Вы начинаете с 0 куки, но производите 2 куки в секунду. Через 250 секунд у вас будет C=500 куки и вы сможете купить ферму, которая производит F = 4 куки в секунду. После покупки фермы у вас есть 0 файлов cookie, и ваш общий объем файлов cookie составляет 6 файлов cookie в секунду. Следующая ферма будет стоить 500 печенек, которые вы сможете купить примерно через 83,3333333 секунды. После покупки вашей второй фермы у вас есть 0 файлов cookie, а общее количество файлов cookie составляет 10 файлов cookie в секунду. Еще одна ферма будет стоить 500 печенек, которые вы сможете купить через 50 секунд. После покупки вашей третьей фермы у вас есть 0 файлов cookie, а общее количество файлов cookie составляет 14 файлов cookie в секунду. Другая ферма будет стоить 500 куки, но на самом деле имеет смысл не покупать ее: вместо этого вы можете просто подождать, пока у вас не будет X=2000 куки, что занимает около 142,8571429 секунд.

Общее время: 250 + 83,3333333 + 50 + 142,8571429 = 526,1904762 секунды.

Обратите внимание, что вы постоянно получаете куки: так что через 0,1 секунды после запуска игры у вас будет 0,2 куки, а через π секунды после запуска игры у вас будет 2π куки.

Answer 1

Я думаю, что есть закрытая форма:

Обратите внимание, что вы должны сравнить (так как оптимально либо купить другую ферму так долго, сколько вы можете, либо никогда не покупать другую)

(X-C)/(2+F(n-1)) with X/(2+Fn)где n - количество ферм.

Поэтому вам нужно просто найти n такой что решает

(X-C)/(2+F(n-1)) = X/(2+Fn),

п =(FX-2C)/CF

Если n положительно, это означает, что ваше решение - Floor (n). В противном случае n=0 - ваше решение.

PS: "2" выше может быть заменено начальной производительностью.

Answer 2

Нет. У него не будет закрытой формы.

Алгоритм идет так,

Подождите, чтобы собрать много печенья. Если у вас много печений, купите новую ферму, если

 (X-C)/R >= X/(R+F) --- (i)

иначе НЕ покупайте ферму и продолжайте собирать куки, пока у вас не будет X много куки.

eqn (i)
LHS is the time for the collecting (X-C) many cookies [collected C many cookies already which I did not spend on buying a farm] with current collecting rate.

RHS is the time for collecting X many cookies with the increased collecting rate.

Из уравнения, которое мы имеем, R <= F(X-C)/C

Таким образом, ответ будет,

C/2 + C/2+F + C/2+2F + C/2+3F + ... + C/2+NF + X/2+NF [2 + NF <= F(X-C)/C]
= C(1/2 + 1/2+F + 1/2+2F + ... + 1/2+NF) + X/2+NF = A

Предположим, у нас есть закрытая форма для расчета

тогда для F = 1, C = 1, X = K

у нас есть A = (1/2 + 1/3 + .. + 1/2+N) + X/2+N где 2+N <= (K-1)

=> (1/2 + 1/3 + .. + 1/2+N) = A - X/2+N который будет иметь закрытую форму тоже.

Но конечная сумма ряда {1/N} не имеет замкнутой формы. Так что ни это не имеет.