10161 - Ant on a Chessboard

[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

[bery olivier]

There is not tricky inputs.
Let me compile my code, and I will post some I/O.

[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 !

[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

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

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

[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!

[daveon]

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

[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

[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

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