SRM606 div2 med EllysNumberGuessing
TopCoder Statistics - Match Overview
問題概要
- Aさんが1以上1000000000以下の数字を思い浮かべる
- BさんがAさんが思い浮かべた数字がx1,x2,...,xnかどうか聞く
- Aさんは思い浮かべた数字とxとの差の絶対値yを答える
- Aさんが思い浮かべた数字が一意に定まる時はその答えを、複数考えられる場合は-1、矛盾する場合は-2を答えよ
制約
- n ≦ 50
- Aさんが思い浮かべる数字は1以上1000000000以下
解説
思い浮かべた数字の候補はxi±yiである。
map[候補となる数字] := 回答より候補となった回数とする。
候補となる数字は1以上1000000000以下であることに注意。
map == nとなる数字が1つだけならそれが答え、2つあるなら-1、1つもないなら-2。
コード
class EllysNumberGuessing { public: int getNumber(vector <int> guesses, vector <int> answers) { int n = answers.size(); map<int, int> MAP; FOR(i,0,n) { int c = guesses[i] + answers[i]; int d = guesses[i] - answers[i]; MAP[c]++; if(c != d) MAP[d]++; } int cnt = 0; int ret = 0; for(auto m : MAP) { if(m.second == n && m.first > 0 && m.first <= 1e9) { cnt++; ret = m.first; } } if(cnt == 0) return -2; else if(cnt == 1) return ret; else return -1; } };