TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

56.8% (21/37)

Tags

Description

分析如DNA序列這樣的生命科學數據是計算機的一個有趣應用。

從生物學的角度上說, DNA 是一種由腺嘌呤,胞嘧啶,鳥嘌呤和胸腺嘧啶這四種核苷酸組成的鍊式結構,
這四種核苷酸分別用大寫字母 A, C, G, T表示,

這樣,一條DNA單鏈可以被表示為一個只含以上四種字元的字元串。
我們將這樣的字元串稱作一個 DNA 序列。

有時生物學家可能無法確定一條DNA單鏈中的某些核苷酸,
在這種情況下,字元 N 將被用來表示一個不確定的核苷酸。

換句話說,N可以用來表示A, C, G, T中的任何一個字元,
我們稱包含一個或者多個 N 的 DNA 序列為未完成序列,反之,就稱作完成序列,

如果一個完成序列可以通過將一個未完成序列中的每個 N 任意替換成A, C, G, T得到的話,就稱完成序列吻合這個未完成序列。

舉例來說,ACCCT 吻合 ACNNT,但是 AGGAT 則不吻合。

研究者們經常按照如下方式排序四種核苷酸:A 優先於 C,C 優先於 G,G 優先於 T,
如果一個 DNA 序列中的每個核苷酸都與其右邊的相同或者優先,就將其歸類為 類型-1 。

舉例來說, AACCGT 是 類型-1 ,但是AACGTC不是。

一般來說,一個 DNA 序列屬於 類型-J(J > 1),只要它屬於 類型-(J-1) 或者是一個 類型-(J-1) 和一個 類型-1 的連接。

舉例來說,AACCC, ACACC 和 ACACA 都是 類型-3 ,但 GCACAC 和 ACACACA 不是。

同樣,研究者們按照字典序對DNA序列進行排序,
按照這個定義,最小的屬於類型-3的DNA序列是AAAAA,最大的是TTTTT,

這裡是另外一個例子,考慮未完成序列ACANNCNNG,那麼前7個吻合這個未完成序列的DNA序列

寫一個程式,當給定一串長度為 M 的不完整序列後,尋找與它吻合的第 R 串類型 K 序列。

Input Format

輸入第一行有3個整數M, K, R,以空白分隔。
第二行包含一串長度為 M 的字元序列,代表不完整序列。

與此串不完整序列吻合的 類型K 序列的個數將不會大於4×1018
此外,R 不會大於與所給定的不完整序列吻合之 類型K 序列的個數。
(1 ≤ M ≤ 50,000),K (1 ≤ K ≤ 10),R (1 ≤ R ≤ 2×1012)

Output Format

在輸出一行吻合輸入的不完整序列的第 R 串 類型K 序列。

Sample Input 1

9 3 5
ACANNCNNG

Sample Output 1

ACAAACCCG

Sample Input 2

5 4 10
ACANN

Sample Output 2

ACAGC

Hints

Problem Source

原TIOJ1741 / APIO '08

Subtasks

No. Testdata Range Score
1 0 6
2 1 6
3 2 6
4 3 6
5 4 6
6 5 6
7 6 6
8 7 6
9 8 6
10 9 6
11 10 6
12 11 6
13 12 6
14 13 6
15 14 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 131072 262144 1
1 1500 131072 262144 2
2 1500 131072 262144 3
3 1500 131072 262144 4
4 1500 131072 262144 5
5 1500 131072 262144 6
6 1500 131072 262144 7
7 1500 131072 262144 8
8 1500 131072 262144 9
9 1500 131072 262144 10
10 1500 131072 262144 11
11 1500 131072 262144 12
12 1500 131072 262144 13
13 1500 131072 262144 14
14 1500 131072 262144 15