題目連結:
題目意譯:
我們將玻璃杯疊成一個金字塔形,其中第一列有著 1 個玻璃杯、第二列有 2 個玻璃杯……以此類推直到第一百列。每個玻璃杯可以盛裝一杯的香檳。
接著,若干量的香檳倒入至最上面的第一個玻璃杯。當最上面的玻璃杯滿了後,任何多出來的液體將會平均地降至緊鄰於其左以及右的玻璃杯。當那些玻璃杯也滿了之後,任何多出來的香檳也會相繼向下降至緊鄰於其左、右之玻璃杯(譯注:這邊指的是位於下一列的玻璃杯,不是同一列的),以此類推(底部的玻璃杯如果有多出來的則將會落至地面上)。
例如說,倒入一杯的量之香檳後,頂端的杯子將會被裝滿。倒入一杯的量之香檳後,第二列的兩個玻璃杯將會是半滿的。倒入三杯的量之香檳後,那兩個杯子將被裝滿——代表現在有 3 個滿杯。倒入四杯的量之香檳後,第三列將會是中間的杯子半滿,而兩個靠外側的杯子為四分之一滿,如下圖所示。
現在倒入非負整數杯的量之香檳後,請回傳第 i 列的第 j 個杯子有多滿(i 和 j 的索引值都從 0 開始)。
限制:
0 ≦ poured ≦ 10 ^ 9
0 ≦ query_glass ≦ query_row < 100
範例測資:
範例 1:
輸入: poured = 1, query_row = 1, query_glass = 1
輸出: 0.00000
解釋: 我們倒入 1 杯的香檳到塔頂的玻璃杯(其索引值為 (0, 0))。不會有多餘的液體流到頂端的玻璃杯之下的杯子,因此維持為空的狀態。
範例 2:
輸入: poured = 2, query_row = 1, query_glass = 1
輸出: 0.50000
解釋: 我們倒入 2 杯的香檳到塔頂的玻璃杯(其索引值為 (0, 0))。有一杯量的多餘液體。索引值為 (1, 0) 的玻璃杯和索引值為 (1, 1) 的玻璃杯將平分該多餘液體,因故每個杯子得到了半杯量的香檳。
範例 3:
輸入: poured = 100000009, query_row = 33, query_glass = 17
輸出: 1.00000
解題思維:
模擬即可——即從第 0 列的玻璃杯開始,然後一列一列地往下延展直到第 i 列第 j 個杯子。
對於最頂端的杯子來說它會先承受 poured 量的香檳。但是由於它只能容納一杯的量,因此如果 poured > 1,則其將會往 (1, 0) 和 (1, 1) 這兩個杯子各自倒入 (poured - 1) ÷ 2 杯的香檳。
一般來說,第 i 列第 j 個杯子(即索引值 (i, j))如果承受了 C 杯來自先前的玻璃杯溢出的香檳。則如果 C > 1 的話,其將會往 (i + 1, j) 和 (i + 1, j + 1) 這兩個杯子各自注入 (C - 1) ÷ 2 杯的香檳。
而如果到了最後一列(索引值為 (99, j) 等等者)還有溢出的液體,則直接忽略即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。