10803 - Thunder Mountain

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

Moderator: Board moderators

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

Post by mf » Tue May 24, 2005 12:35 pm

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

Post by wos » Thu May 26, 2005 8:41 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

Post by roticv » Sun Jun 05, 2005 6:46 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;
}


User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed Jun 08, 2005 5:54 am

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

Post by roticv » Thu Jun 23, 2005 7:15 pm

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

Post by rhak_so » Fri Oct 13, 2006 8:33 pm

I get WA , need help .

It is my code :D :

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
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Tired about 10803

Post by mohsincsedu » Tue Mar 27, 2007 4:37 pm

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

Post by nymo » Wed Mar 28, 2007 4:16 pm

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:

Post by mohsincsedu » Wed Mar 28, 2007 4:33 pm

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

Post by nymo » Wed Mar 28, 2007 4:39 pm

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:

Post by mohsincsedu » Wed Mar 28, 2007 4:42 pm

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

Post by nymo » Wed Mar 28, 2007 4:47 pm

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:

Post by mohsincsedu » Wed Mar 28, 2007 5:26 pm

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10803 - Thunder Mountain

Post by Shafaet_du » Fri Oct 08, 2010 11:24 am

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

Post by mostafa_angel » Fri May 27, 2011 12:15 am

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

Post Reply

Return to “Volume 108 (10800-10899)”