coding everyday

每個杯子的容量為C升，從塔頂倒下L升水，當1號杯子滿了之后，會等量溢出到2號和3號杯子。當2號和3號滿了，2號溢出到4號和5號，3號溢出到5號和6號，注意5號接受來自兩個杯子的水。依次類推。給定C和L，請問，第n杯里有多少水。

分析：（出題的人貌似是讓用動態規劃的方式來做，可是偶不懂動態規劃哦。。用我自己的思路來做。）

可以看到這些杯子里面就兩類，一類就是靠邊的杯子，還有一類就是中間的，靠邊的杯子只能從它上面的一個杯子接水，而中間的可以從上面的2個杯子接水，我覺得這可以用分治算法的思路來做這個題目，因為底下杯子水的多少取決于它上面的杯子，上面的杯子又取決于再上面的。

之前說過了，杯子就兩類，一類就是靠邊的，還有一類是中間的；對于靠邊的，它只能從它上面的一個杯子里面得到溢出的水的一半；中間的，可以得到它上邊左邊溢出的一半和右邊溢出的一半。這邊有個小問題，就是如果我們按照最終一個杯子里的水的數量來做的話，有問題，比如第1個杯子，它最終只有cL的水，對吧？但是我們應該當NL來考慮。所以這里我們考慮的杯子的水是所有流經它的數量，而非最終數量。

那現在的問題就是，找出來特定杯子的水從哪來就OK了。靠邊的是從上面來，并且同一行的2個靠邊的是一樣的，所以只需要考慮上一行靠邊的溢出的/2就OK了。中間的（如5），它從2和3來的，可以看出來2和3分別是它上一行的左邊一個杯子和上一行相同位子的杯子。可以擴展幾層驗證一下。所以最后的問題就是如果把n轉換成第x層的第y個位子，就這么簡單。

代碼如下：

 1 template<int N, int c>
 2 float get_unlimited_wine_amount(int x, int y) {
 3     if (x == 1 && y == 1) {
 4         return N;
 5     }
 6 
 7     float ret = 0;
 8     if (y == 1 || y == x) {
 9         ret = 1.0 * (get_unlimited_wine_amount<N, c>(x-1, 1) -c ) /2;
10         return ret > 0 ? ret : 0;
11     }
12 
13     float left = get_unlimited_wine_amount<N, c>(x-1, y-1) - c;
14     left = left > 0 ? left : 0;
15     float right = get_unlimited_wine_amount<N, c>(x-1, y) - c;
16     right = right > 0 ? right : 0;
17     ret = (left + right) / 2;
18     return ret > 0 ? ret : 0;
19 }
20 
21 map<int, float> val;
22 
23 template<int N, int c>
24 float get_wine_amount(int n) {
25     float ret = 0, x, y;
26 
27     for (x = 1; ;x++) {
28         if (((x + 1) * x)/2 >= n)
29             break;
30     }
31 
32     y = n - ((x - 1) * x)/2;
33 
34     ret = get_unlimited_wine_amount<N, c>(x, y);
35     val.insert(make_pair(n, ret));
36 
37     return ret > c ? c : ret;
38 }

出題者的參考答案