## 216 - Getting in Line

Moderator: Board moderators

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am
UFP2161 wrote: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
New poster
Posts: 10
Joined: Mon Mar 14, 2005 7:35 am

### Prob 216 Getting in Line----Why CE?

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
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
New poster
Posts: 4
Joined: Sat Jan 22, 2005 8:30 am
I havent try this question but I Think this is a minimum spanning tree problem, hope I am correct:P
TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 216(Getting in Line )------->Long Time Wrong Answer

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.``
Last edited by TISARKER on Fri Oct 28, 2005 6:54 pm, edited 2 times in total.
Mr. Arithmetic logic Unit
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
For the input

Code: Select all

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

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
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:
Thanks Joey
Mr. Arithmetic logic Unit
sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm

### 216!WA!!!!!!!Plz Help

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;
}
}
Love programmers,help programmers.
sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm

### 216 WA !!Plz Help

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

``````
Love programmers,help programmers.
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
``````
Last edited by Darko on Thu Jul 06, 2006 8:52 pm, edited 1 time in total.
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
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
Last edited by asif_rahman0 on Tue Aug 08, 2006 7:05 pm, edited 1 time in total.
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
Can someone explain me how
"next_permutation()"
comes here?

thnx.
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
New poster
Posts: 4
Joined: Sun Jul 30, 2006 7:02 am
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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am