216 - Getting in Line

[watershed]

My program outtputed the first one, but it shouldn't matter since the description states that:

No two computers are at identical locations and each computer will be listed once.

thanks....I understand
but I still got WA
who have more input data
sorry,my program is poor ^^"

[c] cut [/c]

[johnnydog33]

program p216;
type arr1=array[1..8] of integer;
arr2=array[1..8] of boolean;
var ans,dd:real;
x,y,f,f1:arr1;
dist:array[1..8,1..8] of real;
n,num,i,j:integer;
flag:arr2;
procedure try(i:integer);
var flags:arr2;
ff:arr1;
ddd:real;
k,j:integer;
begin
if (i=n+1) and (dd<ans) then begin
for k:=1 to 8 do f1[k]:=f[k];ans:=dd;
exit;
end;
for j:=1 to n do
if (flag[j]) and ((i=1) or (dist[f[i-1],j]+dd<ans)) then begin
ddd:=dd;
for k:=1 to 8 do ff[k]:=f[k];
for k:=1 to 8 do flags[k]:=flag[k];
if i>1 then dd:=dd+dist[f[i-1],j];
f:=j;
flag[j]:=false;
try(i+1);
for k:=1 to 8 do flag[k]:=flags[k];
dd:=ddd;
for k:=1 to 8 do f[k]:=ff[k];
end;
end;
begin
num:=0;
repeat
readln(n);
if n<>0 then begin
inc(num);
for i:=1 to n do readln(x,y);
for i:=1 to n do
for j:=1 to i do begin
dist[i,j]:=sqrt(sqr(abs(x-x[j]))+sqr(abs(y-y[j])));
dist[j,i]:=dist[i,j];
end;
fillchar(f,sizeof(f),0);
fillchar(flag,sizeof(flag),true);
ans:=1000;dd:=0;
try(1);
writeln('**********************************************************');
writeln('Network #',num);
for i:=1 to n-1 do
writeln('Cable requirement to connect (',x[f1],',',y[f1],') to (',
x[f1[i+1]],',',y[f1[i+1]],') is ',(dist[f1,f1[i+1]]+16):0:2,' feet.');
writeln('Number of feet of cable required is ',(ans+16*(n-1)):0:2);
end;
until n=0;
end.

[camus]

I havent try this question but I Think this is a minimum spanning tree problem, hope I am correct:P

[TISARKER]

I am getting wrong answer for a long time.
I checked all possible case as my ability.
Please give me some input and output for which my program give wrong output.

Code: Select all

Remove after Accepted.

[little joey]

For the input

Code: Select all

7
56 108
127 56
29 132
43 105
30 146
54 135
32 89
0

Your program gives:

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (127,56) to (56,108) is 104.01 feet.
Cable requirement to connect (56,108) to (54,135) is 43.07 feet.
Cable requirement to connect (54,135) to (30,146) is 42.40 feet.
Cable requirement to connect (30,146) to (29,132) is 30.04 feet.
Cable requirement to connect (29,132) to (43,105) is 46.41 feet.
Cable requirement to connect (43,105) to (32,89) is 35.42 feet.
Number of feet of cable required is 301.35.

My program gives:

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (127,56) to (32,89) is 116.57 feet.
Cable requirement to connect (32,89) to (43,105) is 35.42 feet.
Cable requirement to connect (43,105) to (56,108) is 29.34 feet.
Cable requirement to connect (56,108) to (54,135) is 43.07 feet.
Cable requirement to connect (54,135) to (29,132) is 41.18 feet.
Cable requirement to connect (29,132) to (30,146) is 30.04 feet.
Number of feet of cable required is 295.62.

[TISARKER]

Thanks Joey

[sohel_acm]

I am in a great trouble with 216.I am continuously getting WA for this problem,but i can't find where is the error.I tried several critical input.In all cases my program gave correct output.Now plz someone help me.Here is my code

#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 100

char c[M]={0};
long int as[M],ii,jj,a[M],ans[M];
//static int po=0;
float matrix[M][M],ss,hh,leng[M],min,sum_dist,final_dist[M];

struct point
{
float x,y;
}p[M];

void dist(int node)
{
for(ii=1;ii<=node;ii++)
{
for(jj=1;jj<=node;jj++)
{
matrix[ii][jj]=0.0;
matrix[ii][jj]=0.0;
}
}

for(ii=1;ii<node;ii++)
{
for(jj=ii+1;jj<=node;jj++)
{
ss=abs(p[ii].x-p[jj].x);
ss*=ss;
hh=abs(p[ii].y-p[jj].y);
hh*=hh;
matrix[ii][jj]=sqrt(ss+hh);
matrix[jj][ii]=matrix[ii][jj];
}
}
}


int is_solved(int n,int k)
{
return (k==n);
}

void process(int b)
{
int t,sum_dist=0.0;
for(t=1;t<b;t++)
sum_dist+=leng[t];
if(min>sum_dist)
{
min=sum_dist;
for(t=1;t<=b;t++)
{
final_dist[t]=leng[t]+16.0;
ans[t]=as[t];
}
}
}

int network(int n,int k,int y)
{
int u=0,g,s;
if(a[y]!=0)
return 0;
leng[k-1]=matrix[as[k-1]][y];
as[k]=y;
a[y]=1;
}

int backtrack(int n,int k)
{
int h,t,y;
if(is_solved(n,k))
{
process(n);
a[as[k]]=0;
}
k++;
for(t=1;t<=n;t++)
{
y=network(n,k,t);
if(y!=0)
{
backtrack(n,k);
}
}
a[as[k-1]]=0;
return 0;
}
void output(int g)
{
int i,l;
min=0.0;
for(l=1;l<g;l++)
min+=final_dist[l];
for(i=1;i<g;i++)
{
printf("Cable requirement to connect (%0.0f,%0.0f)",p[ans[i]].x,p[ans[i]].y);
printf(" to (%0.0f,%0.0f) ",p[ans[i+1]].x,p[ans[i+1]].y);
printf("is %0.2f feet.\n",final_dist[i]);
}
printf("Number of feet of cable required is %0.2f.\n",min);
}

void main()
{
long int i,j=0,l,in,k;
while(scanf("%ld",&in),in)
{
for(i=1;i<=in;i++)
{
scanf("%f %f",&p[i].x,&p[i].y);
a[i]=0;
}
dist(in);
j++;
printf("**********************************************************\n");
printf("Network #%ld\n",j);
min=1000000.00;
for(i=1;i<=in;i++)
{
as[1]=i;
a[i]=1;
sum_dist=0.0;
backtrack(in,1);
}

output(in);

for(i=1;i<=in;i++)
a[i]=0;
}
}

[sohel_acm]

I am in a great trouble with 216.I am continuously getting WA for this problem,but i can't find where is the error.I tried several critical input.In all cases my program gave correct output.Now plz someone help me.Here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 100

char c[M]={0};
long int as[M],ii,jj,a[M],ans[M];
//static int po=0;
float matrix[M][M],ss,hh,leng[M],min,sum_dist,final_dist[M];

struct point
{
	float x,y;
}p[M];

void dist(int node)
{
	for(ii=1;ii<=node;ii++)
	{
		for(jj=1;jj<=node;jj++)
		{
			matrix[ii][jj]=0.0;
			matrix[ii][jj]=0.0;
		}
	}
	
	for(ii=1;ii<node;ii++)
	{
		for(jj=ii+1;jj<=node;jj++)
		{
			ss=abs(p[ii].x-p[jj].x);
			ss*=ss;
			hh=abs(p[ii].y-p[jj].y);
			hh*=hh;
			matrix[ii][jj]=sqrt(ss+hh);
			matrix[jj][ii]=matrix[ii][jj];
		}
	}
}


int is_solved(int n,int k)
{
	return (k==n);
}

