808  Bee Breeding
Moderator: Board moderators
808  Bee Breeding
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
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

 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
808  Bee Breeding
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*m1)
{
ax[k]=58+mt;
if(t<=1)
{
ay[k]=h2;
h=ay[k];
}
else if(t<=m)
{
ay[k]=h1;
h=ay[k];
}
else if(t<=2*m1)
{
ay[k]=h+1;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=3*m)
{
ax[k]=58m;
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*m1)
{
ax[k]=58+t4*m;
if(t<=4*m)
{
ay[k]=h+1;
h=ay[k];
}
else if(t<=5*m1)
{
ay[k]=h1;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=6*m)
{
ax[k]=58+m;
if(t<=5*m)
{
ay[k]=h1;
h=ay[k];
}
else if(t<=6*m)
{
ay[k]=h2;
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(ayay[v])<=abs(axax[v]))
{
printf("The distance between cells %d and %d is %d.\n",u,v,abs(axax[v]));
}
else
{
printf("The distance between cells %d and %d is %d.\n",u,v,(abs(ayay[v])abs(axax[v]))/2+abs(axax[v]));
}
scanf("%d%d",&u,&v);
}
}
[/cpp]
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*m1)
{
ax[k]=58+mt;
if(t<=1)
{
ay[k]=h2;
h=ay[k];
}
else if(t<=m)
{
ay[k]=h1;
h=ay[k];
}
else if(t<=2*m1)
{
ay[k]=h+1;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=3*m)
{
ax[k]=58m;
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*m1)
{
ax[k]=58+t4*m;
if(t<=4*m)
{
ay[k]=h+1;
h=ay[k];
}
else if(t<=5*m1)
{
ay[k]=h1;
h=ay[k];
}
k++,t++;
if(k>10000)
{break;}
}
else if(t<=6*m)
{
ax[k]=58+m;
if(t<=5*m)
{
ay[k]=h1;
h=ay[k];
}
else if(t<=6*m)
{
ay[k]=h2;
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(ayay[v])<=abs(axax[v]))
{
printf("The distance between cells %d and %d is %d.\n",u,v,abs(axax[v]));
}
else
{
printf("The distance between cells %d and %d is %d.\n",u,v,(abs(ayay[v])abs(axax[v]))/2+abs(axax[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.

 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
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.
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.
i guess no cell number > 10000, although 10000 will occur.
maybe you can try this:
answer is:
good luck
maybe you can try this:
Code: Select all
1 10000
10000 5
9999 10000
10000 10000
Code: Select all
58
58
1
0

 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
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 upperright, y growing bottomright, 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,y1), (x+1,y), (x,y+1), (x1,y+1), (x1,y), (x,y1).
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)
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,y1), (x+1,y), (x,y+1), (x1,y+1), (x1,y), (x,y1).
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)

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

 New poster
 Posts: 12
 Joined: Sun Jun 01, 2003 12:21 pm
 Location: Pune, India
Solved Bee Breeding yet ?
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.
I use this way...
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.
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.
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
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((p1p2).real());
int b = abs((p1p2).imag());
int c = abs((p1p2).real()+(p1p2).imag());
ret <?= a+b; ret <?= b+c; ret <?= c+a;
cout << ret << endl;
}
return 0;
}
Why not solved??
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(a1);
int n1 = acero(a, c1);
double ang1;
if(!c1) ang1 = 0;
else ang1 = (double)n1*60/c1;
int c2 = ciclo(b1);
int n2 = bcero(b, c2);
double ang2;
if(!c2) ang2 = 0;
else ang2 = (double)n2*60/c2;
dist = sqrt(c1*c1+c2*c22*c1*c2*
cos((ang1ang2)*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*i5;
}
return cero;
}
#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(a1);
int n1 = acero(a, c1);
double ang1;
if(!c1) ang1 = 0;
else ang1 = (double)n1*60/c1;
int c2 = ciclo(b1);
int n2 = bcero(b, c2);
double ang2;
if(!c2) ang2 = 0;
else ang2 = (double)n2*60/c2;
dist = sqrt(c1*c1+c2*c22*c1*c2*
cos((ang1ang2)*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*i5;
}
return cero;
}

 New poster
 Posts: 2
 Joined: Wed Feb 18, 2004 5:50 am
I've tried this many times, and i always get WA
here are my test cases:
and my output for the above input is:
thank you.
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.

 New poster
 Posts: 1
 Joined: Thu Nov 17, 2005 8:37 am
808 Bee Breeding
I need some help in doing this problem how should I approach this problem