公式

B - 200th ABC-200 解説 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\).

投稿日時:
最終更新: