回分類題庫
d079: 2009 SIG Winter C - 胖達的DNA
出處:

Difficulity : 1
Accepted : 37 Times | Submit :141 Times | Clicks : 2044
Accepted : 33 Users | Submit : 43 Users | Accepted rate : 77%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2009-02-20 08:52

Content :

胖達喜歡吃橘子跟騎駱駝。這一天胖達一邊吃著橘子一邊騎著駱駝一邊思考著DNA的問題。
他把DNA的排序狀況用下面的規則來決定「未排序」程度。 譬如說"DAABEC"中,
「未排序」的程度為5,因為D比他右邊的4個字元大,E比他右邊的1個字元大,
加起來總共為5。又舉"AACEDGG"來講,「未排序」的程度為1,這是幾乎快要排序好的,
只有E比右邊的1一個字元大。構成胖達的是四種DNA:A、C、G跟T。
排序的原則是根據各組DNA的「未排序」的程度來排,有小到大輸出。
除此之外,每一段的DNA長度均相等。

Input :

輸入的第一列有一個整數代表以下將會有幾組測試資料。
每組測試資料的第一列含有2個正整數n(0<n<=50)和m(0<m<=100),
n代表DNA的長度,m代表DNA的組數。接下來的m列,每列有一個長度為n的DNA。
各組測試資料之間有一行空白行。

Output :

對於每一組輸入的DNA進行排序,依照每一段DNA的「未排序」程度,由小到大輸出各段DNA。
假設有超過兩組DNA的「未排序」程度一樣,則依照輸入時的順序進行輸出。
各組資料之間需要輸出一行空白行。

Sample Input :

2

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

2 3
TC
TT
TA

Sample Output :

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

TT
TC
TA

Hint :


  

Author :


  Solve it!   Status Forum (2)

C++
C
JAVA
7281. pcsh710742 (4 ms , 458KB)
45863. justin6 (8 ms , 220KB)
40362. staycalm (8 ms , 214KB)
20906. liouzhou_101 (8 ms , 272KB)
49465. CC501 (12 ms , 364KB)
20797. nipa (2 ms , 268KB)
54752. ag100 (4 ms , 256KB)
38871. cp100703009 (4 ms , 270KB)
2478. team16 (4 ms , 220KB)
87126. nccucs105703018 (6 ms , 266KB)
65011. nwgs524513cja (184 ms , 2398KB)
53188. nwgs524513cja (192 ms , 3174KB)
87463. a6205 (216 ms , 3000KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