10803 - Thunder Mountain

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
More test cases:

Code: Select all

``````2

2
0 0
0 0

3
0 0
10 0
20 1``````
Output:

Code: Select all

``````Case #1:
0.0000

Case #2:
Send Kurdy``````
Maybe there are no test cases like the 1st one above in the judge's input, the problem statement doesn't say that the cities always have unique coordinates.

And by the way, you can use the value 1.0 / 0.0 as +infinity.

wos
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am
Ok i solved it at last. The problem was i didn't read carefuly enough. I thought that you should output "Send Kurdy" when there are no ways to get from any town to any other, and not when there is only one such way. Thanks for your help.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
I did the following. According to the sample input, it works, but I don't know why I still got a WA.

Code: Select all

``````#include <stdio.h>
#include <math.h>

int z,n,N,i,j,k;
int x[105], y[105];
double w[105][105],tmp,max;

double sq(int a){
return (double)a*a;
}

int main(){
scanf("%d ",&N);
for (z=0;z<N;z++){
scanf("%d",&n);
for (i=0;i<n;i++){
scanf("%d %d",&x[i],&y[i]);
}
for (i=0;i<n;i++){
for (j=i+1;j<n;j++){
tmp = sq(x[i]-x[j])+sq(y[i]-y[j]);
tmp = sqrt(tmp);
w[i][i] = 0;
if (tmp<=10.0){
w[i][j] = tmp;
w[j][i] = 0;
}else{
w[i][j] = 10000000;
w[j][i] = 10000000;
}
}
}
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (w[i][j] > w[i][k] + w[k][j] )
w[i][j] = w[i][k] + w[k][j];
printf("Case #%d:\n",z+1);
max= -1000000;
for (i=0;i<n;i++){
for (j=0;j<n;j++){
if (max < w[i][j])
max = w[i][j];
}
}
if (max >= 10000000)
printf("Send Kurdy\n");
else
printf("%.4lf\n",max);
printf("\n");
}
return 0;
}

``````

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
There is an obvious bug in the way you build the graph. Because of that, your program gives much smaller answers for many of the test cases. Print out the adjacency matrix w before you run Floyd-Warshall and look at it. :-)
If only I had as much free time as I did in college...

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
Thanks alot. It is a very stupid mistake on my part.

rhak_so
New poster
Posts: 1
Joined: Fri Oct 13, 2006 8:14 pm
Location: LIMA - PERU

10803 - Thunder Mountain

I get WA , need help .

It is my code :

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<cmath>
#define MAXVERT 400
#define INFINITO 1000000.0000
#define NULO -1

void inserta_grafo();
void max_dist();
void inicializar();
void floyd();
//void imprimir(double p[][MAXVERT]);
//void camino(int origen, int destino);

double grafo[MAXVERT][MAXVERT];
struct town{
//int ntown;
int x;
int y;

};
town aux[101];
int numvert;
double max;
int cont;
bool flag1;
int main()
{
//freopen("10803.in.txt","r",stdin);
//freopen("10803.out.txt","w",stdout);
int ncasos,x,y;
scanf("%d",&ncasos);
for(int kase=1;kase<=ncasos;kase++)
{
flag1=true;
inicializar();
cont=0;
max=-1.0;
scanf("%d",&numvert);
for(int i=0;i<numvert;i++)
{
scanf("%d %d",&x,&y);
//aux[i].ntown=i;
aux[i].x=x;
aux[i].y=y;
}

inserta_grafo();
floyd();
max_dist();

if(kase==1)
printf("Case #%d:\n",kase);
else
printf("\nCase #%d:\n",kase);

if(flag1==true)
{    //if(max!=-1.0)
max=max*10000.0+0.5;
//int dmax=int(max);
max=double((floor(max))/10000.0);
printf("%.4lf\n",max);
//else
//  printf("Send Kurdy\n");
}else
printf("Send Kurdy\n");

}
return 1;
}
void inicializar()
{
for(int i=0;i<MAXVERT;i++)
{
for(int j=0;j<MAXVERT;j++)
{
if(i==j)
{grafo[i][j]=0.0;
}else
{
grafo[i][j]=INFINITO;
}
}
}
}
void inserta_grafo()
{
for(int i=0;i<numvert;i++)
{
for(int j=0;j<numvert;j++)
{

if(i==j)
grafo[i][j]=0;
else{
double d=pow(double(aux[i].x-aux[j].x),2.0)+pow(double(aux[i].y-aux[j].y),2.0);
//printf("%lf %lf\n",ceil(d),floor(10.0));
//if(ceil(d)>floor(10.0))
if(d>100.0)
{
//printf("d: %lf 10.0: %lf\n",d,10.0);
grafo[i][j]=INFINITO;
}else
{
grafo[i][j]=sqrt(d);
}
}

}
}
}
void floyd()
{
for(int k=0;k<numvert;k++)
{
for(int i=0;i<numvert;i++)
{
for(int j=0;j<numvert;j++)
{
double suma=grafo[k][j]+grafo[i][k];
if(grafo[i][j]>suma)
{
grafo[i][j]=suma;
}
}
}
}
}

void max_dist()
{int flag=0;
for(int i=0;i<numvert;i++)
{
flag=0;
for(int j=0;j<numvert;j++)
{

if(i!=j)
if(grafo[i][j]<INFINITO)
{
flag=1;
//printf("\nentro y cambio el flag  %lf  i:%d j:%d\n",grafo[i][j],i,j);
if(grafo[i][j]>max)
{    max=grafo[i][j];
//printf("%d %d max= %lf\n",i,j,max);
}
}
}
if(flag==0)
flag1=false;
}
}
``````

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

I got WA....

Here is my code:

Code: Select all

``````#include<stdio.h>
#include<math.h>

