TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

68.6% (35/51)

Submission's AC Ratio

20.2% (70/346)

Description

給定一字串$S$,請找出它的所有回文子序列中最長的一個。如果有很多個,那只要隨便輸出一個就好了。

一個字串是「回文」代表它倒過來和原本的字串一樣。
一個字串的子序列的是把它其中一些字元刪去所得到的新字串(可以不刪去任何字元),例如312329311293都是11293的子序列。

Input Format

輸入只有一行,為一個只由數字字元(09)組成的字串$S$。

Output Format

請輸出$S$中任意一個長度至少$\min(1000, P)$的回文子序列,其中$P$是$S$的最長回文子序列的長度。

Sample Input

123456

Sample Output

1

Hints

Problem Source

Problem set by edisonhello
建國中學107學年度校隊選拔:初試pC

Subtasks

No. Testdata Range Constraints Score
1 0~9 $\lvert S \rvert \leq 20$ 12
2 0~19 $\lvert S \rvert \leq 87$ 9
3 0~29 $\lvert S \rvert \leq 300$ 13
4 0~49 $\lvert S \rvert \leq 1000$ 37
5 0~64 $\lvert S \rvert \leq 200000$ 29

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 524288 262144 1 2 3 4 5
1 900 524288 262144 1 2 3 4 5
2 900 524288 262144 1 2 3 4 5
3 900 524288 262144 1 2 3 4 5
4 900 524288 262144 1 2 3 4 5
5 900 524288 262144 1 2 3 4 5
6 900 524288 262144 1 2 3 4 5
7 900 524288 262144 1 2 3 4 5
8 900 524288 262144 1 2 3 4 5
9 900 524288 262144 1 2 3 4 5
10 900 524288 262144 2 3 4 5
11 900 524288 262144 2 3 4 5
12 900 524288 262144 2 3 4 5
13 900 524288 262144 2 3 4 5
14 900 524288 262144 2 3 4 5
15 900 524288 262144 2 3 4 5
16 900 524288 262144 2 3 4 5
17 900 524288 262144 2 3 4 5
18 900 524288 262144 2 3 4 5
19 900 524288 262144 2 3 4 5
20 900 524288 262144 3 4 5
21 900 524288 262144 3 4 5
22 900 524288 262144 3 4 5
23 900 524288 262144 3 4 5
24 900 524288 262144 3 4 5
25 900 524288 262144 3 4 5
26 900 524288 262144 3 4 5
27 900 524288 262144 3 4 5
28 900 524288 262144 3 4 5
29 900 524288 262144 3 4 5
30 900 524288 262144 4 5
31 900 524288 262144 4 5
32 900 524288 262144 4 5
33 900 524288 262144 4 5
34 900 524288 262144 4 5
35 900 524288 262144 4 5
36 900 524288 262144 4 5
37 900 524288 262144 4 5
38 900 524288 262144 4 5
39 900 524288 262144 4 5
40 900 524288 262144 4 5
41 900 524288 262144 4 5
42 900 524288 262144 4 5
43 900 524288 262144 4 5
44 900 524288 262144 4 5
45 900 524288 262144 4 5
46 900 524288 262144 4 5
47 900 524288 262144 4 5
48 900 524288 262144 4 5
49 900 524288 262144 4 5
50 1900 524288 262144 5
51 1900 524288 262144 5
52 1900 524288 262144 5
53 1900 524288 262144 5
54 1900 524288 262144 5
55 1900 524288 262144 5
56 1900 524288 262144 5
57 1900 524288 262144 5
58 1900 524288 262144 5
59 1900 524288 262144 5
60 1900 524288 262144 5
61 1900 524288 262144 5
62 1900 524288 262144 5
63 1900 524288 262144 5
64 1900 524288 262144 5