はじめに
- 問題: 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);
}
}
おまけ
何故か Java の Time で1位をとる。
