AOJ 1237 - Shredding Company
- 問題
Shredding Company | Aizu Online Judge
- 概要
6桁以下の数が書かれた紙がある。それを切って、いくつかの整数を作る。その整数の和がt以下になるもので、最大になる切り方を求め、その整数の組合せとその和を出力せよ。
ただし特殊な例として、どんな切り方をしてもt以下になる組み合わせがなければ"error"、和の最大値を与える組合せがただ1つに定まらない場合は"rejected"と出力。
- アイデア
各桁の間を切る・切らないのbitloop。
あとはありがとうSTL。
- 実装(C++)
#include <algorithm> #include <cstdio> #include <cstdlib> #include <iostream> #include <string> #include <vector> using namespace std; int main(){ while(1){ int t; string num; cin >> t >> num; if(t==0 && num=="0") break; int now=0; int same_ct=0; int small=1000000; vector<int> ans; //カットするべき数の桁数 int len = num.size(); //各桁の間を切るか切らないかでbitloop for(int i=0; i<(1<<(len-1)); ++i){ vector<int> s; int st=0; //printf(" %2d:", i); for(int j=0; j<len-1; ++j){ if(i>>j & 1){ s.push_back(atoi(num.substr(st,j+1-st).c_str())); st=j+1; } } s.push_back(atoi(num.substr(st,len+1-st).c_str())); int tmp=0; for(int j=0; j<s.size(); ++j) tmp+=s[j]; //printf("%5d\n", tmp); small = min(small, tmp); if(t<tmp) continue; if(now<tmp){ ans.resize(s.size()); for(int j=0; j<s.size(); ++j) ans[j]=s[j]; now=tmp; same_ct=1; } else if(now==tmp) same_ct++; } //output if(small>t) printf("error\n"); else if(same_ct>1) printf("rejected\n"); else{ printf("%d", now); for(int i=0; i<ans.size(); ++i) printf(" %d", ans[i]); printf("\n"); } } }