2016年2月25日 星期四

[HOJ 277][GCJ 2013 1B]Falling Diamonds (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/277_files/extensions/MathMenu.js
HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 277 - Falling Diamonds

Special Judge

Problem Statistics
Solved Member: 10  Submission: 66  User Tried: 11
Problem:
有很多方形的鑽石從天上掉了下來,現在貪心的Zeko想要去撿鑽石。

但是Zeko是懶惰的,所以在他確認一個位置有沒有鑽石之前,他不會去撿鑽石。

我們說一個位置有鑽石,代表有一個鑽石的「中心點」落在該座標上,我們保證所有鑽石的中心點座標都是格子點。

每個鑽石除了自己的座標(x , y)之外,它的頂點還會碰到(x-1 , y),(x+1 , y),(x , y-1),(x , y+1)四個座標。

現在有無數顆鑽石從(0 , ∞)垂直掉下來,∞是一個非常大的座標,這些鑽石會不斷落下直到它們打到地面(y = 0)或是卡在兩顆鑽石中間。

當鑽石打到地面,它就會埋入地面直到中心點在 y = 0 。
如果鑽石是邊碰邊和另一個鑽石相撞,它就會沿著鑽石邊形成的斜面滑下(即移動的路徑的斜率為 1 或者 -1)。
如果鑽石是頂點碰頂點和另一個鑽石相撞,它滑向左邊或滑向右邊的機率會是相等的。

如下圖,有可能為其中一種鑽石掉下來的情況


注意到,第二顆鑽石的中心座標為 (-2, 0),但是他也有機會掉在座標 (2, 0) 的位置,並影響到其他的鑽石掉在其他地方的機率。

現在告訴你總共有多少個鑽石從(0, ∞)落下,並且給你Zeko想要關心的座標(X, Y)。請輸出任何一個鑽石落在該座標的機率。
Input:
輸入的第一行是一個整數T(1 ≤ T ≤ 100),代表接下來有幾筆測試資料。
每筆測試資料佔一行,包含三個數字N(1 ≤ N ≤ 1000000), X (-10,000 ≤ X ≤ 10,000), Y (0 ≤ Y ≤ 10,000),分別代表總共有N個鑽石落下、Zeko關心的座標(X, Y)。
Output:
對於每一筆測試資料,請輸出一行,包含一個數字,代表Zeko關心的座標存在一顆鑽石的機率。你輸出的答案與我們的解答必須差在 10-6 以內。
Sample Input:
7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2
Sample Output:
1.0
0.0
1.0
0.75
0.25
0.5
0.0
Source:
Google Code Jam 2013 1B
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
010000ms262144kb
110000ms262144kb10
210000ms262144kb10
310000ms262144kb10
410000ms262144kb70

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原