11135 - Gopher that walks and swims

[Artikali]

I am tired of getting WA. here is my code.

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
using namespace std;
const double _2=sqrt(2.0);
double dist(double x,double y){
	return sqrt(x*x+y*y);
}

int rd1(double a){
	int r;
	if ((a-floor(a))<0.5) r=floor(a);
	else r=ceil(a);
	return r;
}
int main(){
	//freopen("a.in","r",stdin);
	double D,L,xs,ys,xt,yt,k,m;
	int xsn,ysn,xtn,ytn,xn,yn,mn,dif,n;
	double swim,walk,x1,y1,x2,y2,s1,s2,t1,t2;
	int s[330],sr[330];
	while(1){
		cin>>D>>L>>xs>>ys>>xt>>yt;
		dif=D;
		if (dif==0) break;
		xsn=floor((xs-L)/D);
		xtn=floor((xt-L)/D);
		ysn=floor((ys-L)/D);
		ytn=floor((yt-L)/D);
		xn=xtn-xsn;
		yn=ysn-ytn;
		mn=xn;
		dif=yn-xn;
		assert(dif>=0);
		swim=2*L*_2*mn+dif*2*L;
		if (mn==0){
			ys=ys-dif*2*L;
			walk=sqrt((xs-xt)*(xs-xt)+(ys-yt)*(ys-yt));
		}
		else
		if ((xt-xs)<0.0000001){
			walk=ys-yt-swim;
		}
		else {
		x1=(xsn+1)*D-L-xs;
		y1=ys-(ysn*D+L);
		
		x2=xt-(xtn*D+L);
		y2=(ytn+1)*D-L-yt;

		k=(ys-yt)/(xs-xt);
		m=ys-k*xs-L;
		n=xtn-xsn;
		for(int i=0;i<n;i++){
			s[i]=rd1((k*D*(i+xsn+1)+m)/D);
		}
		for(int i=1;i<n;i++){
			sr[i]=s[i-1]-s[i];
		}
		k=D-2*L;
		walk=0;
		for(int i=1;i<n;i++){
			walk=walk+sqrt(sr[i]*sr[i]+1.0);
		}
		walk=walk*k;
		walk+=dist(x1,y1+(ysn-s[0])*k);
		walk+=dist(x2,y2+(s[n-1]-ytn-1)*k);
		}
		printf("The gopher has to swim %0.2f meters and walk %0.2f meters.\n",swim,walk);
	}
	return 0;
}

Please help me.

thanks.

[sclo]

I am tired of getting WA. here is my code.

How you compute the walking distance is wrong. You should use a O(n^2) DP to compute it, where n is the number of minimum ditches to cross. I think that's the most tricky part of this question.

That's why the following statement is important:

It is also known that the gopher on his way to the target point will not have to swim through more than 300 ditches.

[little joey]

You should use a O(n^2) DP to compute it, where n is the number of minimum ditches to cross.

Not quite correct: you can use DP to compute it (I doubt that that is O(n^2) tho, but that may be a matter of definition), but that is not the optimal solution for this problem.