306902: CF1268A. Long Beautiful Integer
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Long Beautiful Integer
题意翻译
### 题目描述 给定一个由 $a_1, a_2, \ldots, a_n$ 从左到右构成的整数 $x$ 和一个正整数 $k$。 若由 $b_1, b_2, \ldots, b_m$ 从左到右构成的整数满足 $\forall i \in [1,m-k], b_i=b_{i+k}$,则称其为美丽数。 请求出最小的由 $b_1, b_2, \ldots, b_m$ 从左到右构成的美丽数 $y$,满足 $y \geq x$。 ### 输入格式 第一行两个整数 $n,k$,其中 $n$ 表示 $x$ 的位数,$k$ 的含义如题所述。 下一行包含由 $a_1, a_2, \ldots, a_n$ 从左到右构成的 $n$ 位整数 $x$,数据保证不包含前导零。 ### 输出格式 第一行输出一个整数 $m$,表示答案 $y$ 的位数。 下一行输出由 $b_1, b_2, \ldots, b_m$ 从左到右构成的 $m$ 位整数 $y$,不包含前导零。 ### 数据范围 $2 \leq n \leq 2 \times 10^5$,$1 \leq k \leq n$。题目描述
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. Also, you are given a positive integer $ k < n $ . 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 $ . You need to find the smallest beautiful integer $ y $ , such that $ y \geq x $ .输入输出格式
输入格式
The first line of input contains two integers $ n, k $ ( $ 2 \leq n \leq 200\,000, 1 \leq k < n $ ): the number of digits in $ x $ and $ k $ . 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 $ .
输出格式
In the first line print one integer $ m $ : the number of digits in $ y $ . 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 $ .
输入输出样例
输入样例 #1
3 2
353
输出样例 #1
3
353
输入样例 #2
4 2
1234
输出样例 #2
4
1313