Contest Duration: - (local time) (100 minutes) Back to Home

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: