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 ...
Đề 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | 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. |
