10161 - Ant on a Chessboard

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10161 - Ant on a Chessboard

Post by Bug! » Wed Nov 12, 2003 9:18 am

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:

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

Post by bery olivier » Wed Nov 12, 2003 1:52 pm

There is not tricky inputs.
Let me compile my code, and I will post some I/O.
Not AC yet Image AC at last Image

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

Post by bery olivier » Wed Nov 12, 2003 2:07 pm

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
Not AC yet Image AC at last Image

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

Post by Bug! » Thu Nov 13, 2003 9:47 am

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

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

10161WA.......pls help

Post by ayeshapakhi » Sun May 28, 2006 10:01 pm

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
Location: Bangladesh

Post by sohel_acm » Tue May 30, 2006 10:39 pm

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.
Love programmers,help programmers.

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

10161 - ant on a chessboard

Post by xintactox » Fri Sep 01, 2006 7:58 pm

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
Location: TORONTO, CANADA

Post by daveon » Sun Oct 01, 2006 5:14 pm

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

Post by isagooddaytodie » Tue Apr 17, 2007 9:54 am

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

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

Re: 10161 - Ant on a Chessboard

Post by fR0D » Mon Jul 28, 2008 2:11 pm

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

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

Re: 10161 - Ant on a Chessboard

Post by uDebug » Fri Feb 14, 2014 9:08 am

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!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 101 (10100-10199)”