[UVA] 10920 - Spiral Tap
Problem A - Spiral Tap
Time Limit: 1 second
The game of Spiral Tap is played on a square grid. Pieces are placed on a grid and the moves are realized according to the position of the pieces on the grid. However, the coordinate system in the game of Spiral Tap are a bit different that those find in traditional board games, such as chess.
The cell numbering scheme follow a spiral, starting from the center of the grid in an anti-clockwise fashion. The following figure illustrates the cell numbering scheme.
The goal is, given the spiral tap coordinates of a cell, find its cartesian coordinates (line 1 is at the bottom, and column 1 is the leftmost).
Input
The input is a series of lines. Each line is composed of two numbers: SZ and P. SZ is the size of the border of the grid and is an odd number no larger than 100000. P is the spiral position of a cell in this grid. The line such that SZ = P = 0 marks the end of the input (and is not part of the data set).
Output
For each line in the data set of the input, your program must echo a line "Line = X, column = Y.", where X and Y are the cartesian coordinates of the corresponding cell.
Sample Input
3 1 3 3 3 9 5 9 5 10 0 0
Sample Output
Line = 2, column = 2. Line = 3, column = 1. Line = 3, column = 3. Line = 4, column = 4. Line = 5, column = 4.
Problem setter: David Deharbe, Copyright 2005 UFRN. All rights reserved.
算一下在第幾層, 然後定為點在右上角, 再依序扣回來直到算到答案為止。#include <stdio.h>
#include <math.h>
int main() {
int n, m;
while(scanf("%d %d", &n, &m) == 2 && n) {
int x = n/2+1, y = n/2+1, z, w;
int sq = (int)sqrt(m);
if(sq%2 == 0) sq--;
for(z = sq; z*z < m; z += 2);
w = z/2;
x += w, y += w;
int v = z*z;
if(v - z < m) {
y -= v - m;
goto end;
} else
y -= z-1, v -= z, x--;
if(v - z + 1 < m) {
x -= v - m;
goto end;
} else
x -= z-2, v -= z-1, y++;
if(v - z + 1 < m) {
y += v - m;
goto end;
} else
y += z-2, v -= z-1, x++;
if(v - z + 1 < m) {
x += v - m;
goto end;
} else
x += z-2, v -= z-1;
end:
printf("Line = %d, column = %d.\n", y, x);
}
return 0;
}