## 11910 - Closest Fractions

Moderator: Board moderators

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

### 11910 - Closest Fractions

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
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 11910 - Closest Fractions

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~
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
Contact:

### Re: 11910 - Closest Fractions

suneast wrote: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?
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

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;

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

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

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
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

### Re: 11910 - Closest Fractions

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

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~ mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

### Re: 11910 - Closest Fractions

Seriously, man, I hate these precision problems 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

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?