808 - Bee Breeding

[arc16]

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

[Ghost77 dimen]

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]

[psb]

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]

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.

[arc16]

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

[Ghost77 dimen]

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]

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]

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]

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]

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 .

[Sanghack]

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]

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]

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]

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]

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