Problem 11614 Etruscan Warriors Never Play Chess，Etruscan的戰士

Etruscan 部隊的戰士的行進是很有組織的，在第一排會站一個戰士，第二排會站兩個戰士，第三排會站三個戰士，以此類推。當最後一排不足一人或以上，則不為一排，也就是說，6 為 3、7 為 3、8 為 3、9 為 3、10 才為 4。

首先只需推導公式就可以很快的寫出來。S 為輸入的值。
首項為 0，公差為 1，末項為 0 + (n - 1) * 1，而

                    S < n * (n - 1) / 2
                2 * S < n * (n - 1)
                2 * S < n2 - n + 1/4 - 1/4
          2 * S + 1/4 < (n - 1/2)2
      (2 * S + 1/4)1/2 < (n - 1/2) 
(2 * S + 1/4)1/2 + 1/2 < n

則 n = (2 * S + 1/4)^1/2 + 1/2。但 n 求出後要減掉 1 才為解。參考程式碼如下：

printf("%lld\n", 
(long long int)floor(sqrt( 2.0 * (double)S + 0.25 ) + 0.5) - 1) ;

這題執行時間 0.000 秒。
By David.K

p11614題目連結
回ACM題庫目錄
回首頁