## B - 200th ABC-200 Editorial by en_translator

One way of implementation to get accepted is to repeat the following operations \(K\) times: divide \(N\) by \(200\) if \(N\) is currently a multiple of \(200\), or otherwise convert \(N\) to a string, append a string `200`

, and then convert it back to an integer type.

The answer does not fit in a \(32\)-bit integer, but it does fit in a \(64\)-bit integer. The reason will be explained later.

Sample code in 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;
```

However, in some language it is a bother to transfer between string type and integer type back and forth. Instead, one can simplify it as follows:

An operation of appending `200`

can be substituted by multiplying the integer by \(1000\) and then add \(200\).

For example, when appending `200`

to \(1234\), one can multiply \(1234\) by \(1000\) to obtain \(1234000\), and then add \(200\) to it to obtain \(1234200\).

This method enables to handle only integers and simplifies implementation.

Sample code in 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);
}
```

By the way, what is the maximum possible value of the answer?

In fact, an integer \(X\) followed by \(200\) is \(1000 \times X + 200\), which is always a multiple of \(200\). That is, the operation right after that of appending `200`

is always that of dividing by \(200\).

As a result of these consecutive two operations, \(X\) becomes \(5 \times X + 1\).

Therefore, even after \(20\) application of the operations to the original integer \(N\), it becomes at most \(5^{10} \approx 10^7\) times larger.
Actually, we may skip the operation of dividing by \(200\) at last, so it becomes at most \(2 \times 10^9\) times as large as the original integer.

Strictly, the maximum solution is \(195311035156200 \approx 1.95 \times 10^{14}\) when \(N=99999\) and \(K=19\).

posted:

last update: