【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c031
【解題想法】
- 觀察範例，可以知道第 x 個斜排有 x 個有理數，分別是
- x/1, (x-1)/2, …, 2/(x-1), 1/x
- 奇數排和偶數排，數的方向不同。
- Line-17: 計算第 n 個數字處於第幾斜排。
- Line-18: 計算第 n 個數字處於該斜排的第幾個位置。
#include <iostream>
#include <vector>
using namespace std;
vector <int> v;
int main() {
int i = 1, n = 1;
v.push_back(0);
v.push_back(n);
while (n < 1e7){
i++;
n += i;
v.push_back(n);
}
while (cin >> n){
int row = lower_bound(v.begin(), v.end(), n) - v.begin();
int idx = row + n - v[row];
cout << "TERM " << n << " IS ";
if (row % 2){
cout << (row+1-idx) << "/" << idx << "\n";
} else {
cout << idx << "/" << (row+1-idx) << "\n";
}
}
return 0;
}