trang chủ / đề bài / kbeautstr

Xâu K-đẹp

Đề bài

Mô tả

Cho số nguyên k. Một xâu gồm các chữ cái Latin in thường được gọi là đẹp nếu số lần xuất hiện của mỗi chữ cái trong xâu đều chia hết cho k (chữ cái không xuất hiện có số lần là 0, cũng chia hết cho k).

Cho xâu s độ dài n gồm các chữ cái Latin in thường. Hãy tìm xâu đẹp độ dài n nhỏ nhất theo thứ tự từ điển mà lớn hơn hoặc bằng s theo thứ tự từ điển. Nếu không tồn tại xâu như vậy, in ra −1.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên T: số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm hai dòng:
    • Dòng thứ nhất chứa hai số nguyên n và k.
    • Dòng thứ hai chứa xâu s độ dài n gồm các chữ cái Latin in thường.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng xâu đẹp nhỏ nhất theo thứ tự từ điển, có độ dài n và lớn hơn hoặc bằng s, hoặc −1 nếu không tồn tại.

Ràng buộc

  • 1≤T≤104
  • 1≤k≤n≤105
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 105

Ví dụ

Input Output Giải thích
4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa
acac
abc
-1
abaabaaab
Bộ 1: trong acac, mỗi chữ a và c xuất hiện 2 lần. Bộ 2: với k=1 mọi xâu đều đẹp nên đáp án là chính s. Bộ 3: không có xâu đẹp nào độ dài 4 với k=3. Bộ 4: trong abaabaaab, a xuất hiện 6 lần, b xuất hiện 3 lần.
4
4 2
abcd
3 2
cba
4 4
aaaa
9 5
abaabaaaa
acac
-1
aaaa
-1
Bộ 2 và bộ 4: n không chia hết cho k nên không có xâu đẹp. Bộ 3: aaaa đã đẹp nên đáp án là chính nó.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0