codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1268A.md (1140B)


      1 Source: https://codeforces.com/problemset/problem/1268/A
      2 
      3 A. Long Beautiful Integer
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an integer $x$ of $n$ digits $a_1, a_2, \ldots, a_n$, which make up its decimal notation in order from left to right.
     22 
     23 Also, you are given a positive integer $k \lt n$.
     24 
     25 Let's call integer $b_1, b_2, \ldots, b_m$ beautiful if $b_i = b_{i+k}$ for each $i$, such that $1 \leq i \leq m - k$.
     26 
     27 You need to find the smallest beautiful integer $y$, such that $y \geq x$.
     28 
     29 Input
     30 
     31 The first line of input contains two integers $n, k$ ($2 \leq n \leq 200\,000, 1 \leq k \lt n$): the number of digits in $x$ and $k$.
     32 
     33 The next line of input contains $n$ digits $a_1, a_2, \ldots, a_n$ ($a_1 \neq 0$, $0 \leq a_i \leq 9$): digits of $x$.
     34 
     35 Output
     36 
     37 In the first line print one integer $m$: the number of digits in $y$.
     38 
     39 In the next line print $m$ digits $b_1, b_2, \ldots, b_m$ ($b_1 \neq 0$, $0 \leq b_i \leq 9$): digits of $y$.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3 2
     47 353
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3
     54 353
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 4 2
     61 1234
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 4
     68 1313
     69 ```