#34446: 公式解


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 08:34

依題目所述,我們可以把題目整理成
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;

最後再用 n(n+1) - 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)+1)*(x+1)>>1)+" "+x));

也沒有一定要縮成這樣,就是一個我自己小小的嗜好而已 ~嘻

註: 不能貼完整的程式碼,所以上面的程式碼是針對eof結束,本題是輸入0結束,所以還要再改一下。

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

 
#34447: Re: 公式解


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 08:57

更正
大字體等式的下一行
「少加的頁數」
是 n(n+1) / 2 - s

 
ZeroJudge Forum