void process(int b)
{
	int t,sum_dist=0.0;
	for(t=1;t<b;t++)
			sum_dist+=leng[t];
	if(min>sum_dist)
	{
		min=sum_dist;
		for(t=1;t<=b;t++)
		{
			final_dist[t]=leng[t]+16.0;
			ans[t]=as[t];
		}
	}
}

int network(int n,int k,int y)
{
	int u=0,g,s;
	if(a[y]!=0)
		return 0;
	leng[k-1]=matrix[as[k-1]][y];
	as[k]=y;
	a[y]=1;
}

int backtrack(int n,int k)
{
	int h,t,y;
	if(is_solved(n,k))
	{
		process(n);
		a[as[k]]=0;
	}
	k++;
	for(t=1;t<=n;t++)
	{		
		y=network(n,k,t);
		if(y!=0)
		{
			backtrack(n,k);
		}
	}
	a[as[k-1]]=0;
	return 0;
}
void output(int g)
{
	int i,l;
	min=0.0;
	for(l=1;l<g;l++)
		min+=final_dist[l];
	for(i=1;i<g;i++)
	{
		printf("Cable requirement to connect (%0.0f,%0.0f)",p[ans[i]].x,p[ans[i]].y);
		printf(" to (%0.0f,%0.0f) ",p[ans[i+1]].x,p[ans[i+1]].y);
		printf("is %0.2f feet.\n",final_dist[i]);
	}
	printf("Number of feet of cable required is %0.2f.\n",min);
}

void main()
{
	long int i,j=0,l,in,k;
	while(scanf("%ld",&in),in)
	{
		for(i=1;i<=in;i++)
		{
			scanf("%f %f",&p[i].x,&p[i].y);
			a[i]=0;
		}
		dist(in);
		j++;
		printf("**********************************************************\n");
		printf("Network #%ld\n",j);
		min=1000000.00;
		for(i=1;i<=in;i++)
		{
			as[1]=i;
			a[i]=1;
			sum_dist=0.0;
			backtrack(in,1);
		}	
		
		output(in);
		
		for(i=1;i<=in;i++)
			a[i]=0;
	}
}

[Darko]

I thought it was MST, too - I just kept track of degrees while building it.

Can someone please check this input:

Code: Select all

8
115 104
126 26
125 81
35 110
20 128
138 74
106 44
117 118
8
144 135
18 58
94 112
37 111
90 9
85 95
67 9
73 43
8
8 107
0 38
68 144
102 37
55 84
41 111
77 108
27 123
8
106 95
110 97
88 109
128 26
11 33
26 41
126 141
19 75
8
25 45
58 58
13 145
21 0
29 108
71 67
112 104
70 98
8
90 84
90 141
7 51
34 12
139 8
109 150
150 141
112 6
0

[EDIT: removed potentially misleading output]

[asif_rahman0]

My accepted code genareted the following output:

Code: Select all

