Spoj(GAMES) – HOW MANY GAMES

Brute force will give you TLE even though it will pass initial test cases.

The logic behind this problem is to represent the average score x in the form of a/b where b is minimum.

We know x=a/b . First let us bring x in the form of a/b by multiplying x with pow(10,number of digits after decimal point)

Example: x=30.25 Here we multiply x with pow(10,2) so now a=3025 and b=100

Now we have to reduce the fraction a/b to its least form.

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

Similarly 3025/100=121*25/4*25=121/4

Now we find gcd(a,b) which is nothing but gcd(x*pow(10,numberOfDigitsAfterDecimalPoint),pow(10,numberOfDigitsAfterDecimalPoint))

FInally answer is b/gcd(a,b)

Where b = pow(10,numberOfDigitsAfterDecimalPoint)

a = x*pow(10,numberOfDigitsAfterDecimalPoint)

So ans for average score x=30.25 is 100/gcd(3025,100)=100/25=4

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	int gcd(int a,int b){
	if(a<b)
	return gcd(b,a);
	if(b==0)
	return a;
	return gcd(b,a%b);
	}
	int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	string str;
	cin>>str;
	int len=str.length();
	int c=0;
	int decimalPointFlag=0;
	for(int i=len-1;i>=0;i--){
	if(str[i]=='.'){
	decimalPointFlag=1;
	break;
	}
	else{
	c++;
	}
	}
	int power=0;
	int number=0;
	int numerator;
	if(decimalPointFlag){
	for(int i=0;i<len;i++){
	if(str[i]!='.'){
	number=number*10+str[i]-'0';
	}
	}
	power=pow(10,c);
	numerator=number;
	printf("%d\n",power/gcd(numerator,power));
	}
	else{
	printf("1\n");
	}
	}
	}

view raw GAMES.cpp hosted with ❤ by GitHub