問題
http://community.topcoder.com/stat?c=problem_statement&pm=11023&rd=14236
ある小数が与えられる。
この小数と、接頭辞が最も多く一致する、分母がmaxDen以下の分数と
それが何桁一致するかを求める。
そのような分数が複数存在する場合は、最も分母が小さいもの、
分母が一緒であれば分子が最も小さいものを求める。
解き方
分母の数が１０００なのでO(10^6)となり、全探索で求められる。
コード
class BestApproximationDiv1 {
public:
int calc(string s1,string s2){
int ret=1;
FORE(i,0,s1.size()){
if(s1[i]==s2[i])ret++;
else break;
}
return ret;
}
string findFraction(int maxDen, string number) {
int a=1000,b=1000,score=-1;
for(int i=1;i<=maxDen;i++)for(int j=0;j<i;j++){
int x=(int)(1000000.0*j/i);
stringstream out;
string str;
out<<x;
out>>str;
while(str.size()<6)str='0'+str;
int tmp=calc(str,number.substr(2));
if(tmp>score){
a=j,b=i,score=tmp;
}
}
char ch[100];
sprintf(ch,"%d/%d has %d exact digits",a,b,score);
return ch;
}
};
public:
int calc(string s1,string s2){
int ret=1;
FORE(i,0,s1.size()){
if(s1[i]==s2[i])ret++;
else break;
}
return ret;
}
string findFraction(int maxDen, string number) {
int a=1000,b=1000,score=-1;
for(int i=1;i<=maxDen;i++)for(int j=0;j<i;j++){
int x=(int)(1000000.0*j/i);
stringstream out;
string str;
out<<x;
out>>str;
while(str.size()<6)str='0'+str;
int tmp=calc(str,number.substr(2));
if(tmp>score){
a=j,b=i,score=tmp;
}
}
char ch[100];
sprintf(ch,"%d/%d has %d exact digits",a,b,score);
return ch;
}
};