#define INF 100000

double T[105][105];

double Min(double a, double b, double c)
{
if(a>(b+c+2*sqrt(b*c)))
return (b+c+2*sqrt(b*c));
return a;
}

int Dis(int a,int b, int c, int d)
{
return ((a-c)*(a-c)+(b-d)*(b-d));
}

int main()
{

int n,tst,i,j,k,cas = 1,X[105],Y[105],temp,dis;
double max;
scanf("%d",&tst);

while(tst--)
{
scanf("%d",&n);
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
T[i][j] = INF;
for(i = 0;i<n;i++)
{
scanf("%d %d",&X[i],&Y[i]);
}
for(i = 0;i<n-1;i++)
{
for(j = i + 1;j<n;j++)
{
dis = Dis(X[i],Y[i],X[j],Y[j]);

if(dis<=100)
{
T[i][j] = T[j][i] = dis;
}
}
}
for(i = 0;i<n;i++)
T[i][i] = 0;

for(k = 0;k<n;k++)
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
{
T[i][j] = Min(T[i][j],T[i][k],T[k][j]);
}
max = 0;
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
{
if(max<T[i][j])
max = T[i][j];
}

printf("Case #%d:\n",cas++);
if(max==INF)
printf("Send Kurdy\n\n");
else
printf("%.4lf\n\n",sqrt(max));
}
return 0;
}
``````

What the wrong in my code????
Last edited by mohsincsedu on Wed Mar 28, 2007 4:54 pm, edited 1 time in total.
Amra korbo joy akhdin............................

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
To mohsincsedu,

Code: Select all

``````      for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
for(k = 0;k<n;k++)
{
T[i][j] = Min(T[i][j],T[i][k],T[k][j]);
}
``````
is this the way to do FW() ?
regards,
nymo

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
What's the problem here???

Any problem within the loops???
Amra korbo joy akhdin............................

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

To mohsincsedu...

Correct way to FW():

Code: Select all

``````for (k=0; k<n; k++)     // According to your code, k should be the outermost
for (i=0; i<n; i++)  // index ...
for (j=0; j<n; j++)
{
Process...
}
``````
Last edited by nymo on Wed Mar 28, 2007 4:57 pm, edited 1 time in total.
regards,
nymo

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
Still WA.......................

Min() Fuction is defined same way as previous......
bcaz T[j] is distance^2

So T[j] = Min(T[j],(T[k]+T[k][j])) is not true here.....
Last edited by mohsincsedu on Wed Mar 28, 2007 4:48 pm, edited 1 time in total.
Amra korbo joy akhdin............................

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
mohsincsedu, I 've just an overview of your code... Min() should be changed... may be some other flaws... I don't know... your FW() implementation is not okay ....

/* EDIT: I missed the part that you were not finding the actual distance */
regards,
nymo

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
I don't understand where is the problem finding distance

T[j] contains sq of distance

so in FW T[j] update by b and c in the following way:
first distance is sqrt(b)
second distance is sqrt(c)

so (sqrt(b)+sqrt(c))^2 = b + c + 2*sqrt(b*c)

what's the Wrong........
Amra korbo joy akhdin............................

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

Re: 10803 - Thunder Mountain

Floyed Warshall can solve the problem easily. Be careful about precision though.Every answer will obey the formula fabs(ans*1e4 - floor(ans*1e4) - 0.5) > 1e-2 is a useless line.
sample i/O:

Code: Select all

``````3
6
12 10
1 12
4 5
7 9
1 3
10 15
7
15 20
25 30
30 31
26 27
32 19
31 31
21 24
8
15 20
25 30
30 31
26 27
32 19
31 31
21 24
12 10``````

Code: Select all

``````Case #1:
15.1935

Case #2:
23.0421

Case #3:
Send Kurdy

``````
good luck!

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 10803 - Thunder Mountain

hi...
I got WA for this Problem...
can anybody help...

Code: Select all

``````#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

#define INF 99999.0

typedef struct p{
double x , y;
}point;

point in[110];
double path[110][110];

double dis(point a , point b)
{
return sqrt(((a.x - b.x)*(a.x - b.x)) + ((a.y - b.y)*( a.y - b.y)));
}

int main()
{
double res;
int t , n;
int dcnt;
cin >> t;
int cnt = 1;
bool kur;
while(t--)
{
for(int i = 0 ;i < 110 ; i++)
{
for(int j = 0; j < 110 ; j++)
{
if (i == j)
path[i][j] = 0;
else
path[i][j] = INF;
}
}
kur = false;
res = 0;
cin >> n;
//double a , b;
for(int i =0  ;i < n ; i++)
{
cin >> in[i].x >> in[i].y;
}

bool is;
for(int i = 0 ; i < n ; i++ )
{
is = false;
for(int j = 0 ; j < n ; j++)
{
double tmp = dis(in[i] , in[j]);
if(tmp*tmp <= 100.00 && i != j)
path[i][j] = path[j][i] = tmp , is = true;
}
if(!is)
{
kur = true;
break;
}
}
if(!kur)
{
for(int k  = 0 ; k < n ; k++)
{
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
path[i][j] = min(path[i][j] , path[i][k] + path[k][j]);
}
}
}
}

/*for(int i = 0 ;i < n ; i++)
{
for(int j = 0; j < n ; j++)
{
printf("i = %d , j = %d , path[i][j] = %lf\n" , i , j , path[i][j]);
}
}*/

for(int i =0 ; i < n ; i++)
res =max(res, *max_element(path[i] , path[i]+n ));
printf("Case #%d:\n",cnt++);
if(!kur)
printf("%0.4lf\n",res);
else
printf("Send Kurdy\n");
//if(t > 0)
printf("\n");
}

return 0;
}
``````