codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.