Page 4 of 4
Re: I used brute force for this problem, but always have get
Posted: Sat Sep 15, 2007 5:35 pm
by Robert Gerbicz
zid_adrenalyns wrote:
Actually, I have the same output for the samples posted.
I don't think that.
For example this line is wrong:
Code: Select all
return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);
because the cabel is longer by 16 feets than the distance of the two points, so it should be:
Code: Select all
return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y]))+16.0;
There can be some other errors also.
And your program is little ugly, I would never write this:
still WA
Posted: Sun Sep 16, 2007 4:12 pm
by zid_adrenalyns
Robert Gerbicz wrote:zid_adrenalyns wrote:
Actually, I have the same output for the samples posted.
I don't think that.
For example this line is wrong:
Code: Select all
return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);
because the cabel is longer by 16 feets than the distance of the two points, so it should be:
Code: Select all
return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y]))+16.0;
U r right!, I made a terrible mistake, but I have fixed that in my last submition (before the last post).
And your program is little ugly, I would never write this:
About the code post below, U can chage this lines for enum{X,Y}; I think this is irrelevant.
There can be some other errors also.
Are u find them? Please tell me.
Posted: Sun Oct 14, 2007 5:50 am
by gba356
I tried to solve the problem with DFS and some branch and bound, but it keeps give me WA.
Could somebody help me?
Code: Select all
#include<iostream>
#include<math.h>
#define N 10
#define INF 214748647
#define Dist(i,j) sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) )
using namespace std;
int n,x[N],y[N];
int visit[N]={0},path[N],minpath[N];
double mindist,dist[N][N];
inline void
DFS(int start,int depth,double tempdist)
{
path[depth-1]=start;
if( tempdist>=mindist )return;
if( depth==n&&tempdist<mindist )
{
for(int i=0;i<n;i++)
minpath[i]=path[i];
mindist=tempdist;
return;
}
for(int i=0;i<n;i++) /* DFS */
if( !visit[i] )
{
visit[i]=1;
DFS(i,depth+1,tempdist+dist[start][i]);
visit[i]=0;
}
}
int main()
{
// freopen("216.in","r",stdin);
// freopen("216.out","w",stdout);
cout.setf(ios::fixed);
cout.precision(2);
int case_n=0;
while( cin>>n,n )
{
mindist=INF;
for(int i=0;i<n;i++)
cin>>x[i]>>y[i];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dist[i][j]=dist[j][i]=Dist(i,j);
for(int i=0;i<n;i++)
DFS(i,0,0);
cout<<"**********************************************************"<<endl;
cout<<"Network #"<<++case_n<<endl;
for(int i=0;i<n-1;i++)
cout<<"Cable requirement to connect ("<<x[minpath[i]]<<","
<<y[minpath[i]]<<") to ("<<x[minpath[i+1]]<<","<<y[minpath[i+1]]<<") is "
<<dist[minpath[i]][minpath[i+1]]+16<<" feet."<<endl;
cout<<"Number of feet of cable required is "<<mindist+16*(n-1)<<"."<<endl;
}
}
i tried all the sample I/O but still getting wrong answer. :
Posted: Thu Nov 22, 2007 1:13 am
by ahmadfarid
please help please please please
i tried all the sample I/O but still getting wrong answer. :'(
[/code]#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
//ifstream in ("input.txt");
//ofstream out ("output.txt");
long n;
long path[10];
bool valid[10];
long x[8], y[8];
double minimum = 2147483647;
double total = 0;
long order[8];
long X[8], Y[8];
double Dis[8];
void Display()
{
long i;
total = 0;
for(i=0; i<n-1; i++)
{
// out << path << " ";
double xdif, ydif;
xdif = x[path[i+1]] - x[path];
ydif = y[path[i+1]] - y[path];
total += (16+sqrt(pow(double(ydif),2.0)+pow(double(xdif),2.0)));
}
// out << "\t" << total << endl;
if(minimum>total)
{
minimum = total;
for(i=0; i<n; i++)
{
double xdif = x[path[i+1]] - x[path];
double ydif = y[path[i+1]] - y[path];
X = x[path];
Y = y[path];
Dis = (16+sqrt(pow(double(ydif),2.0)+pow(double(xdif),2.0)));
}
}
}
void Permutation(long counter)
{
if(counter == n)
{
total = 0;
Display();
return;
}
long i;
for(i=0; i<n; i++)
{
if(valid[i])
{
valid[i] = false;
path[counter] = i;
Permutation(counter+1);
valid[i] = true;
}
}
}
int main()
{
long counterr = 0;
while (cin >> n)
{
if (n==0)
break;
for (long i=0; i<n; i++)
cin >> x[i] >> y[i];
for(long i=0; i<n; i++)
valid[i] = true;
Permutation(0);
Display();
//if (counterr!=0)
cout<<"**********************************************************"<<endl;
cout << "Network #" << ++counterr << endl;
for (long i=0; i<n-1; i++)
{
double xdif = X[i] - X[i+1];
double ydif = Y[i] - Y[i+1];
cout << "Cable requirement to connect (" << X[i] << "," << Y[i] << ") to (" << X[i+1] << "," << Y[i+1] << ") is ";
cout << setiosflags(ios::fixed) << setiosflags(ios::showpoint) << setprecision(2) << Dis[i] << " feet.\n";
}
cout << "Number of feet of cable required is ";
cout << setiosflags(ios::fixed) << setiosflags(ios::showpoint) << setprecision(2) << minimum << "." << endl;
minimum = 2147483647;
total = 0;
}
return 0;
}
Posted: Wed Dec 05, 2007 3:16 pm
by Orgi
Can anybody supply some test cases for 216?
Please, if someone has AC on C or C++, i'd like to know how he/she copes with rounding errors?
Posted: Sat Mar 15, 2008 6:07 pm
by haaaz
I am also getting WA on the new server when I tried to resubmit codes I wrote long time ago... I have tried all sample inputs I found in this forum and I think my program gives the correct outputs.
I am just using DFS brute force....
AND most importantly my code got accepted a few years ago on the old server!!! can anybody help?
Code: Select all
//p216 Getting in Line
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const double INF=999999999999.0;
struct com {
int x,y;
};
com comlist[8];
int n;
int list[8],ans[8];
double total;
double d[8][8];
bool used[8]={false};
double dist(com a, com b) {
return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))+16;
}
void p(int depth) {
if (depth==n) {
//caluculate distance
double t=0;
for (int i=1; i<n; i++) t+= d[ list[i-1] ][ list[i] ];
if (t<total) {
total=t;
for (int i=0; i<n; i++) ans[i]=list[i];
}
return;
}
for (int i=0; i<n; i++) {
if (used[i]) continue;
list[depth]=i;
used[i]=true;
p(depth+1);
used[i]=false;
}
}
int main() {
com x;
int test=1;
cout.setf(ios::fixed);
cout.precision(2);
while (cin >> n) {
if (n==0) break;
total=INF;
cout << "**********************************************************\n"
<< "Network #" << test << '\n';
for (int i=0; i<n; i++) {
list[i]=i;
cin >> x.x >> x.y;
comlist[i]=x;
}
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j]=dist(comlist[i],comlist[j]);
p(0);
for (int i=1; i<n; i++) {
cout << "Cable requirement to connect (" << comlist[ans[i-1]].x << "," << comlist[ans[i-1]].y
<< ") to (" << comlist[ans[i]].x << "," << comlist[ans[i]].y << ") is " << d[ans[i-1]][ans[i]] << " feet.\n";
}
cout << "Number of feet of cable required is " << total << ".\n";
test++;
}
return 0;
}
[/code]
Re: 216 WA !!Plz Help
Posted: Mon May 09, 2011 9:29 pm
by Shafaet_du
Try this cases:
Code: Select all
8
100 150
102 23
34 67
32 63
11 25
132 35
54 122
54 23
8
120 15
102 21
34 64
132 16
1 125
13 135
12 162
55 45
0
output:
Code: Select all
**********************************************************
Network #1
Cable requirement to connect (132,35) to (102,23) is 48.31 feet.
Cable requirement to connect (102,23) to (54,23) is 64.00 feet.
Cable requirement to connect (54,23) to (11,25) is 59.05 feet.
Cable requirement to connect (11,25) to (32,63) is 59.42 feet.
Cable requirement to connect (32,63) to (34,67) is 20.47 feet.
Cable requirement to connect (34,67) to (54,122) is 74.52 feet.
Cable requirement to connect (54,122) to (100,150) is 69.85 feet.
Number of feet of cable required is 395.62.
**********************************************************
Network #2
Cable requirement to connect (132,16) to (120,15) is 28.04 feet.
Cable requirement to connect (120,15) to (102,21) is 34.97 feet.
Cable requirement to connect (102,21) to (55,45) is 68.77 feet.
Cable requirement to connect (55,45) to (34,64) is 44.32 feet.
Cable requirement to connect (34,64) to (1,125) is 85.35 feet.
Cable requirement to connect (1,125) to (13,135) is 31.62 feet.
Cable requirement to connect (13,135) to (12,162) is 43.02 feet.
Number of feet of cable required is 336.10.
no need to use eps
Re: 216(Getting in Line )------->Long Time Wrong Answer
Posted: Mon Jun 18, 2012 12:35 pm
by @li_kuet
Re: 216 WA !!Plz Help
Posted: Mon Jun 18, 2012 12:38 pm
by @li_kuet
Re: 216 WA !!Plz Help
Posted: Tue Jun 19, 2012 12:23 am
by brianfry713
Input:
AC output:
Code: Select all
**********************************************************
Network #1
Cable requirement to connect (8,11) to (8,16) is 21.00 feet.
Cable requirement to connect (8,16) to (9,16) is 17.00 feet.
Number of feet of cable required is 38.00.
Re: 216(Getting in Line )------->Long Time Wrong Answer
Posted: Tue Jun 19, 2012 12:24 am
by brianfry713
Re: 216 - Getting in Line
Posted: Wed Jan 01, 2014 5:55 am
by Farsan
MST should not work here because every node (except terminal nodes) must have exactly 2 edges but in mst any node can have any number of edges connected with it...
Re: 216 - Getting in Line
Posted: Wed Jan 08, 2014 3:02 am
by brianfry713
Don't find the MST. Each network has at least 2 and at most 8 computers. Use a brute force algorithm.
