UVa 10161: Ant on a chessboard

Here is the basic snake arrangement:

26 27 28 29 30 31  6
25 24 23 22 21 32  5
10 11 12 13 20 33  4
9  8  7  14 19 34  3
2  3  6  15 18 35  2
1  4  5  16 17 36  1

1  2  3  4  5  6

If we expand the first 4 rows and columns, we can observe a pattern.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 2 2 2 3 3 3 3 3 4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5

Note the square root relationship here. We can identify which diagonal a number is in by taking the (ceil(sqrt(n))). Looking back at the grid, it is simple manipulation to determine which row and column a given value is in.

/*
 * Sai Cheemalapati
 * UVa 10161: Ant on a chessboard
 *
 */

#include<cmath>
#include<cstdio>

int n, x, y;

int main() {
	for(;;) {
		scanf("%d", &n);
		if(n == 0) break;

		int root = ceil(sqrt(n));
		int c = root * root - root + 1;
		x = y = root;

		if(root % 2 == 0) {
			if(n > c) y -= n - c;
			else x -= c - n;
		} else {
			if(n > c) x -= n - c;
			else y -= c - n;
		}

		printf("%d %d\n", x, y);
	}
}
8
20
25
0
2 3
5 4
1 5

2 thoughts on “UVa 10161: Ant on a chessboard

    • Wow, thanks! It was an observation I made after looking at the relationship between a value and the diagonal it’s a member of. It’s in the table above, but from the bottom left, 1 is in the first diagonal, 2 3 and 4 are in the 2nd, and so forth. I noticed there was a square relationship between which diagonal a value was a member of and the value itself, and I came up with a simple equation which would give me the value of the element on each diagonal.

      So, I knew that root^2 gave you the largest value on a diagonal, and that the value on the diagonal was (1 – root) less than root^2, so that’s where that formula came from.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s