10804 - Gopher Strategy

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

Moderator: Board moderators

nano72
New poster
Posts: 10
Joined: Tue Sep 05, 2006 5:25 pm

Double type rounding

Post by nano72 » Tue Sep 05, 2006 5:35 pm

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Sep 05, 2006 6:25 pm

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.
If only I had as much free time as I did in college...

nano72
New poster
Posts: 10
Joined: Tue Sep 05, 2006 5:25 pm

Post by nano72 » Tue Sep 05, 2006 7:09 pm

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Sep 05, 2006 8:38 pm

change 0.01 to 2.
If only I had as much free time as I did in college...

nano72
New poster
Posts: 10
Joined: Tue Sep 05, 2006 5:25 pm

Post by nano72 » Wed Sep 06, 2006 11:13 am

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
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Fri Sep 22, 2006 10:50 pm

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.. :x
Sleep enough after death, it is the time to work.
Mostafa Saad

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

So many WA's in this prob

Post by shihabrc » Mon Feb 05, 2007 11:00 pm

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.
Shihab
CSE,BUET

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: 10804 - Gopher Strategy

Post by fushar » Fri Apr 03, 2009 12:11 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10804 - Gopher Strategy

Post by mf » Sat Apr 04, 2009 12:22 am

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

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: 10804 - Gopher Strategy

Post by fushar » Sat Apr 04, 2009 3:00 pm

Yeah, finally I managed to get AC :D
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...

Post Reply

Return to “Volume 108 (10800-10899)”