trang chủ / đề bài / icpc22_reg_l

Nhỏ nhất theo thứ tự từ điển

Đề bài

Mô tả

Là một người cầu toàn, Hạnh bị ám ảnh bởi việc sắp xếp và sắp xếp lại mọi thứ. Khi các đồ vật không được bày biện theo cách "đúng", Hạnh thường cảm thấy khó chịu và thiếu trọn vẹn. Chẳng hạn, Hạnh rất bứt rứt khi nhìn thấy một đoạn code C++ có dấu ngoặc nhọn nằm trên một dòng riêng.

Hôm nay Hạnh nhận được một xâu dài vô tận. Xâu này trông thật tệ: nó có một số xâu con liên tiếp gồm các ký tự giống nhau, và thậm chí nó còn không nhỏ nhất theo thứ tự từ điển! Thật kinh khủng!! Hãy giúp Hạnh sắp xếp lại xâu.

Một cách hình thức, cho xâu S và số nguyên K. Bạn phải tìm một hoán vị S′ của xâu S sao cho:

  • Trong S′ không có xâu con độ dài K nào mà mọi ký tự đều giống nhau.
  • Trong tất cả các xâu thỏa mãn điều kiện trên, S′ là xâu nhỏ nhất theo thứ tự từ điển.

Xâu a là xâu con của xâu b nếu có thể thu được a bằng cách xóa một số (có thể là không hoặc tất cả) ký tự ở đầu và một số (có thể là không hoặc tất cả) ký tự ở cuối của b. Ví dụ, abc là xâu con của abcd, nhưng abd thì không.

Xâu a nhỏ hơn xâu b theo thứ tự từ điển khi và chỉ khi một trong hai điều sau đúng:

  • a là tiền tố của b và a≠b;
  • ở vị trí đầu tiên mà a và b khác nhau, ký tự của a đứng trước ký tự tương ứng của b trong bảng chữ cái.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương T, số bộ test. Tiếp theo là T bộ test, mỗi bộ test gồm 2 dòng:

  • Dòng thứ nhất chứa xâu S khác rỗng, chỉ gồm các chữ cái tiếng Anh in thường.
  • Dòng thứ hai chứa số nguyên dương K.

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng xâu S′. Nếu không có đáp án, in ra một dòng chứa xâu OH NO!.

Ràng buộc

  • Tổng độ dài các xâu S không vượt quá 105.
  • Tổng các giá trị K không vượt quá 2·105.

Ví dụ

Input Output Giải thích
2
aabbccdd
2
aaa
2
ababcdcd
OH NO!
Với K=2, không được có hai ký tự giống nhau đứng liền nhau. Xâu aaa không thể sắp xếp để thỏa mãn điều này.
2
aaaab
3
abc
1
aabaa
OH NO!
Với K=3, không được có ba chữ a liên tiếp. Với K=1, mọi ký tự đều tạo thành một xâu con độ dài 1 gồm các ký tự giống nhau, nên không có đáp á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