読者です 読者をやめる 読者になる 読者になる

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

AOJ 1237: Shredding Company

はじめに

問題文概訳

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

  • シュレッダーに数値を入力する、その後、数字が書かれた紙を入れる。
  • シュレッダーは紙を裁断する。この時、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位をとる。

f:id:yoshiki_utakata:20150528160905p:plain