a208: APIO2008 3.DNA
Tags :
Accepted rate : 9人/10人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:11

Content

分析如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 序列
是:

 

 

ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG

写一个程序,找到按字典序的第R 个适合给定的长度为M 的未完成序列的
范式-K。

Input
输入第一行包含三个由空格隔开的整数:M(1≤M≤50,000),K(1≤K≤10)和
R(1≤R≤2×10^12)。第二行包含一个长度为M 的字符串,表示未完成序列。保证适
合该未完成序列的范式-K 的总数不超过4×10^18,因此该数可以用C 和C++中的
long long 类型或者Pascal 中的Int64 类型表示。同时,R 不会超过适合给定未完
成序列的范式-K 的总数。
Output
在第一行中输出第R 个适合输入中的未完成序列的范式-K。
Sample Input
9 3 5
ACANNCNNG

5 4 10
ACANN
Sample Output
ACAAACCCG

ACAGC
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (7%): 1.0s , <1K
公開 測資點#2 (7%): 1.0s , <1K
公開 測資點#3 (6%): 1.0s , <1K
公開 測資點#4 (7%): 1.0s , <1K
公開 測資點#5 (7%): 1.0s , <1M
公開 測資點#6 (6%): 1.0s , <1K
公開 測資點#7 (7%): 1.0s , <1K
公開 測資點#8 (7%): 1.0s , <1K
公開 測資點#9 (6%): 1.0s , <1K
公開 測資點#10 (7%): 1.0s , <1M
公開 測資點#11 (7%): 1.0s , <1M
公開 測資點#12 (6%): 1.0s , <1M
公開 測資點#13 (7%): 1.0s , <1K
公開 測資點#14 (7%): 1.0s , <1M
Hint :
感谢morris1028补上图片!
Tags:
出處:
APIO2008第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」