Official

B - 200th ABC-200 Editorial by physics0523


ひとつの実装方針として、もし \(N\) が現在 \(200\) の倍数であれば \(200\) で割り、そうでなければ \(N\) を文字列型に変換した上で後ろに文字列 200 を連結し、また整数型に戻すという操作を \(K\) 回行うことによって、この問題に正解することができます。
答えは \(32\) bit整数型には収まりませんが、 \(64\) bit整数型に収まります。この理由は後ほど説明します。

Perlによる実装例:

use bigint;

$input = <STDIN>;
chomp $input;
my ($n, $k) = split (/ /, $input);

for my $i(0..$k-1){
  if($n%200==0){$n/=200;}
  else{$n=$n."200";}
}

print $n;

しかし、言語によっては文字列型と整数型を行き来することは非常に手間となります。そこで、以下のような工夫をすることが可能です。
後ろに 200 を付ける操作を、整数を \(1000\) 倍して \(200\) を足すという操作に置き換えることができます。
例えば、 \(1234\) の後ろに 200 を付ける場合、まず \(1234\)\(1000\) 倍して \(1234000\) とし、ここに \(200\) を足して \(1234200\) とします。
これにより、全ての処理が整数型で完結し、簡潔な実装となります。

Rustによる実装例:

use proconio::input;

fn main(){
    input!{
        mut n: i64,
        k: i32,
    }
    
    for i in 0..k{
        if n%200==0 {
            n/=200;
        }
        else{
            n=1000*n+200;
        }
    }
    println!("{}",n);
}

ところで、答えの値は、最大でどの程度になるでしょうか?
実は、ある整数 \(X\) の末尾に 200 を付けた整数は \(1000 \times X + 200\) であり、これは必ず \(200\) の倍数です。つまり、後ろに 200 を付ける操作の次の操作は、必ず \(200\) で割る操作となります。
結局、この連続する \(2\) 回の操作を通して、 \(X\)\(5 \times X + 1\) となります。

よって、元の整数 \(N\)\(20\) 回操作をかけても、 \(N\)\(5^{10} \approx 10^7\) 倍程度にしかなりません。 実際には、最後に \(200\) で割る操作が入らない場合があるので、最大で元の整数の \(2 \times 10^9\) 倍程度の値をとることになります。
厳密な解の最大値は、\(N=99999,K=19\) の場合の \(195311035156200 \approx 1.95 \times 10^{14}\) です。

posted:
last update: