017.書本小偷

[LarryLuTW]

前言:

很久沒出題目了 最近我會找一些不會太難但是需要想的題目 如果下次有約出來的話也可以順便講解這些題目

內容:

老師就讀國小的兒子正在學加法，他喜歡把書本翻開，從第1頁開始一頁一頁翻，然後把這些頁數加起來。例如有一本書有10頁，他就會做1+2+3+4+5+6+7+8+9+10。這結果是55。 有一次他又拿一本書在那邊做加法練習，可是在加的過程中他漏掉了某一頁沒加到。他跑來找我請我幫他算出到底是哪一頁沒加到，但是他只告訴我他加起來的結果，他甚至沒告訴我這本書有幾頁。 請你寫一個程式幫老師算出他漏掉的是哪一頁以及這本書總共有幾頁。

輸入說明:

輸入含有多筆測資。 每筆測資一行含有一個正整數 s（1 <= s <= 108） 代表我兒子告訴我他加起來的結果

輸出說明:

每組測資輸出一列 輸出我兒子漏掉的是哪一頁以及這本書總共有幾頁

範例輸入:

1
2
3
9000
499977
49999775

範例輸出:

2 2
1 2
3 3
45 134
523 1000
5225 10000

[w5151381guy]

我有一個疑問，假如我輸入頁數總和為1，可是說不定我這本書真的只有1頁而已，那1這個測資該怎麼辦啊

[LarryLuTW]

但題目說有漏掉一頁，所以如果總和是1的話代表漏掉第二頁，全部共有兩頁

[w5151381guy]

我剛剛有想到一個方法，我把總和從1開始減直到我剪出來的數字是負的就結束，而變成負的那個數字我把他取正數就剛好是我缺的那一頁，只是不知道有沒有更快的做法就是了，然後我有先上傳第一個版本了

[LarryLuTW]

好像不一定 如果 1～10 少 9 那減到 10 才會開始變成負的

[w5151381guy]

恩啊 用總和下去想就可以比較容易理解，假如全部有10頁，總和是55少了第9頁所以總和變46，所以我在減的時候一定是全部減完才會知道少了第9頁

[w5151381guy]

我後來想想，假如我用梯形公式下去想，(1+x)_x/2，先把一開始輸入的數字_2之後再開根號不就可以知道全部有幾頁，因為當我數字大的時候(1+x)*x可以看成x^2，之後再用完整的頁數去減掉一開始的數字就可以知道少了哪一頁，而且這樣還不用用到迴圈就不會有O(n)的問題了

[LarryLuTW]

嗯嗯我後來也是想到那個公式，感覺應該會快很多

[LarryLuTW]

我看完code了

num = sqrt(input * 2) + 0.5;
// 這邊應該會是 [sqrt(input * 2)] 或是 [sqrt(input * 2)+1]
// [x]  <---  高斯符號
// 直接加 0.5 取整數有可能會錯
// 可能要實際算算看

---

result = static_cast<int>(num);
// 然後要轉型的話可以直接
// result = int(num)

[w5151381guy]

我有稍微修改一下摟~~

[LarryLuTW]

看完了～ 應該沒什麼問題了