534 - Frogger

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

Moderator: Board moderators

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:

Post by Bluefin » Sat Nov 04, 2006 5:29 pm

Can someone please look at my code and tell me what's wrong??
I've got BOUNDLESS WA !! :cry:
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;
}
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:

Post by Bluefin » Sat Nov 04, 2006 5:31 pm

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 !!!
"It's nice to be important, but it's more important to be nice"

http://bluefintuna.wordpress.com/

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Mon Apr 30, 2007 10:12 am

Bluefin wrote:Can someone please look at my code and tell me what's wrong??
I've got BOUNDLESS WA !! :cry:
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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Sat Sep 22, 2007 11:57 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Oct 01, 2007 10:37 am

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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Tue Oct 02, 2007 6:10 am

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

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Mon Feb 18, 2008 7:54 pm

''I want to be most laziest person in the world''

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Re: 534 Frogger - I/O

Post by WingletE » Sun Feb 24, 2008 10:51 am

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

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

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 534 Frogger - I/O

Post by saiful_sust » Wed Feb 17, 2010 4:10 pm

I solve this problem with Floyd algorithm minimax

But Get Runtime error in MST
PLZ help me :oops: :oops: :oops:

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
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 534 - Frogger help

Post by prashantharshi » Sat Jun 07, 2014 3:38 pm

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
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Re: 534 - Frogger, WA, Why???

Post by garbage » Tue Feb 03, 2015 7:41 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 534 - Frogger

Post by brianfry713 » Wed Feb 04, 2015 9:28 pm

Try solving it using Floyd-Warshall's Algorithm.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 5 (500-599)”