11910 - Closest Fractions

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

Moderator: Board moderators

Post Reply
suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

11910 - Closest Fractions

Post by suneast » Sun Jan 30, 2011 5:45 am

hi, all :

for this problem, seems quite easy at first sight... :wink:

but I keep getting WA during the contest and don't know why

any tricks ?

thx in advance :D

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11910 - Closest Fractions

Post by suneast » Sun Jan 30, 2011 5:58 am

now , I got AC...
but still don't know why :o

I just change my reading to

Code: Select all

	scanf("%s",str);
	puts(str);
:D

happy coding~
Last edited by suneast on Tue Feb 08, 2011 8:24 am, edited 1 time in total.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11910 - Closest Fractions

Post by zobayer » Wed Feb 02, 2011 10:43 am

suneast wrote:now , I got AC...
but still don't know why :o

I just change my reading to

Code: Select all

	scanf("%s",&str);     ->     puts(str);
:D

happy coding~
Hmm, good that you've got AC, but, what does your post mean?
You were reading a string, then what & is doing here, and why you will change a scanf to a puts, shouldn't it be gets or something like that?
You should not always say what you know, but you should always know what you say.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11910 - Closest Fractions

Post by suneast » Wed Feb 02, 2011 12:25 pm

Oh, I’m so sorry zobayer…

Actually I mean that :
We should read the data using string format, to avoid float point precision error, then output what we have read. (I think this is the most important part in this problem :)

I do it like this:

double var;
char str[20];

scanf("%s",&str);
sscanf(str,"%lf",&var);
printf("Input : ");
puts(str);

instead of

scanf("%lf",&var);

Hope I am help to you…

Sorry for my thoughtless post before….

Happy coding~

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: 11910 - Closest Fractions

Post by shantanu18 » Wed Feb 02, 2011 10:01 pm

Why Runtime Error!!! :o

Code: Select all

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <sstream>
#define MAX 1024
#define eps 0.9000000000
#define min(a,b) (a<b? a:b)
//#define p 10
using namespace std;

struct node{
	int x;
	int y;
	double res;
};
bool com(const node a,const node b)
{
	return a.res < b.res;
}
int gcd(int a,int b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}

string toString(double value)
{
	int val=value;
	int cnt=0;
	while(val)
	{
		val=val/10;
		cnt++;
	}
	val=value*pow(10.0,(double)(9-cnt));
	stringstream ss;
	ss<<val;
	string st=ss.str();
	if(cnt)
		st.insert(st.begin()+cnt,'.');
	return st;
}
int main()
{
	//freopen("11910.txt","r",stdin);
	double value;
	while(scanf("%lf",&value)==1)
	{
		vector <node> vec;
		for(int i=2;i<MAX;i++)
		{
			for(int j=i-1;j>=1;j--)
			{
				if(gcd(i,j)==1)
				{
					double result = (double)((double)i/(double)j);
					if(fabs(result-value)<=eps )
					{
						node tmp;
						tmp.x=i;
						tmp.y=j;
						tmp.res=fabs(result-value);
						vec.push_back(tmp);
					}					
				}
			}
		}
		sort(vec.begin(),vec.end(),com);
		int length = min(2,vec.size()-1);
		printf("Input : ");
		cout<<toString(value)<<endl;
		for(int i=0;i<=length;i++)
		{
			double res = (double)((double)vec[i].x/(double)vec[i].y);
			printf("%5d : ",i+1);
			cout<<toString(res);
			printf(" =%6d / %-4d\n",vec[i].x,vec[i].y);
		}
	}
	return 0;
}


mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Re: 11910 - Closest Fractions

Post by mpi » Thu Feb 10, 2011 2:10 pm

Can somebody help me with this?
Here is some I/O from my WA program:

Input

Code: Select all

3.141592654
00000000001
1000.000000
999.9999999
-2.00000000
-0.11111111
0.000000000
123456789
984.12331
33.000000
Output

Code: Select all

Input : 3.141592654
    1 : 3.141592920 =  355 / 113
    2 : 3.141630901 =  732 / 233
    3 : 3.141552511 =  688 / 219
