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;
	}

};