2162B.md (2836B)
1 Source: https://codeforces.com/problemset/problem/2162/B 2 3 B. Beautiful String 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a binary$^{\text{∗}}$ string $s$ of length $n$. 22 23 Your task is to find any subsequence$^{\text{†}}$ $p$ of $s$ such that: 24 25 * The subsequence $p$ is non-decreasing. That is, each character in $p$ is not greater than the next one. 26 * Let $x$ denote the string obtained by removing all characters of $p$ from $s$, while preserving the order of the remaining characters. Then $x$ must be a palindrome$^{\text{‡}}$. 27 28 You only need to output any valid subsequence $p$ that satisfies both conditions. If no such subsequence exists, output $-1$. 29 30 Note that an empty string is both non-decreasing and a palindrome. 31 32 $^{\text{∗}}$A binary string is a string consisting of characters '0' and '1'. 33 34 $^{\text{†}}$A subsequence of a string $s = s_1s_2\ldots s_n$ is a sequence $p = s_{i_1}s_{i_2}\ldots s_{i_k}$ such that $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$. The characters are selected in order, but not necessarily contiguously. Note that an empty string is a subsequence of any string. 35 36 $^{\text{‡}}$A string $t = t_1t_2\ldots t_m$ is a palindrome if $t_i = t_{m - i + 1}$ for all $1 \leq i \leq m$. In other words, the string reads the same forward and backward. 37 38 Input 39 40 The first line contains a single integer $t$ ($1 \le t \le 3000$) — the number of test cases. 41 42 The first line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the length of the string. 43 44 The second line contains a binary string $s$ of length $n$. 45 46 Output 47 48 If a solution exists: 49 50 * On the first line, print a single integer $k$ ($0 \le k \le n$) — the length of the subsequence $p$. 51 * On the second line, print $k$ distinct integers $i_1, i_2, \dots, i_k$ ($1 \le i_1 \lt i_2 \lt \dots \lt i_k \le n$) — the indices of the characters in $s$ that form $p$ (in order as they appear in $s$). 52 53 Otherwise, print a single line containing $-1$. 54 55 Example 56 57 Input 58 59 ``` 60 5 61 62 3 63 64 010 65 66 3 67 68 001 69 70 5 71 72 00111 73 74 8 75 76 11010011 77 78 6 79 80 100101 81 ``` 82 83 Output 84 85 ``` 86 0 87 88 2 89 90 2 3 91 92 5 93 94 1 2 3 4 5 95 96 2 97 98 3 4 99 100 2 101 102 5 6 103 ``` 104 105 Note 106 107 In the first test case, we remove an empty string, resulting in $x = \texttt{010}$, which is a palindrome. 108 109 In the second test case, we remove $p = \texttt{01}$ (indices $2$, $3$), resulting in $x = \texttt{0}$, which is a palindrome. 110 111 In the third test case, we remove $p = \texttt{00111}$ (indices $1$ to $5$), resulting in an empty string, which is trivially a palindrome. 112 113 In the fourth test case, we remove $p = \texttt{01}$ (indices $3$, $4$), resulting in $x = \texttt{110011}$, which is a palindrome. 114 115 In the fifth test case, we remove $p = \texttt{01}$ (indices $5$, $6$), resulting in $x = \texttt{1001}$, which is a palindrome.