谷歌代码堵塞:Cookie切割器



cookie切割器问题有一个闭式解决方案吗?供参考的是:谷歌页面

*更新以包含问题声明

问题

在这个问题中,您从0个cookie开始。点击一个巨大的cookie,您将以每秒2个cookie的速度获得cookie。只要你有至少C个饼干,你就可以买一个饼干农场。每次你买一个饼干农场,它会花费你C块饼干,每秒会给你额外的F块饼干。

一旦你有了X块没有花在农场上的饼干,你就赢了!如果你使用尽可能好的策略,计算出你需要多长时间才能获胜。

示例

假设C=500.0,F=4.0,X=2000.0。以下是最佳策略的效果:

您从0个cookie开始,但每秒生成2个cookie。250秒后,您将拥有C=500个cookie,并且可以购买每秒生产F=4个cookie的农场。购买农场后,您有0个饼干,您的饼干总产量为每秒6个饼干。下一个农场将花费500块饼干,你可以在大约83.3333333秒后购买。购买第二个农场后,您有0块饼干,您的饼干总产量为每秒10块。另一个农场将花费500块饼干,你可以在50秒后购买。购买第三个农场后,您有0块饼干,您的饼干总产量为每秒14块。另一个农场将花费500块饼干,但实际上不买它是有道理的:相反,你可以等到你有了X=2000块饼干,这大约需要142.8571429秒。

总时间:250+83.333333+50+142.8571429=526.1904762秒。

请注意,你会连续收到cookie:因此,在游戏开始0.1秒后,你会收到0.2个cookie,而在游戏开始π秒后,会收到2个πcookie。

否。它不会有任何封闭的形式。

算法是这样的,

等待收集C许多cookie。如果你有C很多饼干,如果

 (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)

CCD_ 5,其也将具有闭合形式。

但是,级数{1/N}的有限和不具有任何闭形式,所以这两者都不具有。

我想有一个封闭形式:

注意,你必须进行比较(因为最好是尽可能多地购买另一个农场,或者永远不要购买另一家农场)

(X-C)/(2+F(n-1)) with X/(2+Fn),其中n是农场的数量。

因此,你只需要找到这样的n来解决

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

n=(FX-2C)/CF

如果n为正,则表示您的解为Floor(n)。否则,n=0就是您的解决方案。

PS:上面的"2"可以用初始生产率代替。

相关内容

  • 没有找到相关文章

最新更新