e128 - 新北100-1貪食蛇
題目描述
題目描述了貪食蛇的行進方式，給定貪食蛇行進的秒數 N，要求輸出貪食蛇頭部在該時間點的座標 (x, y)。貪食蛇的行進規則是按照螺旋狀的路線前進，起始點為 (1, 1)。
解題思路
這題的核心在於理解貪食蛇螺旋行進的模式，並根據給定的秒數 N 計算出對應的座標。可以觀察到，貪食蛇的行進路徑可以被劃分為多個正方形層。例如，前 1 秒到 4 秒形成一個 2x2 的正方形，前 9 秒到 16 秒形成一個 4x4 的正方形，以此類推。
解題思路是首先計算出 N 所屬的正方形層數，即計算 sqrt(N) 的值。然後，根據 N 的奇偶性判斷貪食蛇頭部所在的邊，並計算出 x 和 y 座標。
具體步驟如下：
- 計算 N 的平方根 a = sqrt(N)。
- 如果 a 是奇數：
- 如果 N 是完全平方數 (N == a*a)，則輸出 (1, a)。
- 否則，計算出當前層的邊長，並根據 N 與當前層最大值的差值，計算出 x 和 y 座標。
- 如果 a 是偶數：
- 如果 N 是完全平方數 (N == a*a)，則輸出 (a, 1)。
- 否則，計算出當前層的邊長，並根據 N 與當前層最大值的差值，計算出 x 和 y 座標。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
long long int a,aa;
while(cin >> a){
if(a==0)break;
aa=a;
a=sqrt(a);
if(a&1){
if(aa==a*a)
cout << "1 " << a << "\n";
else{
int m=((a*a+1)+(a+1)*(a+1))/2;
++a;
if(aa<m)
cout << a-(m-aa) << " " << a << "\n";
else if(aa>m)
cout << a << " " << a-(aa-m) << "\n";
else
cout << a << " " << a << "\n";
}
}
else{
if(aa==a*a)
cout << a << " 1\n";
else{
int m=((a*a+1)+(a+1)*(a+1))/2;
++a;
if(aa<m)
cout << a << " " << a-(m-aa) << "\n";
else if(aa>m)
cout << a-(aa-m) << " " << a << "\n";
else
cout << a << " " << a << "\n";
}
}
}
}