Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11SSTR - String Reconstruction

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/c11sstr


Hôm nay chúng ta sẽ sẽ cùng ôn về Suffix Array !!!

Cho 1 xâu S gồm n kí tự, ta sinh ra n xâu con của S là: T[1] = S[1..n], T[2] = S[2..n], T[3] = S[3..n],.. T[n] = S[n..n];

Sau đó ta sẽ sắp xếp n xâu T lại theo thứ tự từ điển tăng dần, 1 xâu A được xem là có thứ tự từ điển nhỏ hơn B nếu tồn tại 1 vị trí k sao cho A[1..k-1] = B[1..k-1]A[k] < B[k];

Cuối cùng ta sẽ xây dựng mảng a[1], a[2], .., a[n] với a[i] = x nếu xâu T[x] nằm ở vị trí i sau khi đã được sắp xếp tăng dần. Mảng a được gọi là Suffix Array của xâu S.

Ví dụ:

  • Cho xâu S = 'bcab'. 
  • Ta có 4 xâu con:
    • T[1] = 'bcab'
    • T[2] = 'cab'
    • T[3] = 'ab'
    • T[4] = 'b'
  • Mảng T sau khi sắp xếp lại theo thứ tự tăng dần là: T[3], T[4], T[1], T[2].
  • Vậy ta có Suffix Array a là: 3 4 1 2

Yêu cầu: 

  • Cho trước Suffix Array a, và số K. Trong những xâu có Suffix Array a, hãy tìm xâu S có thứ tự từ điển nhỏ thứ K.
  • Để đơn giản các xâu chỉ bao gồm các kí tự từ 'a' đến 'z'

Chú thích:

  • Với S[i..j] (i
  • S[k] là kí tự thứ k của xâu S.
  • |S| là độ dài của xâu S hay số lượng kí tự trong xâu S.
  • Nếu k > |S| thì S[k] là một kí tự rỗng, kí tự rỗng được xem là nhỏ hơn bất kì kí tự nào khác

Input

  • Dòng đầu tiên có 2 số: N, K lần lượt là số kí tự và thứ tự từ điển của xâu cần in ra.
  • Dòng thứ 2 chứa N số nguyên phân biệt là dãy a[1], a[2],..., a[N]

Output

  • Gồm xâu kết quả in trên 1 dòng duy nhất, chỉ gồm các chữ cái thường từ 'a' đến 'z', trường hợp không có kết quả thì in ra -1

Giới hạn

  • 20% test đầu tiên có N <= 20; K = 1;
  • 10% test tiếp theo có N <= 20; K <= 1000;
  • 10% test tiếp theo có N <= 20; K <= 1012;
  • 20% test tiếp theo có N <= 1000; K = 1;
  • 20% test tiếp theo có N <= 1000; K <=1000;
  • 20% test cuối cùng có N <= 1000; K <= 1012;

Example

Input:
4 2
3 4 1 2
Output:
bdab

Giải thích:

3 xâu đầu tiên theo thứ tự từ điển có Suffix Array như đã cho là:
bcab
bdab
beab
K = 2 nên kết quả sẽ là xâu 'bdab'

Được gửi lên bởi:Hacker7
Ngày:2013-12-07
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOS Round 23 - Lê Đôn Khuê

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.