解いた問題

2/14/2012

SRM485 Div1 Easy

250
最初の2つを決め打ちする。
bool lex_cmp(vector<lli> v, vector<lli> u)
{
  for (int i = 0; i < v.size(); ++i) {
    if (v[i] != u[i]) return v[i] > u[i];
  }
  return false;
}

class AfraidOfEven {
public:
  vector <int> restoreProgression(vector <int> seq_)
  {
    const int size = seq_.size();

    vector<lli> seq;
    for (int i = 0; i < size; ++i) {
      seq.push_back(seq_[i]);
    }

    vector< vector<lli> > vs;

    for (int p1 = 0; p1 < 32; ++p1) {
      for (int p2 = 0; p2 < 32; ++p2) {       
        vector<lli> v;
        v.push_back(seq[0] * (1LL << p1));
        v.push_back(seq[1] * (1LL << p2));
        lli diff = v[1] - v[0];
        for (int i = 2; i < size; ++i) {
          v.push_back(v.back() + diff);
        }
        bool flg = true;
        for (int i = 0; i < size; ++i) {
          lli n = v[i];
          while (seq[i] < n && n % 2 == 0) n = n / 2LL;
          flg = flg && (n == seq[i]);
        }
        if (flg && *max_element(v.begin(), v.end()) <= (lli)INT_MAX) vs.push_back(v);
      }
    }

    vector<lli> r = vs[0];
    for (int i = 0; i < vs.size(); ++i) {
      if (lex_cmp(r, vs[i])) r = vs[i];
    }

    for (int i = 0; i < size; ++i) {
      seq_[i] = r[i];
    }

    return seq_;
  }
};

0 件のコメント :

コメントを投稿