## 10161 - Ant on a Chessboard

Moderator: Board moderators

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

### 10161 - Ant on a Chessboard

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

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:
There is not tricky inputs.
Let me compile my code, and I will post some I/O.
Not AC yet AC at last

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:
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 !
Not AC yet AC at last

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am
At last I got AC, for some stupid reason...
I don't know know if 0 will be the last input....

Regard,
Andre

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

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

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);
}
}

sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 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.
Love programmers,help programmers.

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

### 10161 - ant on a chessboard

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!

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
You can calculate the answer in O(1) time.

isagooddaytodie
New poster
Posts: 3
Joined: Tue Mar 13, 2007 11:04 am
Contact:

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

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

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

### Re: 10161 - Ant on a Chessboard

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
``````

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10161 - Ant on a Chessboard

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))``
Check input and AC output for over 7,500 problems on uDebug!