Page 1 of 1

### 10161 - Ant on a Chessboard

Posted: Wed Nov 12, 2003 9:18 am
Hi all, can you give me sample input and output for this problem??
I've try some input and try to submit it, but i still got WA for several times. Is there any tricky input??

Thanx,
Regard
Andre Posted: Wed Nov 12, 2003 1:52 pm
There is not tricky inputs.
Let me compile my code, and I will post some I/O.

Posted: Wed Nov 12, 2003 2:07 pm
My program gives :
input :
1
8
20
25
30
18202530
0
Output :
1 1
2 3
5 4
1 5
5 6
4267 3774
BTW : this problem is really beatifull. It's a bit easy, but I like it ! Posted: Thu Nov 13, 2003 9:47 am
At last I got AC, for some stupid reason... I don't know know if 0 will be the last input....

Regard,
Andre

### 10161WA.......pls help

Posted: Sun May 28, 2006 10:01 pm
would anyone pls send me some test cases?
source code is here...i dont understand why it's getting WA.....

#include <stdio.h>
#include <math.h>

void main()
{
long time,row,col,temp,flo,cei,aux;
double num;

while(scanf("%ld",&time)==1 && time)
{
num=(double)sqrt(time);

flo=(long)floor(num);
cei=(long)ceil(num);

temp=(flo*flo+1+cei*cei)/2;

if(flo==cei)
{
if(time%2==0)
{
row=1;
col=flo;
}
else
{
row=flo;
col=1;
}
}
else
{
if(time==temp) row=col=cei;
else if(time<temp)
{
if(flo%2==1)
{
row=cei;
for(col=1,aux=flo*flo+1; aux<time; aux++,col++);
}
else
{
col=cei;
for(row=1,aux=flo*flo+1; aux<time; aux++,row++);
}
}
else
{
if(flo%2==1)
{
col=cei;
for(row=1,aux=cei*cei; aux>time; aux--,row++);
}
else
{
row=cei;
for(col=1,aux=cei*cei; aux>time; aux--,col++);
}
}
}
printf("%ld %ld\n",col,row);
}
}

Posted: Tue May 30, 2006 10:39 pm
Hi
See this Input

Code: Select all

``````1234567890
``````
My AC program give this output

Code: Select all

``````35137 29394
``````

Code: Select all

``````40880 35137
``````
Fix it.I hope you will get ACC.Good Luck.

### 10161 - ant on a chessboard

Posted: Fri Sep 01, 2006 7:58 pm
Hello everybody!

I trying to solve this problem using brute force, don't know if there is some formula to calculate it... Is there some formula?!
How could I optimize my algorithm?!

Thanks!

Posted: Sun Oct 01, 2006 5:14 pm
You can calculate the answer in O(1) time.

### are you sure it's O(1)?

Posted: Tue Apr 17, 2007 9:54 am
You telling me you can find nearest F(N) = N^2 with O(1)?

Hmmm, I'm not sure the exact worst time is but i think it's greater than O(1), since it's from zero to the next F(N).

please point out my mistake if i'm wrong about the run time or there's better solution. ZW

### Re: 10161 - Ant on a Chessboard

Posted: Mon Jul 28, 2008 2:11 pm
I am getting wrong answer while my code gives expected output for all test cases put here.Plz help.

Code: Select all

``````Got AC
Silly Mistake
``````

### Re: 10161 - Ant on a Chessboard

Posted: Fri Feb 14, 2014 9:08 am
I was put on the right track by looking at the following site (just the first portion - I didn't look at the code).

http://saicheems.wordpress.com/2013/11/ ... hessboard/

So, all credit goes to this person.

Hint #1
This is the first hint. If you don't want to know more, don't look at Hint #2.

The basic idea here is to arrange the numbers into a grid (like is done in the problem statement) and observe the following pattern

Code: Select all

`````` Number ---> Row or Column
1 ---> 1
2 ---> 2
3 ---> 2
4 ---> 2
5 ---> 3
6 ---> 3
7 ---> 3
8 ---> 3
9 ---> 3
10 ---> 4
11 ---> 4
12 ---> 4
13 ---> 4
14 ---> 4
15 ---> 4
16 ---> 4``````
What's the relationship between Number and Row or Col?

Hint #2
This is the second hint and final hint. Providing any more hints would be giving the answer away.

From the previous pattern, we observe that,

Code: Select all

``Number = ceil(sqrt(Row or Column))``