TopCoder SRM 616 Div2 Medium ColorfulCoinsEasy

Div2 mediumはDiv1 Mediumを簡単にした問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13094

問題

この国にはN種類の異なる色のコインがあり、その価値が与えられる。
当然ながら、各コインの価値は互いに整数倍/約数の関係にある。

初期状態でどんな色のコインがあるかわからず、コインの色と価値の対応もわからないとする。

ここで、ある金額を指定すると、その金額を最小のコイン枚数で引き出せるATMがある。
このATMを1回使い、どのコイン色がどの価値に対応するか求められるか答えよ。

解法

価値pのコインの次の価値のコインがk*pとする。
ATMに指定する金額をXとすると、(X/p)%k枚だけこのコインが出てくる。

各コインと価値の対応を1発で求めるには、ある価値のコインが1枚、他のコインが2枚、また別のコインが3枚…と異なる枚数が出てくるような金額を入れればよい。
ただし各コインの枚数は1～(k-1)の間でなければならない。
(初期状態でどんな色のコインがあるか不明のため、最低1枚は出してみないといけない)

最大価値のコインは、無限に大きな金額を指定すれば大量にそのコインが出てくる。
それ以外のコインについて、以下の処理を行えばよい。

• 次の価値のコインとの比からkを求め、そのコインを出せる最大枚数(k-1)を計算する。
• 上記(k-1)を小さい順にソートし、1-indexでi番目の値がi以上であれば求められる。そうでなければ求められない。

class ColorfulCoinsEasy {
	public:
	string isPossible(vector <int> values) {
		int i;
		vector<ll> V;
		FOR(i,values.size()-1) V.push_back(values[i+1]/values[i]);
		sort(V.begin(),V.end());
		FOR(i,V.size()) if(i>=V[i]-1) return "Impossible";
		return "Possible";
	}
};

まとめ

先にDiv1 Mediumを解いていたので簡単。