Codeforces #171 Div2 A "Point on Spiral"
問題
平面上の座標を
(0,0) (1,0) (1,1) (-1,1) (-1, -1) (2, -1) (2, 2)・・・
とぐるぐる回っていく。
(x, y)まで行った時に、何回曲がったかを返せ。
制約
1 <= |x|, |y| <= 100
考えた事
xとyが100以下って事は、愚直にシミュレートしても
計算量は40000回ぐらいだな。
(ってゆうか愚直にやらない方法は間違えそうで怖い)
ソースコード
int main(){ int px, py; cin >> px >> py; bool find = false; if( px == 0 && py == 0 ){ find = true; } int res = 0; int x = 0, y = 0; int dx[] = { 1, 0, -1, 0 }; int dy[] = { 0, 1, 0, -1 }; int d = 0; for( int i = 0; !find; i++ ){ int len = i / 2 + 1; for( int j = 0; j < len; j++ ){ x += dx[d]; y += dy[d]; if( x == px && y == py ){ find = true; } } if( !find ) res++; d++; d %= 4; } cout << res << endl; }