/*
數數字
假設今天有一種特殊的方陣，邊長為 7，且該方陣的每個元素是由外到內從 1 開始不斷增加，如以下範例：
①①①①①①①
①②②②②②①
①②③③③②①
①②③④③②①
①②③③③②①
①②②②②②①
①①①①①①①
給定一個數字 k（例如 11），則從方陣的左上角開始，以斜向且接續的方式數到第 11 個數字（數的方式如下圖），例如以上的範例為 1，則問題的答案即為 1。
①②⑥⑦⑮
③⑤⑧⑭⑯
④⑨⑬⑰㉒
⑩⑫⑱㉑㉓
⑪⑲⑳㉔㉕
Input
第一行代表測資的筆數 n。接下來有 n 行，每行兩個數字以空白間隔，第一個數字代表方陣的邊長，第二個數字 k 代表要求的第 k 個數。
Output
將數到的第 k 個數字輸出。
範例輸入：
3
7 11
3 5
4 9
範例輸出：
1
2
2
*/
/*
[解題概念]
設現有邊長 j 的正方形，欲求第 k 個的數字。
將每一斜排視為一組，這將成為鏡射成對的數字，
即第 k 數字會和第 j * j - k + 1 的數字相同。
##加速重點部分 #p.s. plusToN (t) = (1 + t) * t / 2
接著找尋第 k 個數字位於第幾斜排(n+1)。
以題目的第 11 個數字為例子，11 必定介於 10 和 15 之間，
即 plusToN(4) < 11 <= plusToN(5)，
也就是第 k 個數字必定位於到上一排的數字總數與到這一排的數字總數之間。
即 plusToN(n) < k <= plusToN(n + 1)。
由於公式 plusToN(t) = (1 + t) * t / 2 = (t + t^2) / 2 趨近於 (t^2)/2，
即 plusToN(t) ~= (t^2)/2。
以上面的例子來說，為了找到第 11 個數字最近的排數 4，
將 11 帶入公式 11 = (t^2)/2 求出 t 值，並向下取整數。
(11 不是一個排的最後，所以 t 值不會是整數)
因此，可以找到一個趨近值 m = floor(sqrt(k*2))，表示為 m = floor(sqrt(k*2)) ~= n，
用這個 m 值開始尋找，除了 n 極小的狀況，會產生 m > n 的現象以外，
其他都會是 n >= m 的狀況，大部分都是 n == m，
此時從 m - 1 開始找，就可以有效率地找到 n 值。
接著，取得第 k 個數字是該斜排的第幾個數字，這可以輕易地藉由 k - plusToN(n) 做到。
由於該斜排的數字，長得像是 "1 ... n/2 ... 1" ，本身也是鏡射。
若第 k 個數字的索引值(該斜排的第幾個數字)，
超過該排最大可能的數字(以題目的 7 11 來舉例就是 4)，那麼就將 k 做鏡射，
修正完的就是最終答案。
if (index > maxNum) index = i + 1 - index + 1;
這一行:
這邊 i + 1 是 n + 1，拿 7 11 來說就是 5
代表 11 12 13 14 15 那一行
如果最後 index 是 5
也就是 15 - 10
那修正的方式，就是 5 - 5 + 1
也就是 (4+1) - index + 1
因為那一行是
11 12 13 14 15
值分別是
1 2 3 2 1
*/
#include <iostream>
#include <cmath>
using namespace std;
int plusToN(int n) {
return (1 + n) * n / 2;
}
int getAns(int j, int k) {
int halfup = plusToN(j);
if (k > halfup) k = j * j - k + 1;
//
int m = (int) floor(sqrt(k*2));
for (int i = m - 1;;++i) {
int low = plusToN(i), high = plusToN(i + 1);
if (low < k && k <= high) {
int index = k - low;
int maxNum = (i + 1) / 2;
if (index > maxNum) index = i + 1 - index + 1;
return index;
}
}
}
int main() {
int times, j, k;
cin >> times;
while(times--) {
cin >> j >> k;
cout << getAns(j, k) << endl;
}
}
今天不清楚為什麼發神經
程式碼的部分，為了好讀我沒有做太多的加速
整篇的精華應該在解題策略上
這個演算法挺不錯的
創作內容
數數字
Minecraft (12)