SRM 356 250pt : AverageProblem
問題概要
小数点3桁目以降が切り捨てられた小数が与えられる。考えられる分母の最小数を求める問題。
解法
まず、1000が上限であることが分かる。なので、あとは分母を全探索する。分母を決めれば、分子は[1..分母]まで全部試して、入力を全部カバーするかどうか見ればよい。計算量1000*1000くらい。
もちろん浮動小数点の扱いとか誤差が面倒なので、整数に直して処理する。
もちろん、切り捨てでなくて四捨五入の場合でも同じように解ける。
#include <algorithm> #include <vector> #include <string> #include <sstream> #include <cstdio> using namespace std; struct AverageProblem { int numberOfParticipants(vector <string> marks) { vector<int> ss; for(int i=0; i<(int)marks.size(); i++){ stringstream s(marks[i]); string t; while(s>>t){ if((int)t.length()==6){ ss.push_back(10000); } else{ ss.push_back((t[0]-'0')*1000+atoi(t.substr(2).c_str())); } } } sort(ss.begin(), ss.end()); ss.erase(unique(ss.begin(), ss.end()), ss.end()); for(int i=1; i<=1000; i++){ vector<int> tmp; for(int j=0; j<=i*10; j++){ int k = ((1000*j)/i); tmp.push_back(k); } // sort(tmp.begin(), tmp.end()); if(includes(tmp.begin(), tmp.end(), ss.begin(), ss.end())){ return i; } } return -1; } };