trang chủ / đề bài / icpc21_mn_c

Thợ mỏ vàng

Đề bài

Mô tả

Ông Phidang là một thợ mỏ vàng, và hiện ông đang ở một mỏ vàng. Ông có một cỗ máy khai thác rất mạnh nhưng có vẻ khá nặng. Ông Phidang sẽ dùng cỗ máy này để khai thác vàng hoặc các khoáng sản quý khác (ví dụ kim cương, bạc, ...).

Trong mỏ có nhiều loại khoáng sản, và ông Phidang có sở thích riêng với từng loại. Mức ưa thích của mỗi loại được biểu diễn bằng một chữ cái Latin in thường, và thứ hạng ưa thích được xét theo thứ tự bảng chữ cái. Ví dụ, loại khoáng sản ông Phidang thích nhất là 'a', loại 'b' kém ưa thích hơn một chút, loại 'c' còn kém hơn nữa, và cứ thế tiếp tục.

Mỏ vàng có thể mô tả như một dãy các ô khai thác liên tiếp nhau. Ví dụ, mỏ vàng "ebadcac" gồm 7 ô liên tiếp chứa lần lượt các khoáng sản e, b, a, d, c, a, c.

Ông Phidang có thể bắt đầu khai thác ở bất kỳ ô nào ông muốn. Tuy nhiên, sau khi bắt đầu, ông chỉ có thể di chuyển sang một trong hai ô kề bên (trái hoặc phải) để khai thác tiếp, vì ô hiện tại cần một đơn vị thời gian để được bù đầy lại, còn cỗ máy thì quá nặng nên ông không thể đi xa. Vì lượng khoáng sản ở mỗi ô là vô hạn, ông Phidang có thể quay lại các ô trước đó để khai thác.

Ông Phidang rất tham lam nên ở mỗi bước ông luôn muốn khoáng sản thu được là loại ưa thích nhất có thể. Điều này cũng có nghĩa là ông muốn chọn xâu (gồm các khoáng sản thu được theo thứ tự) có thứ tự từ điển nhỏ nhất.

Hãy giúp ông Phidang tìm ô bắt đầu tốt nhất và cách khai thác để đạt mức ưa thích tốt nhất sau một số bước cho trước. Ví dụ với mỏ vàng "ebadcac", các khoáng sản ông Phidang thu được sau 5 bước là "ababa", đó là cách tốt nhất theo sở thích của ông.

Dữ liệu vào

  • Dòng đầu tiên chứa xâu s gồm các chữ cái Latin in thường mô tả mỏ vàng. Số ô khai thác không nhỏ hơn 2 và không lớn hơn 100.
  • Dòng thứ hai chứa một số nguyên k (1≤k≤104) là số bước khai thác.

Dữ liệu ra

In ra dãy các chữ cái (không có dấu cách) là các khoáng sản theo thứ tự ông Phidang sẽ khai thác.

Ràng buộc

  • 2≤|s|≤100, s chỉ gồm chữ cái Latin in thường.
  • 1≤k≤104.

Ví dụ

Input Output Giải thích
ebadcac
5
ababa Bắt đầu ở ô thứ 3 (chữ a), rồi đi qua lại giữa ô thứ 3 và ô thứ 2 (chữ b).
ccc
6
cccccc Mọi ô đều là c.

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