## 808 - Bee Breeding

Moderator: Board moderators

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

### 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

thanks

Ghost77 dimen
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
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
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.

Ghost77 dimen
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.
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
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
``````

Code: Select all

``````58
58
1
0
``````
good luck

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
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:
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)

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
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?

cjmu
New poster
Posts: 2
Joined: Mon Oct 07, 2002 6:16 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 ?

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

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

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

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:

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

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