作者cutecpu (可愛中央處理器)
站內Prob_Solve
標題Re: [ACM ] ACM 107 The Cat in the Hat
時間Wed Nov 11 08:18:03 2009
根據測資 282475264 60466176
程式算出來的 N=6 K=10
代入 H=(N+1)^K=282475249 跟測資的 282475264 有點誤差
懷疑測資的 282475264 是否合法
※ 引述《netsphere ()》之銘言：
: ※ [本文轉錄自 C_and_CPP 看板]
: 作者: netsphere () 看板: C_and_CPP
: 標題: [ACM ] ACM 107 The Cat in the Hat
: 時間: Wed Nov 11 00:46:04 2009
: ACM 107 The Cat in the Hat
: 題目: http://zerojudge.tw/ShowProblem?problemid=d087
: code: http://codepad.org/iSj5eQe0
: 一開始那隻貓的高度H
: 每次從帽子變出的貓的數目N
: 從帽子變出貓的次數K
: 題目輸入: 一開始那隻貓的高度H 以及最後動手工作的貓的數目W
: 這題我想用
: H = (N+1)^K
: W = (N)^K
: => H^(1/K) -1 = W^(1/k)
: 先用Loop求出使上面式子成立的 K
: 再代出 N
: 輸出 有多少隻貓是沒有在工作S，以及所有貓的高度的總和T
: 用等比公式:
: S=(1-N^K)/(1-N)
: T=H*[ (1-(n/(n+1))^(k+1)) / (1 - (n/(n+1)) ) ]
: 但再zerojudge始終卡在這筆測資 282475264 60466176
: 我程式算出的答案是12093235 1614529773
: 但答案是 12093235 1614529687
: 我一直搞不懂為什麼會差一點 難到是浮點數誤差?
: 煩請各位神大大給小弟一個開示.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.54.103
1F：推 LPH66:應是不合法測資無誤...282475264 非整數的整數次冪 11/11 12:41
2F：推 LPH66:但修正後測資 282475249 60466176 之答案 11/11 12:45
3F：→ LPH66:的確是 12093235 1614529687 (直接代原PO導的公式亦是如此) 11/11 12:46
4F：推 LPH66:給原PO的提示: 你 T 的式子是可以在數學上進一步化簡的 11/11 13:00
5F：→ LPH66:最後會化簡成一個很簡單的式子 完全用不到 pow 11/11 13:01
6F：推 LPH66:喔囧 剛剛發現因為 H 是錯的 所以你的答案才會跟著錯... 11/11 15:06
7F：→ bleed1979:我比較懷疑原po提供的測資來源是否正確 11/11 17:05
8F：→ bleed1979:因為我的AC程式碼跑不出結果但明明上傳是AC的 11/11 17:05
9F：推 netsphere:謝謝C大L大B大. 我只能說見鬼了同一份code昨天WA今天AC 11/11 19:15