11910 - Closest Fractions

[suneast]

hi, all :

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

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

any tricks ?

thx in advance

[suneast]

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

I just change my reading to

Code: Select all

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

happy coding~

[zobayer]

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

I just change my reading to

Code: Select all

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

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?

[suneast]

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]

Why Runtime Error!!!

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]

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]

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~

[mpi]

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

[howardcheng]

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?