TopCoder

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

User's AC Ratio

69.0% (20/29)

Submission's AC Ratio

14.7% (27/184)

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