# 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”

1. Mahir Tajwar says:

bro the way u did this was pure class ❤ c=root*root-root+1 was this a guess or there is a concrete logic behind this??

• saicheems says:

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.