Input : 00000000001
    1 : 1.000000000 =    1 / 1
    2 : 0.999000000 =  999 / 1000
    3 : 0.998998999 =  998 / 999
Input : 1000.000000
    1 : 1000.000000 = 1000 / 1
    2 : 999.0000000 =  999 / 1
    3 : 998.0000000 =  998 / 1
Input : 999.9999999
    1 : 1000.000000 = 1000 / 1
    2 : 999.0000000 =  999 / 1
    3 : 998.0000000 =  998 / 1
Input : -2.00000000
    1 : 0.001000000 =    1 / 1000
    2 : 0.001001001 =    1 / 999
    3 : 0.001002004 =    1 / 998
Input : -0.11111111
    1 : 0.001000000 =    1 / 1000
    2 : 0.001001001 =    1 / 999
    3 : 0.001002004 =    1 / 998
Input : 0.000000000
    1 : 0.001000000 =    1 / 1000
    2 : 0.001001001 =    1 / 999
    3 : 0.001002004 =    1 / 998
Input : 123456789
    1 : 1000.000000 = 1000 / 1
    2 : 999.0000000 =  999 / 1
    3 : 998.0000000 =  998 / 1
Input : 984.12331
    1 : 984.0000000 =  984 / 1
    2 : 985.0000000 =  985 / 1
    3 : 983.0000000 =  983 / 1
Input : 33.000000
    1 : 33.00000000 =   33 / 1
    2 : 32.96666666 =  989 / 30
    3 : 33.03333333 =  991 / 30

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11910 - Closest Fractions

Post by suneast » Thu Feb 10, 2011 2:18 pm

mpi wrote: Hi, mpi
I think your data input is invalid. :(

because in the problem description :

Code: Select all

Each case contains one number on a line, each with exactly ten digits. 
but I will still print out the output from my accepted program

Code: Select all

Input : 3.141592654
    1 : 3.141592920 =  355 / 113
    2 : 3.141630901 =  732 / 233
    3 : 3.141552511 =  688 / 219
Input : 00000000001
    1 : 1.000000000 =    1 / 1
    2 : 0.999000000 =  999 / 1000
    3 : 0.998998999 =  998 / 999
Input : 1000.000000
    1 : 1000.000000 = 1000 / 1
    2 : 999.0000000 =  999 / 1
    3 : 998.0000000 =  998 / 1
Input : 999.9999999
    1 : 1000.000000 = 1000 / 1
    2 : 999.0000000 =  999 / 1
    3 : 998.0000000 =  998 / 1
Input : -2.00000000
    1 : 0.001000000 =    1 / 1000
    2 : 0.001001001 =    1 / 999
    3 : 0.001002004 =    1 / 998
Input : -0.11111111
    1 : 0.001000000 =    1 / 1000
    2 : 0.001001001 =    1 / 999
    3 : 0.001002004 =    1 / 998
Input : 0.000000000
    1 : 0.001000000 =    1 / 1000
    2 : 0.001001001 =    1 / 999
    3 : 0.001002004 =    1 / 998
Input : 123456789
    1 : 1000.000000 = 1000 / 1
    2 : 999.0000000 =  999 / 1
    3 : 998.0000000 =  998 / 1
Input : 984.12331
    1 : 984.0000000 =  984 / 1
    2 : 985.0000000 =  985 / 1
    3 : 983.0000000 =  983 / 1
Input : 33.000000
    1 : 33.00000000 =   33 / 1
    2 : 32.96666667 =  989 / 30
    3 : 33.03333333 =  991 / 30
Hope I'm help to you...
happy coding~ :D

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Re: 11910 - Closest Fractions

Post by mpi » Thu Feb 10, 2011 2:48 pm

Seriously, man, I hate these precision problems :evil:
Thank you, suneast. Got AC after printing doubles properly.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 11910 - Closest Fractions

Post by howardcheng » Wed Apr 27, 2011 6:41 pm

Any hints? My code appears to pass all the cases posted here, and I am reading/printing the input as a string. Are there more tricky cases?

Post Reply

Return to “Volume 119 (11900-11999)”