AOJ1237 Shredding Company

問題リンク Shredding Company

• 概要

ターゲットとなる整数tと印字された整数numが与えられる。numを任意の場所でカットし、できた断片に書かれている数字の総和を考えたとき、tを超えずに最大となるものを求め、更にそれを実現するカットを答えよ。
どのようにカットしてもtを超えてしまう場合はerror, 最大となるカット方法が2つ以上ある場合はrejectedと答えよ。
t, numは最大6ケタ

• 解法

numは6ケタまでしかないのでカットする個所は最大でも5か所です。それぞれについて、カットする,しないを全通り試します。2^5しかないので計算量の心配は何もないです。

• ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Shredding Company
public class AOJ1237 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int t = sc.nextInt();
			String s = sc.next();
			if(t==0&&"0".equals(s))break;
			int max = -1;
			List<String> piece = new ArrayList<String>();
			boolean col = false;
			int n = s.length()-1;
			for(int i=0;i<1<<n;i++){
				int p = 0;
				int sum = 0;
				List<String> sub = new ArrayList<String>();
				for(int j=0;j<n;j++){
					if((i>>j&1)==0)continue;
					String u = s.substring(p, j+1);
					sub.add(u);
					sum += Integer.parseInt(u);
					p = j+1;
				}
				sub.add(s.substring(p));
				sum += Integer.parseInt(s.substring(p));
				if(sum<=t&&max<sum){
					max = sum; col = false; piece = sub;
				}
				else if(sum==max){
					col = true;
				}
			}
			if(max==-1)System.out.println("error");
			else if(col)System.out.println("rejected");
			else{
				System.out.print(max+" ");
				for(int i=0;i<piece.size();i++)System.out.print(piece.get(i)+(i==piece.size()-1?"\n":" "));
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1237().run();
	}
}