TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

70.0% (14/20)

Submission's AC Ratio

17.0% (17/100)

Description

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

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

Input Format

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

子任務(測資) 額外限制 分數
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

Output Format

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

Sample Input

123456

Sample Output

1

Hints

Problem Source

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

Subtasks

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