回分類題庫
g010: D.似曾相識
關鍵字: NPSC 2005 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 134 Times / 115 Users | Submit : 208 Times / 116 Users | Accepted rate : 99%
題目加入時間 : 2011-12-06 10:05

Content: 简体中文

大饅頭和他的朋友們剛買了一副新的玩具卡片,每張玩具卡片上可能印著一個英文字母、數字,或標點符號,也可能是空白的。大饅頭把這些玩具卡片拿出來放在地上排成很多個字,然後再把這些字組成一個個句子。玩到一半的時候突然電話響了,於是大饅頭就把這些卡片放在原地去接電話,這時候不巧頑皮的機拉飯剛好經過看到地上散落的卡片,就很調皮的開始惡作劇一番。

機拉飯做的動作是這樣的,每次隨便在這些卡片中找兩張相鄰的卡片,然後把它們的順序交換過來。例如大饅頭原本拼了「tea pot」這個句子(注意到中間有一張空白卡片!),如果把第一個單字中的「t」往後交換兩次,就會得到「eat pot」這個句子,再把就第二個單字中的「t」往前交換兩次,以及將p和o互換,又會得「eat top」這個句子。

現在機拉飯突發奇想想要把地上的卡片排成另外一個句子,可是又不確定能不能透過交換相鄰卡片的動作就能做到,你能寫個程式幫忙他嗎?(舉例來說,「tea pot」不管如何交換相鄰的卡片,都無法換成「eat bot」)。

Input:

輸入的測試檔包含了多筆測試資料,整個檔案的第一行有一個數字N,代表檔案中測試資料的筆數。接下來有N*2行,每兩行組成了一筆測試資料,每筆資料中第一行的句子是大饅頭原本排出的句子,第二行的是機拉飯想要排出來的句子。行中可能出現的字元包含了大小寫英文字母(大小寫視為不相等),數字0-9,空白字元,以及逗號「,」和句號「.」。每筆測試資料中的兩個句子都是等長的,而測試資料中每一行內的字元數(不包含換行字元)都不會超過1000。

Output:

整個輸出檔應該有N行。對於每筆輸入的測試資料,輸出檔都有對應的一行輸出,代表機拉飯有沒有可能透過多次相鄰卡片的交換拼出這樣的句子。如果這樣的交換是可能的,就輸出一行「possible」,否則請輸出「impossible」。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
Welcome to NTU.
He comes to NTU
abcd eee fg hhijk lmn oooop qrrsttuuv w xyz.
the quick brown fox jumps over the lazy dog.
I am rafan
am I nafar

Sample Output :

impossible
possible
possible

Hint :

Author :

NPSC 2005 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum