BestApproximationDiv1.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#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 <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int) b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i>=loop_ends_here; i--)

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)


class BestApproximationDiv1
{
public:
	string findFraction(int maxDen, string num)
	{
		int a = 0, b = 1, mx = 1;
		ST s = "123456";
		char ch[111] = {0};

		forab(d, 1, maxDen) {
			forab(n, 0, d) {
//				double div = (int)(1.0*n/d*1000000);
//				div /= 1000000;
//				sprintf(ch, "%0.6lf", div);
				sprintf(ch, "0.%6lld", 1000000ll*n/d);

				int cnt = 1;
				forab(i, 2, 7) {
					if(num[i] == ch[i])
						cnt++;
					else
						break;
				}
				if(cnt > mx) {
					a = n, b = d;
					mx = cnt;
				}
//				printf("%d/%d = %lf = %s, cnt = %d\n", n, d, 1.0*n/d, ch, cnt);
			}
		}
		cout << a << "/" << b << endl;

		SS ss;
		ss << a << "/" << b  << " has " << mx << " exact digits";

		return ss.str();
	}
};

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, int p0, string p1, bool hasAnswer, string p2) {
	cout << "Test " << testNum << ": [" << p0 << "," << "\"" << p1 << "\"";
	cout << "]" << endl;
	BestApproximationDiv1 *obj;
	string answer;
	obj = new BestApproximationDiv1();
	clock_t startTime = clock();
	answer = obj->findFraction(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << "\"" << p2 << "\"" << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << "\"" << answer << "\"" << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	int p0;
	string p1;
	string p2;
	
	{
	// ----- test 0 -----
	p0 = 115;
	p1 = "0.141592";
	p2 = "16/113 has 7 exact digits";
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Elly is not a big fan of mathematical constants.  Most of them are infinite, and therefore hard to memorize.  Fractions, on the other hand, are often easier to remember and can provide good approximations.  For example, 22/7 = 3.1428... is one way to approximate Pi.  Unfortunately, it's only accurate to 2 places after the decimal point, so it doesn't help at all.  A slightly better example is 355/113 = 3.14159292... which is correct up to 6 digits after the decimal point.
// 
// Elly understands that working with infinite decimal fractions is going to be very difficult, so she first wants to find a good way to approximate floating point numbers with decimal representations that are finite.  Your task is to help her in this mission.  You will be given a string number containing the decimal representation of a non-negative fraction strictly less than 1. There will be exactly 6 digits after the decimal point in number (trailing zeros are possible and significant).  More precisely, number will be formatted "0.dddddd" (quotes for clarity) where each d is a decimal digit ('0'-'9').
// 
// Given a fraction F = A/B, where 0 <= A < B, its quality of approximation with respect to number is calculated as follows:
// 
// 
// Let S be the decimal fraction (infinite or finite) representation of F.
// If S is infinite or the number of digits after the decimal point in S is greater than 6, only consider the first 6 decimals after the decimal point in S.  Truncate the rest of the digits without performing any kind of rounding.
// If the number of digits after the decimal point in S is less than 6, append trailing zeroes to the right side until there are exactly 6 digits after the decimal point.
// The quality of approximation is the number of digits in the longest common prefix of S and number.  The longest common prefix of two numbers is the longest string which is a prefix of the decimal representations of both numbers with no extra leading zeroes.  For example, "3.14" is the longest common prefix of 3.1428 and 3.1415.
// 
// 
// Elly doesn't like long approximations either, so you are only allowed to use fractions where the denominator is less than or equal to maxDen.  Find an approximation F = A/B of number such that 1 <= B <= maxDen, 0 <= A < B, and the quality of approximation is maximized.  Return a string formatted "A/B has X exact digits" (quotes for clarity) where A/B is the approximation you have found and X is its quality.  If there are several such approximations, choose the one with the smallest denominator among all of them.  If there is still a tie, choose the one among those with the smallest numerator.
// 
// 
// DEFINITION
// Class:BestApproximationDiv1
// Method:findFraction
// Parameters:int, string
// Returns:string
// Method signature:string findFraction(int maxDen, string number)
// 
// 
// CONSTRAINTS
// -maxDen will be between 1 and 1000, inclusive.
// -number will contain exactly 8 characters.
// -number will consist of a digit '0', followed by a period ('.'), followed by exactly six digits ('0'-'9').
// 
// 
// EXAMPLES
// 
// 0)
// 42
// "0.141592"
// 
// Returns: "1/7 has 3 exact digits"
// 
// 3 plus the current approximation yields an approximation of Pi.
// 
// 1)
// 3
// "0.133700"
// 
// Returns: "0/1 has 1 exact digits"
// 
// Not a lot of options here.
// 
// 2)
// 1000
// "0.123456"
// 
// Returns: "10/81 has 7 exact digits"
// 
// 
// 
// 3)
// 1000
// "0.420000"
// 
// Returns: "21/50 has 7 exact digits"
// 
// This one can be represented in more than one way. Be sure to choose the one with the lowest denominator.
// 
// 4)
// 100
// "0.909999"
// 
// Returns: "10/11 has 4 exact digits"
// 
// Even though 91/100 is a much closer approximation, 10/11 matches up to 3 digits, and 91/100 only to one.
// 
// 5)
// 115
// "0.141592"
// 
// Returns: "16/113 has 7 exact digits"
// 
// A better approximation for the decimal part of Pi.
// 
// END KAWIGIEDIT TESTING




//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!