10804 - Gopher Strategy

[nano72]

Hi guys,

I am writing some code to do normal rounding passing it in the value say 0.085 rounding it to .01 places where i should get 0.09. (note this only one example I may want to round it .001, etc )
Has anyone out there a neat way I could so this in c++.

Thanks in advance ,
nano72

[Abednego]

If d is the number of digits you want to round to, do this:

Code: Select all

double x = 0.085;
double m = pow( 10.0, d );
x = (int)(x * m + 0.5) / m;

Note the doubles. Make sure you're not dividing integers by integers.

[nano72]

Thanks for that but checked it out and it doesn't do alot
My return value is 0.000000
where i would expect 0.09

the substituding is

double x = 0.085;
double m = pow( 10.0, 0.01);
x = (int)(0.085 * m + 0.5) / m;


Any ideas ..

[Abednego]

change 0.01 to 2.

[nano72]

Hi Abednego,
Tried that substitude and it works for the .085 combination I now get .09 which is correct!
BUT for the .086 - i get .091 expect .09
for .081 - i get .86 expect .08
.08 get .085 where i expect to get .08 if rounding to nearest 0.01

Any ideas here ..

Thanks again !

[898989]

please, some help, this is the first time i write this type of binary search, can any one find the bug

Code: Select all

		if(m != k && n != 0)
		{
			while(fabs(start-end) > EPS)
			{
				middle = (start+end)/2;
				
				/* Build Bipartite graph using matching condition d<=middle */
				for(i=0;i<=m;i++)
				{
					for(j=0;j<=n;j++)
						cap[i][j] = 0;
				}	
				
				for(i=0;i<m;i++)
				{
					for(j=0;j<n;j++)
					{
						d = hypot(xg[i]-xh[j], yg[i]-yh[j]);
						
						if(d <= middle)	cap[i][j] = 1;
					}
				}	
				
				n_right_side = m;	n_left_side = n;
				
				max = Bipartite();
				
				if(max >= m-k)		end   = middle;
				else				start = middle;
			}
		}

		cout<<"Case #"<<l<<":\n";

		if(m == k)	
			cout<<0<<"\n";
		else if(n == 0)
			cout<<"Too bad.\n";
		else		
			cout<<middle+EPS<<"\n";

xg[], yg[] are the positions of gophers, xh[], yh[] are the positions of holes.

Assume Bipartite(); is a function that calc max bipartite matching
hypot(x, y) = sqrt(x*x+y*y);
intially start = 0;
end = largest distance between (xg, yg[j]) for all i, j.
i try it once end = 1000000..

[shihabrc]

I am doing bin search on distance and running mbm. I'm getting wa in this.

Code: Select all

#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define NIL -1
#define MAXN 110

typedef struct Point_
{
	double x,y;
} Point_;

double maxDis;
int Match[MAXN];
int v,M,N;
double W[MAXN][MAXN];
bool visited[MAXN];
vector <int> adj[MAXN];
Point_ field[MAXN];


bool augment(int u)
{
	int next;
	if( u == -1 ) 
		return true;

	for( int i = 0; i < adj[u].size(); i++ )
	{
		next = adj[u][i];
		if( !visited[next] )
		{
			visited[next] = true;
			if(augment(Match[next]))
			{
				Match[next] = u;
				return true;
			}
		}
	}

	return false;
}


int MBM(double w)
{
	int i,match,j;

	memset(Match,NIL,sizeof(Match));

	for( i = 1; i <= M; i++ ) adj[i].clear();
		
	for( i = 1; i <= M; i++ )
	{
		for( j = M + 1; j < N + M + 1; j++ )
		{
			if( W[i][j] <= w ) adj[i].push_back(j);
		}
	}

	match = 0;

	for( i = 1; i <= M; i++ ) 
	{
		memset(visited,false,sizeof(visited));
		if( augment(i) ) 
			match++;
	}

	return match;
}


void buildGraph()
{
	int i,j;
	v = N + M + 2;
	maxDis = -1;

	for( i = 1; i <= M; i++ )
	{
		for( j = M + 1; j < N + M + 1; j++ )
		{
			W[i][j] = sqrt((field[i].x - field[j].x) * (field[i].x - field[j].x) + (field[i].y - field[j].y) * (field[i].y - field[j].y) );
			if( maxDis < W[i][j] ) 
				maxDis = W[i][j];
		}
	}

}


int main()
{
	int i,K,T,caseno,m;
	double lo,hi,mid;
	
	//freopen("C:\\4.txt","rb",stdin);

	scanf("%d",&T);
	
	for( caseno = 1; caseno <= T; caseno++ )
	{
		scanf("%d %d %d",&M,&N,&K);

		for( i = 1; i <= M; i++ ) scanf("%lf %lf",&field[i].x,&field[i].y);
		for( i = M + 1; i < M + N + 1; i++ ) scanf("%lf %lf",&field[i].x,&field[i].y);

		printf("Case #%d:\n",caseno);
		if( M == K ) 
		{
			printf("0\n\n");
			continue;
		}


		buildGraph();
		
		m = MBM(maxDis);
		if( m < M - K ) 
		{
			printf("Too bad.\n\n");
			continue;
		}

		lo = 0,hi = maxDis;

		while( fabs(lo - hi) > 1e-7 )
		{
			mid = (lo + hi) / 2;
			m = MBM(mid);
			if( m >= M - K ) hi = mid;
			else lo = mid;
		}
		
		double mm = 1000.0;
		mid = (int)(mid * mm + 0.5) / mm;
		printf("%.3lf\n\n",mid);
	}

	return 0;
}

Any suggetions,I/O.....
plz hlp.

[fushar]

how if m = 0 or n = 0? What should be output? Too bad or 0.000?
Also how if m = k?
Those are too tricky for me. I've getting WA too many times...
Any help wanted........

[mf]

If m=0 or m=k or (n=0 and m=0), the answer is 0.000, of course.

[fushar]

Yeah, finally I managed to get AC
I just changed the binary search to work on the sorted distance array instead directly on distance.
Maybe previously I had floating point problems.
Anyway, thanx all for helping me...