## 534 - Frogger

Moderator: Board moderators

Bluefin
New poster
Posts: 20
Joined: Sat Jul 08, 2006 3:39 pm
Contact:
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;
}
``````
"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:
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) ??

"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:
Bluefin wrote: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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
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
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
thnkx a lot helloneo . i read this problem very carefully but not output discription ....thnkx again

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
''I want to be most laziest person in the world''

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

### Re: 534 Frogger - I/O

To rafagiu:
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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 534 Frogger - I/O

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

### Re: 534 - Frogger help

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

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

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