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

const   fi='';
        fo='';
        nmax=500;
type    data=longint;
var
        f:text;
        n,k:data;
        st,s:ansistring;
        A:array[1..nmax] of ansistring;

procedure docfile;
begin
        assign(f,fi); reset(f);
        readln(f,n,k);
        readln(f,st);
        close(f);
end;

function thucap(x:data):ansistring;
begin
        exit(copy(st,x,length(st)-x+1)+copy(st,1,x-1));
end;

    procedure sort(l,r: longint);
      var
         i,j: longint;
         x,y:ansistring;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;


procedure xuli;
var     i,j:data;
begin
        for i:=1 to n do
                a[i]:=thucap(i);
        sort(1,n);
        assign(f,fo); rewrite(f);
        writeln(f,a[k]);
        close(f);
end;

begin
        docfile;
        xuli;
end.

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