n683. 11576 - Scrolling Sign
Tags :
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-13 12:04

Content

電動滾動廣告看板經常用於廣告。 給定的標誌顯示了確切的k個字元。 當標誌開啟時,所有字元位置最初都為空(顯示空格)。 在每個時間間隔中,標誌上的所有字元都會向左移動一個位置,並在最右邊的位置新增一個新字元。 位於最左邊位置的字元移出標誌。 對於某些單字序列,可以重複使用一個單字中的字元來形成後續單字。 例如,在具有三個字元位置的標誌上,標誌可以透過滾動五個字元CATED來顯示訊息CAT ATE TED。 廣告商有一個特定的訊息要透過標誌顯示出來。 訊息顯示得越快,就越能讓更多的人看到整個訊息。 因此,您的任務是找到一種方法,以最少的字母滾動顯示所有訊息的單字。 在顯示訊息單字之間,標誌可以顯示其他不被視為訊息的單字。 但是,訊息的單字必須按照給定的順序顯示。 如果一個單字在訊息中連續出現兩次或更多次,則標誌只需要顯示一次。

Input

輸入的第一行包含一個整數n,表示接下來的測試案例數量。每個測試案例以包含兩個整數的一行開始,即k,標誌上的字符位置數,和w,消息中的單詞數。這兩個整數都介於1到100之間,包括邊界值。接下來的w行每行包含消息的一個單詞,每個單詞恰好包含k個大寫字母。

Output

對於每個測試案例,輸出一行包含一個整數,即必須滾動到標誌上的最少字母數,以便顯示消息的所有單詞。

Sample Input #1
2
3 2
CAT
TED
3 3
CAT
ATE
TEA
Sample Output #1
5
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

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