切換
舊版
前往
大廳
主題

ZeroJudge - e658: 11614 - Etruscan Warriors Never Play Chess　解題心得

Not In My Back Yard | 2020-02-14 00:14:41 | 巴幣 2 | 人氣 190
題目連結：
題目大意：
給定一正整數 T ，代表有 T 筆測試資料，每筆佔一列。每列給定一正整數 n （0 ≦ n ≦ 10 ^ 18），代表有 n 位士兵。

現在這 n 位士兵要排若干行。第一行排一人、第二行排兩人、第三行排三人……以此類推。請問總共有幾行？如果剩下的士兵人數不夠完整組成下一行，則該行不計。

範例輸入：
6
3
6
7
8
9
10
範例輸出：
2
3
3
3
3
4
解題思維：
可以看到本題是要求一個最大的 k 滿足 1 ＋ 2 ＋ …… ＋ k ＝ k × （k ＋ 1） ÷ 2 ≦ n 。

上式移項可得
k ^ 2 ＋ k - 2n ≦ 0
當上式等號成立時，可得 k 之值為
(√(8n ＋ 1) － 1) ÷ 2

因此所求 ＝ floor(k) 。因為上面的解不一定是整數，要找到小於該數的最大整數。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#數學
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

妖魔鬼怪降伏於我

看更多

相關創作

更多創作

追蹤 創作集
其他創作
作品資料夾