Page **1** of **1**

### 10161 - Ant on a Chessboard

Posted: **Wed Nov 12, 2003 9:18 am**

by **Bug!**

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

by **bery olivier**

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

by **bery olivier**

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

by **Bug!**

At last I got AC, for some stupid reason...

I don't know know if 0 will be the last input....

Thanx in advance Bery

Regard,

Andre

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

Posted: **Sun May 28, 2006 10:01 pm**

by **ayeshapakhi**

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

by **sohel_acm**

Hi

See this Input

My AC program give this output

But your program gives

Fix it.I hope you will get ACC.Good Luck.

### 10161 - ant on a chessboard

Posted: **Fri Sep 01, 2006 7:58 pm**

by **xintactox**

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

by **daveon**

You can calculate the answer in O(1) time.

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

Posted: **Tue Apr 17, 2007 9:54 am**

by **isagooddaytodie**

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

by **fR0D**

I am getting wrong answer while my code gives expected output for all test cases put here.Plz help.

### Re: 10161 - Ant on a Chessboard

Posted: **Fri Feb 14, 2014 9:08 am**

by **uDebug**

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