UVa 10161

From Algorithmist
Jump to navigation Jump to search

UVA 10161 - Ant on a Chessboard[edit]

[ Problem Description -- http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1102 ]

Summary[edit]

We need to find the (x,y) position of the ant at time N. The bounds for N are too large to simply simulate the ant's walk, so a more formulaic approach is needed.

Explanation[edit]

First, we note that the ant is on either the x-axis or y-axis at any time that N is a perfect square (1,4,9,...). To solve for the ant's position, we first want to find the last time the ant has been on one of the axes and then compute where the ant is on the next partial square. To do this, we take the square root of N and round down to the nearest integer. Call this number K.

We now have two cases: either K is odd or K is even. If K is odd, that means that we are on the y-axis and the ant will be heading right and down next. If K is even, we are on the x-axis we will be heading up and left next. Now the ant has completed walking along the edge of the KxK square and will start to walk along the edge of the (K+1)X(K+1) square.

First, we start by computing the time left, which is N - K*K.

We have to treat two cases separately:

1. K is even.

If K is even, then the ant will be walking up K+1 spots and then to the left K+1 spots to complete the next square. If the timeLeft is less than or equal to K+1, then the ant's total position will be (K+1, timeLeft). If the timeleft is greater than K+1, then the ant's total position will be (K+1 - timeLeft - sideLength, K+1) because the ant has to walk up the side and then start moving left.

2. K is odd.

If K is odd, then the ant will be walking right K+1 spots and then down K+1 spots to complete the next square. If the timeleft is less than or equal to K+1, then the ant's total position will be (timeLeft, K+1). If timeLeft is greater than K+1, then the ant's total position will be (K+1, K+1 - timeLeft - sideLength).

Just make sure to properly treat the case where N is a perfect square. If N is an even, the ant will be at (sqrt(N), 1) and if it is odd the ant will be at (1, sqrt(N)).

Solutions[edit]

Input[edit]

8
20
25
0

Output[edit]

2 3
5 4
1 5