10803 - Thunder Mountain

[mf]

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]

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]

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]

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. :-)

[roticv]

Thanks alot. It is a very stupid mistake on my part.

[rhak_so]

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 imprimir_padre(int p[][MAXVERT]);
//void camino(int origen, int destino);

double grafo[MAXVERT][MAXVERT];
int padre[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++)
            {
                padre[i][j]=NULO;
                if(i==j)
                {grafo[i][j]=0.0;
                //padre[i][j]=NULO;
                }else
                {
                grafo[i][j]=INFINITO;  
                //padre[i][j]=j;    
                }
            }
     }
}
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;
                    padre[i][j]=k;    
                }    
            }
        }    
    }        
}

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]

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????

[nymo]

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() ?

[mohsincsedu]

What's the problem here???

Any problem within the loops???

[nymo]

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

[mohsincsedu]

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

[nymo]

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 */

[mohsincsedu]

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

[Shafaet_du]

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]

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