IOI Training 2024-08-27

Xét tập hợp \(S\) bao gồm tất cả những xâu ký tự chỉ chứa đúng \(m\) ký tự X, \(n\) ký tự Y, và \(p\) ký tự Z. Bạn hãy viết chương trình in ra xâu có thứ tự từ điển nhỏ thứ \(k\) trong tập \(S\).

Input:

• Dòng đầu chứa ba số nguyên dương \(m\), \(n\), \(p\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) thể hiện số câu hỏi bạn cần trả lời \((1\le Q\le 100)\).
• Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên dương \(k\) \(\left(1\le k\le |S|\right)\).

Output:

• In ra \(Q\) dòng là câu trả lời cho \(Q\) câu hỏi tương ứng.

Ràng buộc:

• \(50\%\) số test ứng với \(50\%\) số điểm có \(1\le m,n,p\le 5\).
• \(50\%\) số test còn lại ứng với \(50\%\) số điểm có \(6\le m,n,p\le 10\).

1 1 1
6
1
2
3
4
5
6

XYZ
XZY
YXZ
YZX
ZXY
ZYX

4 3 5
4
1
10
1000
27720

XXXXYYYZZZZZ
XXXXYZYZZZYZ
XXYZYZXZXZYZ
ZZZZZYYYXXXX

Hiếu vừa khám phá ra một khái niệm mới và khoe ngay với Quý: định nghĩa về xâu đẹp. Theo đó, một xâu \(s\) được gọi là đẹp nếu \(s\) có không quá \(n\) ký tự và \(f(s)\) chia hết cho \(m\), trong đó \(f(s)\) bằng tổng tất cả các \(g(c)\) với \(c\) là một ký tự trong \(s\), quy ước \(g('a')=1\), \(g('b')=2\), \(g('c')=3,\cdots, g('z')=26\). Ví dụ, với \(n=3\) và \(m=9\) thì aap là một xâu đẹp vì \(f("aap")=1+1+16=18\) chia hết cho \(m=9\), còn aah không phải là một xâu đẹp vì \(f("aah")=1+1+8=10\) không chia hết cho \(m=9\). Với xâu rỗng \(s= \emptyset\) thì \(f(s)=0\) (do đó \(s=\emptyset\) cũng là một xâu đẹp với mọi \(m\)).

Quý hiểu ngay khái niệm mới của Hiếu và liền đố ngược lại cậu: hãy tìm ra xâu đẹp có thứ tự từ điển nhỏ thứ \(k\) với \(n\) và \(m\) cho trước. Nhắc lại, xâu \(A\) được xem là có thứ tự từ điển nhỏ hơn xâu \(B\) nếu tồn tại một vị trí \(t\) sao cho \(A[1...t−1]=B[1...t−1]\) và \(A[t]<B[t]\).

Vì số \(k\) của Quý đưa ra quá lớn nên Hiếu chỉ biết ấp úng và nhờ đến các bạn lập trình giải giúp câu đố này cho Hiếu. Hãy giúp Hiếu tìm ra xâu đẹp đó nhé!

Input

• Gồm một dòng duy nhất chứa ba số nguyên dương \(n\), \(m\) và \(k (2 \leq k \leq 10^{15})\).

Output

• In ra xâu đẹp nhỏ thứ \(k\) theo thứ tự từ điển. Nếu số lượng xâu đẹp nhỏ hơn \(k\), in ra \(−1\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 4\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 100,m=1\).
• Subtask \(3\) (\(60\%\) số điểm): \(n,m \leq 100\).

Example

3 9 8

ace

Yêu cầu

• Cho dãy nguyên \(a_1, a_2, ..., a_n\). Bạn cần phải in ra dãy con tăng có thứ tự từ điển thứ \(k\)

Input:

• Cho số nguyên dương \(n, 1 \leq n \leq 10^6, 1 \leq k \leq 3.10^{18}\).
• Cho n số nguyên \(a_1, a_2, ..., a_n, 1 \leq a_i \leq n\).

Output:

• Một dòng duy nhất ghi kết quả bài toán.
• Nếu số lượng dãy con tăng bé hơn k thì in ra -1

Scoring

• \(50%\) số điểm có \(n \leq 20\).
• \(50%\) số điểm có \(n \leq 10^6\).

Example

4 4
2 3 1 4

2 3

4 100
2 3 5 4

-1

Note

• Ở test 1 Các dãy con tăng lần lượt là (1), (1, 4), (2), (2, 3), (2, 3, 4), (2, 4), (3), (3, 4), (4)

