/*
數數字
假設今天有一種特殊的方陣,邊長為 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;
}
}
今天不清楚為什麼發神經
程式碼的部分,為了好讀我沒有做太多的加速
整篇的精華應該在解題策略上
這個演算法挺不錯的