216 - Getting in Line

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

Post by watershed »

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?

Post by 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
New poster
Posts: 4
Joined: Sat Jan 22, 2005 8:30 am

Post by camus »

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
Location: Bangladesh
Contact:

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

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

Post by 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
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER »

Thanks Joey :D
Mr. Arithmetic logic Unit

sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm
Location: Bangladesh

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

Post by 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;
}
}
Love programmers,help programmers.

sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm
Location: Bangladesh

216 WA !!Plz Help

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


Love programmers,help programmers.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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]
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

Post by 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
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

Post by asif_rahman0 »

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

:) thnx.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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
New poster
Posts: 4
Joined: Sun Jul 30, 2006 7:02 am

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Where did (102,37) go? :)

roy
New poster
Posts: 4
Joined: Sun Jul 30, 2006 7:02 am

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

Post Reply

Return to “Volume 2 (200-299)”