Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/09/28

SRM 483 BestApproximationDiv1

| 00:55

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11023&cr=22851423

問題

与えられた数より小さい分母を持つ分数の中から,与えられた 1 より小さい小数点以下6桁の小数を最もよく近似する分数を見つける問題.

アプローチ

分母を小さい値から固定していき,分子を近似対象の小数と分母の掛け算で決定.誤差があるので分子は floor と ceil の両方を計算する.

本番では Failed System Test だった.理由は作った分数の小数表現を sprintf("%.8f") で作ったから.sprintf は指定桁数以下の値を四捨五入してしまうので小数点以下7桁目以降が 995 より大きいテストケースだと失敗する."%.10f" で失敗するケースは無かった模様.

Test Case: 138
Args: {1000, "0.812983"}
Expected: "313/385 has 6 exact digits"
Received: "526/647 has 7 exact digits"

こうした誤差を最初から出さないためには 10^6 倍して整数として計算するのがよい.問題はこの方法でも int の範囲内で計算できるように設計されているようだ.

*

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

#define For(i,a,b)    for(int i=(a);i<(b);++i)

string findFraction(int maxDen, string number)
{
	int ml = 0;
	int mn = 0;
	int md = 0;
	int num = toi(number.c_str()+2);
	
	For(d,1,maxDen+1) For(dd,0,2)
	{
		int n = num*d;
		n -= n%1000000;
		n += dd*1000000;
		int x = n/d;
		int y = 100000;
		int l = 1;
		For(i,0,6)
		{
			if(x/y!=num/y) break;
			l++;
			y /= 10;
		}
		if(l>ml)
		{
			mn = n/1000000;
			md = d;
			ml = l;
		}
	}
	
	char s[64];
	sprintf(s, "%d/%d has %d exact digits", mn, md, ml);
	
	return string(s);
}

ttvijfyomttvijfyom2011/02/27 18:44XXnJye <a href="http://idnbvnetymog.com/">idnbvnetymog</a>, [url=http://ftuabcqbiduw.com/]ftuabcqbiduw[/url], [link=http://gwxepxsaficy.com/]gwxepxsaficy[/link], http://judtzquinqwh.com/