Số đẹp dài nhỏ nhất

Điểm: 5,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho số nguyên dương $x$ gồm $n$ chữ số $a_{1}, a_{2}, \dots, a_{n}$ (đọc từ trái sang phải trong biểu diễn thập phân) và một số nguyên dương $k < n$ .

Một số nguyên dương $b_{1}, b_{2}, \dots, b_{m}$ được gọi là đẹp nếu $b_{i} = b_{i + k}$ với mọi $i$ thỏa $1 \leq i \leq m - k$ .

Hãy tìm số đẹp $y$ nhỏ nhất thỏa $y \geq x$ .

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $k$ .
Dòng thứ hai: $n$ chữ số $a_{1}, a_{2}, \dots, a_{n}$ tạo thành $x$ , với $a_{1} \neq 0$ .

Dữ liệu ra

Dòng đầu: số nguyên $m$ — số chữ số của $y$ .
Dòng thứ hai: $m$ chữ số $b_{1}, b_{2}, \dots, b_{m}$ tạo thành $y$ , với $b_{1} \neq 0$ .

Ràng buộc

$2 \leq n \leq 200 000$
$1 \leq k < n$
$0 \leq a_{i} \leq 9$ , $a_{1} \neq 0$

Ví dụ

Input	Output	Giải thích
3 2 353	3 353	$x = 353$ đã thỏa $b_{1} = b_{3}$ , nên $y = 353$ .
4 2 1234	4 1313	Số đẹp nhỏ nhất không nhỏ hơn $1234$ là $1313$ (gồm chu kỳ $13$ lặp lại).
4 3 8999	4 9009	Lấy chu kỳ $899$ cho ra $8998 < 8999$ , tăng chu kỳ thành $900$ , ghép lại được $9009$ .

Bình luận

Không có bình luận tại thời điểm này.