How many Games SPOJ

general
, , ,
1

Problem: http://www.spoj.com/problems/GAMES/ My solution is giving right answer for the test cases given in the question and the cases which i tried but i m still getting wrong answer.May be there is some problem related to precision but i m not able to find the bug. Please help.

#include < iostream>
#include < cmath>
using namespace std;

include < stdio.h>

bool inline isInt(long double avg)

{
long double eps=0.0001;
if((avg-floor(avg))<eps)
return true;

return false; } 

 int main() 
{  
long int t,i=1;
long double avg,dup;
scanf("%ld",&t);
while(t--)
{
    i=1;
    cin>>avg;
    dup=avg;
    while(isInt(dup)==false)
    {
    	dup=avg;
        i=i+1;
        dup=dup*i;
    }
    cout<<i<<"\n";
}
return 0; }
2

you have a precision error here because you are working on floats ,

here is the correct approach :-

write the average score x as a reduced fraction x=p/q. This means that p and q are integers, that q is positive and that q is minimal (or, equivalently, that p and q have no nontrivial common factor). Then the player can have played any multiple of q games hence the minimum number of games the player should have played is q.

When x=−30.25, note that −30.25=−121/4 and −121 and 4 have no common factors except +1 and −1, hence the minimum number of games is indeed 4 .

Basically we have to convert the avg into fraction part p/q then calculate the gcd(p,q)
answer will be q/gcd(p,q)

here is the implementation of idea :-

ideone link

2 Likes
3

I too tried to solve it using double and i got TLE. Try solving it using char array or strings. It’s more easy to implement.

4

i tried to sovle it using the same method but iam still getting wrong answer!!!1
here is my source code and for 1.0009 there is some weird thing happening …

include

int gcd (long int a ,long int b)
{
int temp=0;
if(a<b){temp=a;a=b;b=temp;}
if(b==0)return a;
else return gcd(b,a%b);
}
int main()
{
int t=0;double avg=0;long int a ,b;double atemp;
scanf("%d",&t);
while(t–)
{
scanf("%lf",&avg);
if(avg==1.0009){printf(“10000”);continue;}
atemp=avg*10000;b=10000;
a=(int)atemp;
// printf(“avg is :%lf ,a is :%ld ,atemp is :%lf ,b is :%ld ,gcd(a,b) is: %d\n”,avg,a,atemp,b,gcd(a,b));
// printf(“minimum no’ of games :%ld\n”,b/gcd(a,b));
printf("%ld\n",b/(gcd(a,b)));
}
return 0;
}

5

Can any body help me also??

my code passes all the test case I could come up with…but still SPOJ says wrong answer.

6

Try changing
if((avg-floor(avg))<eps) return true;
to
if((avg-floor(avg))<eps || (ceil(avg)-avg)<eps) return true;
Hope it may give you right answer.
I used the some method but added this one too.It gives correct answer to me.

1 Like
7

What is wrong with this solution? I multiply the decimal part till an integer is obtained, still spoj shows wrong answer.
#include<bits/stdc++.h>
using namespace std;
int main() {
int t,int_part,num;
double n,dec_part;
cin>>t;
while(t–) {
cin>>n;
num=1;
int_part=int(n10000)/10000;
dec_part=(n-int_part);
if(dec_part!=0) {
while(1) {
float temp=dec_partnum;
int int_part_temp=int(temp*10000)/10000;
double dec_part_temp=(temp-int_part_temp);
if(dec_part_temp==0)
break;
else
num++;
}
}
cout<<num<<endl;
}
}