bài giải MTABC spoj THPTCBT – Xâu thứ cấp

Đề thi HSG môn tin học tỉnh Bến Tre 2014

Các bạn có thể nộp bài trên hệ thống SPOJ THPTCBT tại đây: http://www.spoj.com/THPTCBT/problems/MTABC/

1. Đề bài MTABC spoj

Cho xâu S gồm N kí tự tạo từ các chữ cái ‘a’..’z’. ta gọi S là xâu mẫu. Từ xâu mẫu S này người ta tạo ra N xâu thứ cấp bằng cách dịch chuyển theo vòng tròn xâu S qua trái i vị trí, tức là i kí tự đầu xâu lần lượt được chuyển về cuối xâu. i = 0, 1,…, N – 1. Ví dụ, nếu xâu mẫu s = ‘dabdec’ thì xâu thứ cấp thứ 2 sẽ là [2] = ‘abdecd’; xâu thứ cấp thứ 3 sẽ là [3] = ‘bdecda’.

Giả sử ta đã sắp tăng N xâu thu được theo trật tự từ điển. hãy tìm xâu thứ k trong dãy.

Dữ liệu vào

– Dòng thứ nhất chứ 2 số tự nhiên N và K cách nhau qua dấu cách, 6<=500, 1<=K<=N. N cho biết chiều dài xâu S, k cho biết vị trí của xâu thứ cấp trong dãy đựoc sắp xếp tăng theo từ điển.

– Dòng thứ hai: xâu mẫu S.

Dữ liệu ra

Gồm một dòng duy nhất chứ xâu thứ cấp cần tìm.

Example

Input

6 3

dabdec

Output

cdabde

 

2. Thuật Toán MTABC spoj

Sinh ra các xâu thứ cấp thứ i, rồi dùng Quicksort để sắp xếp. sau đó xuất ra kết quả bài toán. lưu ý phải sử dụng Ansistring.

3. Code tham khảo MTABC spoj

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *