codeforces-scrape

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

1499B.md (2078B)


      1 Source: https://codeforces.com/problemset/problem/1499/B
      2 
      3 B. Binary Removals
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 string $s$, consisting only of characters '0' or '1'. Let $|s|$ be the length of $s$.
     22 
     23 You are asked to choose some integer $k$ ($k \gt 0$) and find a sequence $a$ of length $k$ such that:
     24 
     25 * $1 \le a_1 \lt a_2 \lt \dots \lt a_k \le |s|$;
     26 * $a_{i-1} + 1 \lt a_i$ for all $i$ from $2$ to $k$.
     27 
     28 The characters at positions $a_1, a_2, \dots, a_k$ are removed, the remaining characters are concatenated without changing the order. So, in other words, the positions in the sequence $a$ should not be adjacent.
     29 
     30 Let the resulting string be $s'$. $s'$ is called sorted if for all $i$ from $2$ to $|s'|$ $s'_{i-1} \le s'_i$.
     31 
     32 Does there exist such a sequence $a$ that the resulting string $s'$ is sorted?
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.
     37 
     38 Then the descriptions of $t$ testcases follow.
     39 
     40 The only line of each testcase contains a string $s$ ($2 \le |s| \le 100$). Each character is either '0' or '1'.
     41 
     42 Output
     43 
     44 For each testcase print "YES" if there exists a sequence $a$ such that removing the characters at positions $a_1, a_2, \dots, a_k$ and concatenating the parts without changing the order produces a sorted string.
     45 
     46 Otherwise, print "NO".
     47 
     48 You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 5
     56 10101011011
     57 0000
     58 11111
     59 110
     60 1100
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 YES
     67 YES
     68 YES
     69 YES
     70 NO
     71 ```
     72 
     73 Note
     74 
     75 In the first testcase you can choose a sequence $a=[1,3,6,9]$. Removing the underlined letters from "10101011011" will produce a string "0011111", which is sorted.
     76 
     77 In the second and the third testcases the sequences are already sorted.
     78 
     79 In the fourth testcase you can choose a sequence $a=[3]$. $s'=$ "11", which is sorted.
     80 
     81 In the fifth testcase there is no way to choose a sequence $a$ such that $s'$ is sorted.