2013年7月13日 星期六

1209 - Wordfish

你因為樂趣和利益,想要去了解一個封閉的系統:ACM ICPC 區預賽的 Judge,經由 PC2 這套軟體,進行提交。你明白在區域網站會將資訊分類根據登入的用戶名。

然而,你沒有特別的 Judge 訪問權限可以訪問所有相關資料,只有少數的用戶名可以使用。

你將有所有用戶名的列表,而密碼根據用戶名的某種規則產生如下:


對於每個用戶名,會產生一組相對應的密碼,密碼是根據用戶名的其中 21 種連續的字典順序,而用戶名恰好是第 11 個(即排名中間)。例如用戶名是 WORDFISH,字典順序如下:


..., WOISHRFD, WOISRDFH, WOISRDHF, WOISRFDH, WOISRFHD, WOISRHDF, WOISRHFD, WORDFHIS, WORDFHSI, WORDFIHS, WORDFISH, WORDFSHI, WORDFSIH, WORDHFIS, WORDHFSI, WORDHIFS, WORDHISF, WORDHSFI, WORDHSIF, WORDIFHS, WORDIFSH, ...


密碼是 21 個字典排序中,具有最大的最小相鄰字母差的字串 (如果相同,取字典順序小的),並且附加那個最大距離的值。
如用戶名 WORDFISH,相對應的密碼為 WORDHSFI3,其中的 OR 距離是 3,而 RD 是 14,取最小的最大。


以上內容純屬虛構,如有雷同純屬巧合。

Input 

輸入將只會有長度不超過 20 的大寫字母字串,表示一個用戶名,
並且不會有超過 12 筆的輸入。
特別的是每個用戶名所使用的字母最多出現一次。

Output 

對於每組用戶名, 輸出相對應的密碼。


Sample Input 

WORDFISH

Sample Output 

WORDHSFI3