Khánh Dung có một dãy số nguyên không âm \(\delta=(\delta_0, \delta_1,...,\delta_{n-1})\) thỏa mãn \(|\delta_i-\delta_{i-1}|\leq 1\) với mọi \(1\leq i < n\) và một số nguyên dương \(m\). Trong bài toán này, Khánh Dung chỉ quan tâm đến các xâu ký tự chỉ gồm các ký tự trong số \(m\) ký tự đầu tiên trong bảng chữ cái in thường.

Dung gọi một xâu \(\sigma=\sigma_0\sigma_1...\sigma_{n-1}\) là xâu lý thú khi và chỉ khi: với mọi \(i, j\) \((0\leq i, j < n)\) mà \(0 < |i-j|\leq \delta_i\) thì \(\sigma_i\ne \sigma_j\). Với mỗi xâu lý thú \(\sigma\), cô ấy gọi \(\text{rank}(\sigma)\) là số lượng xâu lý thú có cùng độ dài với xâu \(\sigma\) và có thứ tự từ điển nhỏ hơn hẳn \(\sigma\).

Cho biết ba giá trị \(n\), \(m\), \(k\) và dãy \(\delta\), bạn hãy lập trình xác định xâu \(s\) sao cho \(\text{rank}(s)=k\).

Input:

• Dòng đầu chứa ba số nguyên dương \(n\), \(m\), và \(k\) \(\left(1\leq n\leq 25, 1\leq m\leq 5, 0\leq k\leq 10^{18}\right)\)
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(\delta_0, \delta_1,...,\delta_{n-1}\).

Output:

• Gồm một xâu lý thú \(s\) độ dài \(n\) thỏa mãn \(\text{rank}(s)=k\). Nếu không tồn tại xâu thỏa mãn thì in ra \(-1\).

3 5 48
1 2 3

eab

4 5 214
1 0 0 1

cddc

Khánh Dung có một dãy số nguyên không âm \(\delta=(\delta_0, \delta_1,...,\delta_{n-1})\) thỏa mãn \(|\delta_i-\delta_{i-1}|\leq 1\) với mọi \(1\leq i < n\) và một số nguyên dương \(m\). Trong bài toán này, Khánh Dung chỉ quan tâm đến các xâu ký tự chỉ gồm các ký tự trong số \(m\) ký tự đầu tiên trong bảng chữ cái in thường.

Dung gọi một xâu \(\sigma=\sigma_0\sigma_1...\sigma_{n-1}\) là xâu lý thú khi và chỉ khi: với mọi \(i, j\) \((0\leq i, j < n)\) mà \(0 < |i-j|\leq \delta_i\) thì \(\sigma_i\ne \sigma_j\). Với mỗi xâu lý thú \(\sigma\), cô ấy gọi \(\text{rank}(\sigma)\) là số lượng xâu lý thú có cùng độ dài với xâu \(\sigma\) và có thứ tự từ điển nhỏ hơn hẳn \(\sigma\).

Với hai xâu thú vị \(\alpha\) và \(\beta\) có cùng độ dài \(n\), Dung muốn tìm xâu thú vị \(\gamma\) có cùng độ dài \(n\) thỏa mãn \(\text{rank}(\gamma)=\text{rank}(\alpha)+\text{rank}(\beta)\) hoặc kết luận không tồn tại xâu ký tự nào như vậy.

Cho biết giá trị \(n\), \(m\), dãy \(\delta\), và hai xâu \(\alpha\), \(\beta\), bạn hãy lập trình giúp Dung xác định xâu \(\gamma\) nhé!

Input:

• Dòng đầu chứa hai số nguyên dương \(n\), \(m\) \(\left(1\leq n\leq 10^5, 1\leq m\leq 5\right)\).
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(\delta_0, \delta_1,...,\delta_{n-1}\).
• Dòng tiếp theo chứa xâu \(\alpha\) độ dài \(n\).
• Dòng tiếp theo chứa xâu \(\beta\) độ dài \(n\).

Output:

• Gồm một xâu lý thú \(\gamma\) độ dài \(n\) thỏa mãn \(\text{rank}(\gamma)=\text{rank}(\alpha)+\text{rank}(\beta)\). Nếu không tồn tại xâu thỏa mãn thì in ra \(-1\).

3 5
1 2 3
bed
cad

eab

4 5
1 0 0 1
cacb
adbc

cddc

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}\) và \(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 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.

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 \(\left(N\le 1000, K\le 10^{12}\right)\).
• 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\).

4 2
3 4 1 2

bdab

Nguồn bài: VOS Round 23 - Lê Ðôn Khuê