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 :lol:

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 ! :D

Posted: Thu Nov 13, 2003 9:47 am
by Bug!
At last I got AC, for some stupid reason... :oops:
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

Code: Select all

1234567890
My AC program give this output

Code: Select all

35137 29394
But your program gives

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

:lol:

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.

Code: Select all

Got AC
Silly Mistake

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