UVa11614 - Etruscan Warriors Never Play Chess (數論 Math theorm)

題目大意

有一組軍隊，他們的排隊方式向金字塔般，第一排一個、第二排兩個、第三排三個，以此類推，想請問你第 n 個人是第幾排？

測試資料最大不會超過 \(10^{18{\)

分析

不是難題，但也是有點腦筋急轉彎的感覺。

我們可以看出他像是金字塔一樣，因此透過梯形面積公式 \((上底 + 下底) * 高 / 2 \)的方式得出人數，上底必定是 1，因為第一排有一個人。

之後再透過配方法去解即可。

重點觀念

• 公式解(配方法)，以下進行推導，題目要求的 row 必為正數，因此負不合
  \(\frac{(1+row) * row}{2} \geq n \\ ⇒ row^2 + row -2n = 0 \\ ⇒ row = \frac{-1 \pm \sqrt{ 1^2 - (4 * 1 * (-2n))}{2}} \\ ⇒ row = \frac{-1+ sqrt{1+8n}}{2} \)

參考來源

• 齊笎詳解
• UVA Q11614 - Etruscan Warriors Never Play Chess
• 配方法

心得

這題不難，運用了國中知識解出。相信大家有一定概念都會的XD

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 10000
#define int long long
using namespace std;
int n , a ;

int compute(int a ){
    return ((-1 + sqrt(1+8*a)) / 2) ;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    cin >> n ;
    while(n--){
        cin >> a ;
        cout << compute(a) << '\n' ;
    }
    return 0;
}

手寫紀錄

記錄我在解這題的紀錄，透過紙筆來思考會讓我聰明很多