Network #1
Cable requirement to connect (126,26) to (106,44) is 42.91 feet.
Cable requirement to connect (106,44) to (138,74) is 59.86 feet.
Cable requirement to connect (138,74) to (125,81) is 30.76 feet.
Cable requirement to connect (125,81) to (115,104) is 41.08 feet.
Cable requirement to connect (115,104) to (117,118) is 30.14 feet.
Cable requirement to connect (117,118) to (35,110) is 98.39 feet.
Cable requirement to connect (35,110) to (20,128) is 39.43 feet.
Number of feet of cable required is 342.58.
**********************************************************
Network #2
Cable requirement to connect (144,135) to (94,112) is 71.04 feet.
Cable requirement to connect (94,112) to (85,95) is 35.24 feet.
Cable requirement to connect (85,95) to (37,111) is 66.60 feet.
Cable requirement to connect (37,111) to (18,58) is 72.30 feet.
Cable requirement to connect (18,58) to (73,43) is 73.01 feet.
Cable requirement to connect (73,43) to (67,9) is 50.53 feet.
Cable requirement to connect (67,9) to (90,9) is 39.00 feet.
Number of feet of cable required is 407.71.
**********************************************************
Network #3
Cable requirement to connect (0,38) to (8,107) is 85.46 feet.
Cable requirement to connect (8,107) to (27,123) is 40.84 feet.
Cable requirement to connect (27,123) to (41,111) is 34.44 feet.
Cable requirement to connect (41,111) to (68,144) is 58.64 feet.
Cable requirement to connect (68,144) to (77,108) is 53.11 feet.
Cable requirement to connect (77,108) to (55,84) is 48.56 feet.
Cable requirement to connect (55,84) to (102,37) is 82.47 feet.
Number of feet of cable required is 403.51.
**********************************************************
Network #4
Cable requirement to connect (128,26) to (106,95) is 88.42 feet.
Cable requirement to connect (106,95) to (110,97) is 20.47 feet.
Cable requirement to connect (110,97) to (126,141) is 62.82 feet.
Cable requirement to connect (126,141) to (88,109) is 65.68 feet.
Cable requirement to connect (88,109) to (19,75) is 92.92 feet.
Cable requirement to connect (19,75) to (26,41) is 50.71 feet.
Cable requirement to connect (26,41) to (11,33) is 33.00 feet.
Number of feet of cable required is 414.03.
**********************************************************
Network #5
Cable requirement to connect (21,0) to (25,45) is 61.18 feet.
Cable requirement to connect (25,45) to (58,58) is 51.47 feet.
Cable requirement to connect (58,58) to (71,67) is 31.81 feet.
Cable requirement to connect (71,67) to (112,104) is 71.23 feet.
Cable requirement to connect (112,104) to (70,98) is 58.43 feet.
Cable requirement to connect (70,98) to (29,108) is 58.20 feet.
Cable requirement to connect (29,108) to (13,145) is 56.31 feet.
Number of feet of cable required is 388.62.
**********************************************************
Network #6
Cable requirement to connect (139,8) to (112,6) is 43.07 feet.
Cable requirement to connect (112,6) to (34,12) is 94.23 feet.
Cable requirement to connect (34,12) to (7,51) is 63.43 feet.
Cable requirement to connect (7,51) to (90,84) is 105.32 feet.
Cable requirement to connect (90,84) to (90,141) is 73.00 feet.
Cable requirement to connect (90,141) to (109,150) is 37.02 feet.
Cable requirement to connect (109,150) to (150,141) is 57.98 feet.
Number of feet of cable required is 474.06.

-----------------------------------------------
rabbi

[asif_rahman0]

Can someone explain me how
"next_permutation()"
comes here?

thnx.

[Darko]

Thanks for that I/O - my idea was a bit (heh) flawed. As for next_permutation() - there are at most 8 nodes, you can try all possibilities (which I should've done).

[roy]

to asif_rahman0
In the test case you posted above, i found the your network three cost is not minimum. My program generates the following connection:


Cable requirement to connect (0,38) to (8,107) is 85.46 feet.
Cable requirement to connect (8,107) to (27,123) is 40.84 feet.
Cable requirement to connect (27,123) to (41,111) is 34.44 feet.
Cable requirement to connect (41,111) to (55,84) is 46.41 feet.
Cable requirement to connect (55,84) to (77,108) is 48.56 feet.
Cable requirement to connect (77,108) to (68,144) is 53.11 feet.
Number of feet of cable required is 391.29.

[Darko]

Where did (102,37) go?

[roy]

yes, Sorry i have make a mistake here.
I have done this question and i find the main problem is that when you find the minimum line among all the nodes, it is incorrect to use the concept that we can find the minimum line by just finding the minimum distance between every two nodes (dijkstra algorithm). Since this algorithm is only used to generate the minimum spanning tree, it is totally different with the minimum line.
However, i think some smart guy can convert the dijkstra algorithm or other algorithm to fit this situation. If anyone can convert it, i really hope they can post the algorithm here.