375 . 上海自來水來自海上

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Cheng0928
$\huge \color{ProcessBlue}{負けヒ}$

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Algo Algo25_b

Description

回文，就是正著念跟反著念都一樣的字串，例如「上海自來水來自上海」跟「level」。

現在給你一個字串，希望你在這個字串中間插入幾個字元（也可能是 $0$ 個），使得插入字元後產生的字串是個回文。 除了最終形成回文以外，還需要產生的這個字串是最短的，但是最短的這些字串也可能有多個，因此你的程式需要找出的其實是這些最短的回文中，字典序第 $k$ 小的。

舉例來說，如果輸入的字串是 "cdba"，而你要找出的是字典序第 $7$ 小的， 那麼你要從以下 $8$ 個：abcdcba, abdcdba, acbdbca, acdbdca, cabdbac, cadbdac, cdabadc, cdbabdc，中，輸出字典序第 $7$ 小的 "cdabadc"。

Input Format

每次輸入只包含一筆測試資料。

輸入包含兩行，第一行包含一個由小寫英文字母組成的字串，其長度大於 $0$ 且不超過 $2000$。第二行包含一個正整數 $k(1 \leq k \leq 10^{18})$。

Output Format

請輸出由輸入的字串插入數個字元而形成的最短回文中，字典序第 $k$ 小的。若字典序第 $k$ 小的字串不存在，也就是最短的回文根本不足 $k$ 個，則輸出 "NONE"(不含引號)。

Sample Input 1

crc
1

Sample Output 1

crc

Sample Input 2

icpc
1

Sample Output 2

icpci

Sample Input 3

hello
1

Sample Output 3

heolloeh

Sample Input 4

hoge
8

Sample Output 4

hogegoh

Sample Input 5

hoge
9

Sample Output 5

NONE

Sample Input 6

bbaaab
2

Sample Output 6

NONE

Sample Input 7

thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500

Sample Output 7

feeberrthdstodxtksrnfacdjsohnlfuivdhqvqsozhgdqypllstwausnzcmjkboehgcerzvwxakyhswuojpfhzumvmlxxdfkmezmprlotpndbubbkblnjiedttmawsyqazekcftgshqbrhrtkzngaxbzfhnnlanxvphyfnkqmzcsdfscaawdleqaxtnhehwzgzwhehntxaqeldwaacsfdsczmqknfyhpvxnalnnhfzbxagnzktrhrbqhsgtfckezaqyswamttdeijnlbkbbubdnptolrpmzemkfdxxlmvmuzhfpjouwshykaxwvzrecgheobkjmcznsuawtsllpyqdghzosqvqhdviuflnhosjdcafnrsktxdotsdhtrrebeef

Hints

Problem Source

NEOJ Problem 423

Subtasks

No. Testdata Range Constraints Score
1 0~47 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1
1 1000 131072 65536 1
2 1000 131072 65536 1
3 1000 131072 65536 1
4 1000 131072 65536 1
5 1000 131072 65536 1
6 1000 131072 65536 1
7 1000 131072 65536 1
8 1000 131072 65536 1
9 1000 131072 65536 1
10 1000 131072 65536 1
11 1000 131072 65536 1
12 1000 131072 65536 1
13 1000 131072 65536 1
14 1000 131072 65536 1
15 1000 131072 65536 1
16 1000 131072 65536 1
17 1000 131072 65536 1
18 1000 131072 65536 1
19 1000 131072 65536 1
20 1000 131072 65536 1
21 1000 131072 65536 1
22 1000 131072 65536 1
23 1000 131072 65536 1
24 1000 131072 65536 1
25 1000 131072 65536 1
26 1000 131072 65536 1
27 1000 131072 65536 1
28 1000 131072 65536 1
29 1000 131072 65536 1
30 1000 131072 65536 1
31 1000 131072 65536 1
32 1000 131072 65536 1
33 1000 131072 65536 1
34 1000 131072 65536 1
35 1000 131072 65536 1
36 1000 131072 65536 1
37 1000 131072 65536 1
38 1000 131072 65536 1
39 1000 131072 65536 1
40 1000 131072 65536 1
41 1000 131072 65536 1
42 1000 131072 65536 1
43 1000 131072 65536 1
44 1000 131072 65536 1
45 1000 131072 65536 1
46 1000 131072 65536 1
47 1000 131072 65536 1
Submit
Back to Top