808 - Bee Breeding

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

Moderator: Board moderators

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

808 - Bee Breeding

Post by arc16 » Fri Aug 23, 2002 3:05 am

Is there any formula for this problem?
My solution is by simulating the cell numbering using array, then count the distance between 2 cells using phytagoras. It works well when i test it, but the judge give me WA :(
if someone have a better algorithm, or formula, please help me.

thanks

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

808 - Bee Breeding

Post by Ghost77 dimen » Sun Sep 22, 2002 5:58 am

My method to solve problem 808 ,Bee Breedig,are as follows.
I can't find a mistake or a bug from it ,but I only got WA when it had
been submitted. Please tell me your thought ,don't be afraid whether
it go right. Thanks a lot ,to read my poor English.


[cpp]
#include<stdio.h>
#include<math.h>
void main(void)
{
int ax[10001],ay[10001];
int k=2,m,t=1,h=0,u,v;
ax[1]=58,ay[1]=0;

for(m=1;m<59;m++)
{
do
{
if(t<=2*m-1)
{
ax[k]=58+m-t;
if(t<=1)
{
ay[k]=h-2;
h=ay[k];
}
else if(t<=m)
{
ay[k]=h-1;
h=ay[k];
}
else if(t<=2*m-1)
{
ay[k]=h+1;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=3*m)
{
ax[k]=58-m;
if(t<=2*m)
{
ay[k]=h+1;
h=ay[k];
}
else if(t<=3*m)
{
ay[k]=h+2;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=5*m-1)
{
ax[k]=58+t-4*m;
if(t<=4*m)
{
ay[k]=h+1;
h=ay[k];
}
else if(t<=5*m-1)
{
ay[k]=h-1;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=6*m)
{
ax[k]=58+m;
if(t<=5*m)
{
ay[k]=h-1;
h=ay[k];
}
else if(t<=6*m)
{
ay[k]=h-2;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
}while(t<=6*m);
t=1;
}
scanf("%d%d",&u,&v);
while(u!=0)
{
if(abs(ay-ay[v])<=abs(ax-ax[v]))
{
printf("The distance between cells %d and %d is %d.\n",u,v,abs(ax-ax[v]));
}
else
{
printf("The distance between cells %d and %d is %d.\n",u,v,(abs(ay-ay[v])-abs(ax-ax[v]))/2+abs(ax-ax[v]));
}
scanf("%d%d",&u,&v);
}
}

[/cpp]
Last edited by Ghost77 dimen on Sun Sep 29, 2002 4:46 am, edited 1 time in total.

psb
New poster
Posts: 1
Joined: Tue Sep 24, 2002 10:39 pm

Post by psb » Tue Sep 24, 2002 10:41 pm

I have a similar problem. My program seems to work for the cases I've tried (all generated by hand), but it is rejected by the online judge. Does anyone have a large test case that I could try??

Thanks.

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Thu Sep 26, 2002 7:31 pm

Today,I consider one possible reason caused it wrong.

But I don't know whether it is right or not.

In the context, it says that the cell number won't exceed 10000.

But my method is program for any range,the range of int.

So maybe it is a problem,for example,10000 to n.

In the shortest path of this case, if the path contain one cell exceeded

10000.

My program will wrong in this situation,but really will it occur?

And one more situation should be discussed.

If 4 to 4,itself,which answer should be choosed, 0 or 2.

Maybe I consider too much or too strange, but I only want to solve the

problem.

Anyone would like pay little attention to my viewpoint.
Last edited by Ghost77 dimen on Sun Sep 29, 2002 4:47 am, edited 1 time in total.

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Fri Sep 27, 2002 1:11 am

i guess no cell number > 10000, although 10000 will occur.
maybe you can try this:

Code: Select all

1 10000
10000 5
9999 10000
10000 10000
answer is:

Code: Select all

58
58
1
0
good luck :lol:

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Fri Sep 27, 2002 11:38 am

Thank you,arc 16.

I found something wrong by your sample case.

Let me rewrite my code,maybe I will got AC.

Thank you once more.

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Sun Oct 27, 2002 4:13 pm

You can't use phytagoras, since it is not classical plane. You can convert the number of cell to coordinates such as, for example, x growing upper-right, y growing bottom-right, i.e.

1: 0,0
2: -1,1
3: -1,0
4: 0,-1
5: 1,-1
6: 1,0
7: 0,1
8: -1,2
...
Every cell (x,y) has exactly 6 neighbours: (x+1,y-1), (x+1,y), (x,y+1), (x-1,y+1), (x-1,y), (x,y-1).
Now it's not that difficult to compute a distance between two cells. (consider when you can decrease absolute differences of coordinates by 1 and when by 2)

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sat Nov 09, 2002 8:07 pm

Hi, arc16.

Today, I rewrite the code more clear , and I got A.C..

But I found something interesting, the answer 10000 5 is 59(my answer).

But yours seem is not identical with mine , what's wrong ?

Can anyone explain the strange situaction? 8)

cjmu
New poster
Posts: 2
Joined: Mon Oct 07, 2002 6:16 pm

Post by cjmu » Sun Nov 24, 2002 5:21 pm

i can not find out the relationship between each point.

What's the rule between 8 and 9 ?
any two point
i can,t find coordinate of 9 from (-1,2)"coordinate of 8"


can you tell me?

technogeek
New poster
Posts: 12
Joined: Sun Jun 01, 2003 12:21 pm
Location: Pune, India

Solved Bee Breeding yet ?

Post by technogeek » Tue Jun 03, 2003 9:00 am

I came across an old post of yours.....if you still need help with Bee Breeding : take a hint from http://onkar.s5.com/codezone .
I wanted to change the world, but they didn't give me the source code.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

I use this way...

Post by Sanghack » Thu Aug 14, 2003 11:52 am

I assumed three axis with

x: down right (1 7 19 31 .. )
y: up (1 5 15 31 .. )
z: up right (1 6 17 34 ... )

After you can find the position x,y ( marian have said.. )

And find manhatan distance with coordinate xy, xz, or yz.

The shortest distance is shortest among them.

sugaku
New poster
Posts: 1
Joined: Fri Mar 05, 2004 7:15 pm
Contact:

Post by sugaku » Fri Mar 05, 2004 7:22 pm

I also get WA, but it works on all the ones I have tried by hand.
My answer for 10000 5 is also 59

Any other test cases you can give me? I explicitly check for values over 10000

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;

int dx[] = {-1,-1, 0, 1,1,0};
int dy[] = { 1, 0,-1,-1,0,1};
#define C complex<int>
int grid[1000][1000];
C preq[10001];

int main(void) {
	int a,b;
	preq[1]=C(500,500);
	C p(500,499);
	int dir=0;
	grid[500][500]=1;
	for(int i=2; i<=10000; i++) {
		grid[p.real()][p.imag()]=1;
		preq[i]=p;
		while(grid[p.real()+dx[dir]][p.imag()+dy[dir]]) dir=(dir+1)%6;
		p+=C(dx[dir],dy[dir]);
		dir=(dir+3)%6;
	}
	while((cin >> a >> b)&&(a+b)) {
		if(a>10000 || b>10000 || a<1 || b<1) abort();
		C p1 = preq[a];
		C p2 = preq[b];
		int ret=1000000;
		int a = abs((p1-p2).real());
		int b = abs((p1-p2).imag());
		int c = abs((p1-p2).real()+(p1-p2).imag());
		ret <?= a+b; ret <?= b+c; ret <?= c+a;
		cout << ret << endl;
	}
	return 0;
}

Alejandro
New poster
Posts: 1
Joined: Fri Apr 23, 2004 12:37 pm

Why not solved??

Post by Alejandro » Fri Apr 23, 2004 12:47 pm

This is my atempt for solving the problem. Could you tell me why (My answer for 10000 5 is also 59 )

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;


int ciclo(int a);
int cero(int a, int c);

int main()
{
int a = 0;
int b = 0;
double dist;
vector<int> v;

do {
cin >> a;
cin >> b;
v.push_back(a);
v.push_back(b);
} while (a && b);


vector<int>::iterator i = v.begin();

while(i != v.end() ) {
a = *i++;
b = *i++;
if(!a && !b) break;

int c1 = ciclo(a-1);
int n1 = a-cero(a, c1);
double ang1;
if(!c1) ang1 = 0;
else ang1 = (double)n1*60/c1;

int c2 = ciclo(b-1);
int n2 = b-cero(b, c2);
double ang2;
if(!c2) ang2 = 0;
else ang2 = (double)n2*60/c2;

dist = sqrt(c1*c1+c2*c2-2*c1*c2*
cos((ang1-ang2)*3.14159265359/180));
dist = floor(dist+.5);

if(a && b)
cout<< "The distance between cells ";
cout <<a<<" and "<<b<<" is "<<dist<<endl;
}

return 0;
}


int ciclo(int a)
{
if(!a) return 0;

for(int i=1; ; ++i) {
int n= 6*i;
if(a <= n) return i;
a -= n;
}
}


int cero(int a, int c)
{
if(!c) return 1;

int cero = 1;

for(int i=1; i<=c; ++i) {
cero = cero+6*i-5;
}
return cero;
}

SupeRaskao
New poster
Posts: 2
Joined: Wed Feb 18, 2004 5:50 am

Post by SupeRaskao » Fri Sep 24, 2004 6:58 pm

I've tried this many times, and i always get WA

here are my test cases:

Code: Select all

19 20
30 40
100 1
30 30
1 20
1 10
10 20
50 100
1 10000
1 1000
100 10000
5000 10000
8111 8222
5123 8000
1 1
2 2
3 3
3999 5699
0 0

and my output for the above input is:

Code: Select all

The distance between cells 19 and 20 is 1.
The distance between cells 30 and 40 is 7.
The distance between cells 100 and 1 is 6.
The distance between cells 30 and 30 is 0.
The distance between cells 1 and 20 is 3.
The distance between cells 1 and 10 is 2.
The distance between cells 10 and 20 is 3.
The distance between cells 50 and 100 is 7.
The distance between cells 1 and 10000 is 58.
The distance between cells 1 and 1000 is 18.
The distance between cells 100 and 10000 is 52.
The distance between cells 5000 and 10000 is 32.
The distance between cells 8111 and 8222 is 104.
The distance between cells 5123 and 8000 is 84.
The distance between cells 1 and 1 is 0.
The distance between cells 2 and 2 is 0.
The distance between cells 3 and 3 is 0.
The distance between cells 3999 and 5699 is 20.
thank you.

pathfinder
New poster
Posts: 1
Joined: Thu Nov 17, 2005 8:37 am

808 Bee Breeding

Post by pathfinder » Thu Nov 17, 2005 8:42 am

I need some help in doing this problem how should I approach this problem

Post Reply

Return to “Volume 8 (800-899)”