はじめに

問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1237
ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1370964
Javaで実装
実装量も難易度も低めな気がする

問題文概訳

あなたはシュレッディングカンパニーの新しいシュレッダー開発担当になった。「普通の」シュレッダーは神を小さいクズに裁断するだけだが、この新しいシュレッダーは以下の普通てない特徴をもっている。

シュレッダーに数値を入力する、その後、数字が書かれた紙を入れる。
シュレッダーは紙を裁断する。この時、1欠片の紙には数字が1つ以上書かれている状態になる。
それぞれの紙片に書かれた数の合計が、シュレッダーに入力された数値を超えない範囲で最も近い数字になる。

例えば、50を入力して、12346と書かれた紙を入れると、シュレッダーは1, 2, 34, 6 と裁断する。この場合合計は43となり、これが50を超えない中で最も大きくなる。一方で、12, 34, 6 裁断すると52となり50には近いが、50を超えてしまっているのでこれはだめである。

加えて、以下の3つの点に注意して欲しい

もし入力された数値と紙に書かれた数字が同じ場合、紙は裁断されない。
もし合計がどうしても入力された数値を超える場合、ディスプレイには「eror」と表示される。
分け方が複数考えられる場合、たとえば、入力された数値が15で、紙に111と書かれていた場合。分け方は 1, 11 と 11, 1 の2通りが可能である。この場合は「rejected」と画面に表示される。

紙に書いてある数値は、0が最初になることはない。例えば、123と書かれた紙はあり得るが、0123と書かれた紙はありえない。また、桁数は最大6桁である。

（訳注: tの大きさについて書かれていない…？）

方針

非常に簡単で、各数字と数字の間の部分について、そこで切るか切らないかの2択を全探索していくだけ。実装を見たほうがわかりやすいかもしれない。

実装

分けた数字を出力するのに String を使っているが、ここで StringBuffer を使うと、Javaの関数が参照渡しなので結構面倒なことになる。

class Main extends MyUtil{ public static void main(String args) throws Exception{ while (true) { // 入力は独自クラスを使っている int in = readIntMap(); if(in[0] + in[1] == 0) break; cnt = 0; max = 0; check(10, in[0], in[1], 0, ""); if(cnt == 0){ System.out.println("error"); }else if (cnt > 1){ System.out.println("rejected"); }else{ System.out.println(max + " " + ans); } } }

static int cnt = 0;
static int max = 0;
static String ans = "";
static void check(int i, int t, int num, int sum, String buf){
    if(num < i){
        sum += num;
        buf = num + buf;
        if(max < sum && sum <= t){
            max = sum;
            ans = buf;
            cnt = 1;
        }else if(max == sum){
            cnt++;
        }
        return;
    }

    // iで分断しない場合
    check(i*10, t, num, sum, buf);

    // iで分断する場合
    int next_num = num / i;
    int bundan = num % i;
    int next_sum = sum + bundan;
    check(10, t, next_num, next_sum, " " + bundan + buf);
}

}