#34454: 公式解 更正版


liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [210.71.71.201]
最後登入時間 :
2024-04-22 18:08:18
e635. 12908 - The book thief -- UVA | From: [118.166.137.176] | 發表日期 : 2023-03-21 14:24

上一篇發的連主要的算式都寫錯了(^ω^⁠),所以就重發了

依題目所述,我們可以把題目整理成
1 + 2 + … + n > 
輸入值s
求出最小的n           (第二個答案)
(1+2+…+n) - s        (
第一個答案)

我們可以列出不等式:
n(n+1)/2 > s      (
梯形公式)
整理一下
n(n+1) > 
2s
n^2 + n > 2s
n^2 + n + 
(1/2)^2 > 2s + (1/2)^2       (配方法)
(n+(1/2))^2 > 2s + (1/4)
(n+(1/2))^2 > (
8s+1)/4
n+(1/2) > 
sqrt(8s+1) / 2
n > (sqrt(8s+1) 
- 1) / 2

因為 n  N         //n是整數
如果這邊使用
n =
ceil( (sqrt(8s+1) - 1) / 2 )     //無條件進位
會在 sqrt(8s+1)  N 時,出現   n = (sqrt(8s+1) - 1) / 2 ,與原式不合     (會算出「少加第0頁」的答案)
所以我們使用無條件捨去再+1
得等式:
n = (
(int) sqrt(8s+1) - 1) / 2 + 1;

簡化後可得:
n = ((int) sqrt(8s+1) + 1) / 2;

最後再用 n(n+1)/2 - s 就能得到「少加的頁數」了

 

題外話,由於java有很穩定的指派順序,所以java能把這題的所有運算縮排成一排:
StreamTokenizer st = new StreamTokenizer(new java.io.BufferedReader(new java.io.InputStreamReader(System.in)));
for(int x; st.nextToken()!=-1; System.out.println(-(x=(int)st.nval)+((x=(int)Math.sqrt((x<<3)+1)+1>>1)*(x+1)>>1)+" "+x));

也沒有一定要縮成這樣,就是一個我自己小小的嗜好而已 ~
: 不能貼完整的程式碼,所以上面的程式碼是針對eof結束,本題是輸入0結束,所以還要再改一下。

希望這篇解題報告能幫助到你^_^

 
ZeroJudge Forum