534 - Frogger

[Bluefin]

Can someone please look at my code and tell me what's wrong??
I've got BOUNDLESS WA !!
I think it's just an application of Floyd, so where's my wrong??
any comment is welcome !! Thanks in advance ~~

Code: Select all

// Q534  Frogger 
// select the minimum of longest jumps ~~ minimax

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<math.h>
#define MAX 201

using namespace std;

int n, index = 1;
double d[MAX][MAX], ar[MAX][2];

void Floyed_Warshall();
int min(int a, int b);
int max(int a, int b);

int main(int argc, char argv[])
{
    while(cin >> n)
    {
        if(n == 0)
            break;
                
        for(int i = 1; i <= n; i++)
            cin >> ar[i][0] >> ar[i][1];
        
        for(int i = 1; i <= n; i++)
            for(int j = i+1; j <= n; j++)
                d[j][i] = d[i][j] = 
                sqrt((ar[j][1]-ar[i][1])*(ar[j][1]-ar[i][1])+(ar[j][0]-ar[i][0])*(ar[j][0]-ar[i][0]));
                
        Floyed_Warshall();
        cout << "Scenario #" << index++ << endl << "Frog Distance = ";
        printf("%.3f\n\n",d[1][2]);
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

void Floyed_Warshall()
{
     for(int i = 1; i <= n; i++)
            d[i][i] = 0;
        
     for(int k = 1; k <= n; k++)
         for(int i = 1; i <= n; i++)
             for (int j = 1; j <= n; j++)
                 d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
}

int min(int a, int b)
{
    return (a < b) ? a: b;
}

int max(int a, int b)
{
    return (a > b) ? a: b;
}

[Bluefin]

I've try to solve this problem ~~ But always WA

Can you give me more critical IO (my program gave correct output for the above IO) ??

Thanks in advance !!!

[sjn]

Can someone please look at my code and tell me what's wrong??
I've got BOUNDLESS WA !!
I think it's just an application of Floyd, so where's my wrong??
any comment is welcome !! Thanks in advance ~~

Code: Select all

// Q534  Frogger 
// select the minimum of longest jumps ~~ minimax

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<math.h>
#define MAX 201

using namespace std;

int n, index = 1;
double d[MAX][MAX], ar[MAX][2];

void Floyed_Warshall();
int min(int a, int b);
int max(int a, int b);

...
    system("PAUSE");

...
int min(int a, int b)
{
    return (a < b) ? a: b;
}

int max(int a, int b)
{
    return (a > b) ? a: b;
}

Your code seems ok except two things:
1. no pause, otherwise it will cause "Restricted Function";
2. function of "min" and "max" should return double and parameters should also be double.

/sjn

[mukeshtiwari]

plz some one tell me whats wrong with my code . Got WA many times .
i use floyed warshall algorithm . as problem states

a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.

and

The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

so we have to find minimum of all maximum distances over all possible paths . may be i m missing some thing . kindly help me . thnkx in advance

here is my code

Code: Select all

#include<cstdio>
#include<cmath>
#include<memory>
	int min(int a,int b)
		{
			if(a>b)
				return b;
			else
				return a;
		}
	int max(int a,int b)
		{
			if(a>b)
				return a;
			else
				return b;
		}
	int main()
		{

			int  graph[300][300],x[300],y[300],v=1;
			int n,i,j,k,k1,k2;
			while(scanf("%d",&n) && n)
			 {
			
				for(i=0;i<n;i++)
					scanf("%d%d",&x[i],&y[i]);
				for(i=0;i<n;i++)
				  {
					for(j=i;j<n;j++)
					   {
					     graph[i][j]=graph[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
					   }  

				 }
				/*for(i=0;i<n;i++)
				 {
					for(j=0;j<n;j++)
						printf("%d ",graph[i][j]);
					printf("\n");
				}*/
				for(k=0;k<n;k++)
				 {
				    for(i=0;i<n;i++)
					{
				          for(j=0;j<n;j++)
						{
							k1=max(graph[i][k],graph[k][j]);
							k2=graph[i][j];
							graph[i][j]=min(k1,k2);
						}
					}
				}
			printf("Scenario #%d\n",v++);
			printf("Frog Distance = %.3lf\n",sqrt((double)graph[0][1]));
			 }
		}

[helloneo]

Output description says..

Put a blank line after each test case, even after the last one.

So, you have to print an extra blank line..
I don't know why judge gives WA instead of PE

[mukeshtiwari]

thnkx a lot helloneo . i read this problem very carefully but not output discription ....thnkx again

[turcse143]

get help from this link:
http://www.comp.nus.edu.sg/~stevenha/pr ... %20Frogger

[WingletE]

To rafagiu:
Thanks for your testcase.
They did help me a lot!

By the way, in the last testcase, the n is 21.
I'd got confused by that case for some time, but it was really useful.

[saiful_sust]

I solve this problem with Floyd algorithm minimax

But Get Runtime error in MST
PLZ help me

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Node_num 210004

struct S
{
	int u,v,cost;
};
S a[Node_num];

int Set[Node_num],Rank[Node_num];
int Node,Edge;
int x[210003],y[210003];

void make_set(int x)
{
	Set[x] = x;
	Rank[x] = 0;
}

int find_set(int x)
{
	if(x != Set[x])
	{
		Set[x] = find_set(Set[x]);
	}
	return Set[x];
}

void Union(int x,int y)
{
	if(Rank[x] > Rank[y])
	{
		Set[y] = x;
	}
	else
	{
		Set[x] = y;
		if(Rank[x] == Rank[y])
		{
			Rank[y]++;
		}
	}
	return;
}

int comp_fun(const void *m,const void *n)
{
	S *x,*y;
	x=(S*)m;
	y=(S*)n;
	return ( x->cost - y->cost );
}

int main()
{
	int  test,n,m,s,k,i,j,t1,t2,u_set,v_set,kase=1,mn;
	double sum;

	while(scanf("%d",&n) == 1 && n)
	{
		for(i=0;i<n;i++)
			scanf("%d %d",&x[i],&y[i]);

		k=0;
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
            {

                a[k].u=i,a[k].v=j;
                t1=x[i]-x[j];t2=y[i]-y[j];
                a[k].cost = t1*t1 + t2*t2;
                k++;
            }
		}

		qsort(a,k,sizeof(S),comp_fun);

		for(i=0;i<=n;i++) make_set(i);

		for(i=0; i<k ;i++)
		{
			u_set=find_set(0);
			v_set=find_set(1);
			if(u_set != v_set)
			{
				Union(a[i].u,a[i].v);
			}
			else break;
		}
		if(i==0)i = 1;
		sum = sqrt(a[i-1].cost);
		printf("Scenario #%d\nFrog Distance = %.3lf\n\n",kase++,sum);
	}
	return 0;
}
[list]IMPOSSIBLE MEANS I M POSSIBLE [/list]

[prashantharshi]

it is an application of floyd warshal algo
finding the minimax path.
here we have to minimise the maximum edge value in all path
for(k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[j]=min(dp[j],max(dp[k],dp[k][j])

[garbage]

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define sz 205
#define inf 9999
using namespace std;

vector<long long>myVec[sz];
vector<double>dst[sz];

double findPath(long long r, long long pr[], double st[][sz], double mn)
{
    
	if(pr[r] == r)
    {
        printf("Frog Distance = %.3lf\n\n", mn);
		return 0;
    }

	else
	{
	    if(mn < st[r][pr[r]])
            mn = st[r][pr[r]];
        
		findPath(pr[r], pr, st, mn);
	}
}

long long shortestPath(long long n, long long from, long long to)
{
    long long hold, index, pr[sz], visit[sz];
    double mn, newDist, d[sz], st[sz][sz];

    for(long long i=0;i<=n;i++)
    {
        pr[i] = i;
        d[i] = inf;
        visit[i] = 0;
    }

    d[from] = 0;
    visit[from] = 1;

    while(from != to)
    {
        for(long long i=0;i<myVec[from].size();i++)
        {
            index = myVec[from][i];

            if(visit[index] == 0)
            {
                newDist = dst[from][i];
                if(newDist < d[index])
                {
                    pr[index] = from;
                    d[index] = newDist;
                }
            }
        }

        mn = inf;
        for(long long i=0;i<=n;i++)
        {
            if(visit[i] == 0 && d[i] < mn)
            {
                mn = d[i];
                hold = i;
            }
        }
        
        st[hold][from] = mn;
        from = hold;
        visit[from] = 1;
    }
    
    mn = 0;
    findPath(to, pr, st, mn);

    return 0;
}

int main()
{
    long long n, T=1;
    double dist, pos[sz][2];

    while(cin>>n)
    {
        if(n==0)
            break;

        for(long long i=1;i<=n;i++)
            cin>>pos[i][0]>>pos[i][1];

        for(long long i=1;i<=n-1;i++)
        {
            for(long long j=i+1;j<=n;j++)
            {
                dist = sqrt(pow((pos[i][0] - pos[j][0]), 2) + pow((pos[i][1] - pos[j][1]), 2));
                myVec[i].push_back(j);
                myVec[j].push_back(i);
                dst[i].push_back(dist);
                dst[j].push_back(dist);
            }
        }

        cout<<"Scenario #"<<T++<<endl;
        shortestPath(n, 2, 1);

        for(long long i=0;i<=n;i++)
        {
            myVec[i].clear();
            dst[i].clear();
        }
    }
    return 0;
}

[brianfry713]

Try solving it using Floyd-Warshall's Algorithm.