把總品質為1kg的水分裝在n個杯子裡，每杯水的品質均為(1/n)kg，初始溫度均為0℃。現需要把每一杯水都燒開。我們可以對任意一杯水進行加熱。把一杯水的溫度升高t℃所需的能量為(4200*t/n)J，其中，“J”是能量機關“焦耳”。如果一旦某杯水的溫度達到100℃，那麼這杯水的溫度就不能再繼續升高，此時我們認為這杯水已經被燒開。顯然地，如果直接把水一杯一杯地燒開，所需的總能量為(4200*100)J。
在燒水的過程中，我們随時可以在兩杯溫度不同的水之間進行熱傳遞操作。熱量隻能從溫度較高的那杯水傳遞到溫度較低的那杯水。由于兩杯水的品質相同，是以進行熱傳遞操作之後，原來溫度較高的那杯水所降低的溫度總是等于原來溫度較低的那杯水所升高的溫度。
一旦兩杯水的溫度相同，熱傳遞立刻停止。
為了把問題簡化，我們假設：
- 沒有進行加熱或熱傳遞操作時，水的溫度不會變化。
- 加熱時所花費的能量全部被水吸收，杯子不吸收能量。
- 熱傳遞總是隔着杯子進行，n杯水永遠不會互相混合。
- 熱傳遞符合能量守恒，而且沒有任何的熱量損耗。
在這個問題裡，隻要求把每杯水都至少燒開一遍就可以了，而不要求最終每杯水的溫度都是100℃。我們可以用如下操作把兩杯水燒開：先把一杯水加熱到100℃，花費能量(4200*100/2)J，然後兩杯水進行熱傳遞，直到它們的溫度都變成50℃為止，最後把原來沒有加熱到100℃的那杯水加熱到100℃，花費能量(4200*50/2)J，此時兩杯水都被燒開過了，目前溫度一杯100℃，一杯50℃，花費的總能量為(4200*75)J，比直接燒開所需的(4200*100)J少花費了25%的能量。
你的任務是設計一個最佳的操作方案使得n杯水都至少被燒開一遍所需的總能量最少。
Input
輸入檔案隻有一個數n。(1≤n≤50000)
Output
輸出n杯水都至少被燒開一遍所需的最少的總能量，機關為J，四舍五入到小數點後兩位。
Sample Input
2
Sample Output
315000.00
#include<cstdio>
int n;
double a[50005];
int main()
{
while (~scanf("%d",&n))
{
for (int i=1;i<=n;i++) a[i]=0;
double ans=0;
for (int i=1;i<=n;i++)
{
ans+=1-a[i];
a[i]=1;
for (int j=i+1;j<=n&&a[i]>1e-8;j++)
{
a[i]=a[j]=(a[j]+a[i])/2;
}
}
printf("%.2lf\n",ans*420000/n);
}
return 0;
}