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