題目連結:
題目大意:
給定一正整數 N (1 ≦ N ≦ 2 × 10 ^ 9)。求貪食蛇第 N 秒時在的位置(行數、列數)。當 N = 0 時,不處理這列輸入並結束程式。
2 3
5 4
1 5
1 1
32 25
3163 1756
我們可以觀察出當 N = 1 時,蛇蛇在第一列第一行; N = 2 ~ 4 時,蛇蛇在第二列或第二行;N = 5 ~ 9 時,蛇蛇在第三列或第三行……以此類推。
我們可以先將 N 取平方根(取整數)來得到蛇蛇可能在哪一列或哪一行(設為 X ),然後根據這個平方根之值的竒偶性去判斷蛇蛇移動的方向。竒數代表先往下,過了中點之後往左;偶數的路徑則反過來,先往右,過中點後再往上。
因此,我們可以根據中點的座標(X, X)、竒偶性以及 N 值有無超過中點的座標來求出蛇蛇第 N 秒的座標。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。