1237 - Shredding Company

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1237

問題

数字とtargetが与えられる。
数字を分割してその和がtargetを超えないで最大となる分割の仕方を出力する。
そのような分割の仕方が2つ以上ある時はrejected。
どのように分割してもtargetを超えてしまう時はerror。

解法

数字の桁が6桁以下という事なので分割方法を全探索。
分割の仕方は、数字の間に仕切りを入れる事を考えればbit集合で列挙する事が出来る。
数字は文字列で管理した。

ソース

int main() {
  int t;
  string num;
  while(cin >> t >> num, t||num!="0") {
    int n = num.size();
    vector<string> ansv;
    int ans = 0;
    bool reject = 0;
    REP(S, 1<<(n-1)) {
      int last = 0;
      vector<string> v;
      REP(i, n-1) {
        if (S>>i & 1) {
          v.push_back(num.substr(last, i-last+1));
          last = i+1;
        }
      }
      v.push_back(num.substr(last));
      int sum = 0;
      FOR(it, v)
        sum += atoi(it->c_str());
      if (sum > ans && sum <= t) {
        ans = sum;
        ansv = v;
        reject = 0;
      } else if (sum == ans) {
        reject = 1;
      }
    }
    if (reject) {
      cout << "rejected" <<endl;
    } else if (ans == 0) {
      cout << "error" << endl;
    } else {
      cout << ans;
      FOR(it, ansv) {
        cout << " " << *it;
      }
      cout << endl;
    }
  }
}