ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1237 Shredding Company

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1237

シュレッターに数字が書かれた紙を入れバラバラにします。
それらの紙に書かれた数字を足し合わせてtarget number以下の最大値を求める問題です。

・解法
全探索+枝刈りで解くことができます。

最初にnumから作ることのできる値を全て列挙させてから探索すればよいです。


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
 
int target,digit,ans;
vector<int> comb;
vector<int> num[6];
bool rejected,error;
 
int convert(string s){
  int val = 0;
  rep(i,s.size()){
    val = 10*val + (int)(s[i] - '0');
  }
  return val;
}
 
void dfs(int sum, int idx, vector<int> select){
  if(target < sum) return;
  else if(idx==digit){
    error = false;
    if(ans < sum){
      rejected = false;
      ans = sum;
      comb = select;
    }
    else if(ans==sum) rejected = true;
  }
  else{
    for(int j = 0 ; j < num[idx].size() ; j++){
      vector<int> tmp = select;
      tmp.push_back(num[idx][j]);
      dfs(sum+num[idx][j], idx+j+1, tmp);
    }
  }
}
 
int main(){
  string tmp;
  while(cin >> target >> tmp){
    if(target==0 && tmp=="0") break;
    ans = -1;
    error = true;
    rejected = false;
    comb.clear();
    rep(i,6) num[i].clear();
    digit = tmp.size();
     
    if(target==convert(tmp)){
      cout << target << " " << target << endl;
      continue;
    }
 
    for(int i = 0 ; i < digit ; i++){
      for(int j = 0 ; i+j < digit ; j++){
        //if(tmp[i]=='0' && j!=0) break;
        num[i].push_back(convert(tmp.substr(i,j+1)));
      }
    }
     
    dfs(0,0,vector<int>());
    if(rejected) puts("rejected");
    else if(error) puts("error");
    else{
      cout << ans;
      rep(i,comb.size()){
        cout << " " << comb[i];
      }
      cout << endl;
    }
  }
  return 0;
}