10161  Ant on a Chessboard
Moderator: Board moderators
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
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

 Learning poster
 Posts: 90
 Joined: Sat Feb 15, 2003 1:39 am
 Location: Paris, France
 Contact:

 Learning poster
 Posts: 90
 Joined: Sat Feb 15, 2003 1:39 am
 Location: Paris, France
 Contact:

 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);
}
}
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);
}
}
Hi
See this Input
My AC program give this output
But your program gives
Fix it.I hope you will get ACC.Good Luck.
See this Input
Code: Select all
1234567890
Code: Select all
35137 29394
Code: Select all
40880 35137
Love programmers,help programmers.
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!
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!

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