[問題] UVa 11637
看板Prob_Solve (計算數學 Problem Solving)作者raincole (冷雨)時間15年前 (2009/10/28 10:41)推噓3(3推 0噓 7→)留言10則, 3人參與討論串1/1
http://uva.onlinejudge.org/contests/231-f349ee18/11637.pdf
我對題目的理解是：
有一個長度 N 的序列
將它隨機重新排列
如果其中兩個元素在原序列和新序列中的距離皆不大於 K
則將此兩元素視為「浪費的」
要求出「浪費的」元素的總數的期望值
（原序列是頭尾相接的，但新序列不是）
以N = 312 K = 1的情形而言
我的算法如下：
先考慮中間的319個元素之一A，A在原序列中有2個元素距離不大於1，在新序列中也有2個
故A是「浪費的」的機率為 1 - 318/320 * 317/319
又考慮端點的2個元素之一B，B在原序列中有2個元素距離不大於1，在新序列中只有1個
故B是「浪費的」的機率為 1 - 319/320 * 318/319
所以總期望值：
(1 - 318/320 * 317/319) * 319 + (1 - 319/320 * 318/319) * 2 = 3.99375
應輸出 3.9938
但是UVa toolkit上輸入312 1的答案是3.9937
我想不通這個算法哪裡不對...
請版上高手指教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 113.61.199.94
→
10/28 10:43, , 1F
10/28 10:43, 1F
推
10/28 12:02, , 2F
10/28 12:02, 2F
→
10/28 12:55, , 3F
10/28 12:55, 3F
→
10/28 12:56, , 4F
10/28 12:56, 4F
推
10/28 22:43, , 5F
10/28 22:43, 5F
推
10/28 23:25, , 6F
10/28 23:25, 6F
→
10/28 23:56, , 7F
10/28 23:56, 7F
→
10/28 23:57, , 8F
10/28 23:57, 8F
→
10/28 23:57, , 9F
10/28 23:57, 9F
→
10/28 23:58, , 10F
10/28 23:58, 10F
※ 編輯: raincole 來自: 113.61.199.94 (10/29 00:05)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
