切換
舊版
前往
大廳
主題

ZeroJudge - e128: 新北100-1貪食蛇 解題心得

Not In My Back Yard | 2019-03-24 18:01:17 | 巴幣 0 | 人氣 266

題目連結:


題目大意:
給定一正整數 N (1 ≦ N ≦ 2 × 10 ^ 9)。求貪食蛇第 N 秒時在的位置(行數、列數)。當 N = 0 時,不處理這列輸入並結束程式。



範例輸入:
8
20
25
1
1000
10000000
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 秒的座標。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作