codeforces-scrape

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

2276B.md (2249B)


      1 Source: https://codeforces.com/problemset/problem/2276/B
      2 
      3 B. Replace and Compress
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string $s$ of length $n$ consisting of the characters 0 and/or 1. You need to perform exactly one operation consisting of two steps:
     22 
     23 1. choose at most one character with index from $2$ to $n-1$ inclusive and replace it with the opposite one: 0 to 1 or 1 to 0. You may choose not to change any character. The first and the last characters of the string cannot be changed;
     24 2. replace each maximal block of consecutive equal characters with one such character.
     25 
     26 A block is called maximal if it cannot be extended to the left or to the right by adding the same character. For example, after the second step, the string 100111011 will become 10101.
     27 
     28 Count the number of different strings that can be obtained after performing this operation.
     29 
     30 Input
     31 
     32 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     33 
     34 Each test case consists of one line containing a string $s$ ($3 \le |s| \le 3 \cdot 10^5$) consisting only of the characters 0 and 1.
     35 
     36 Additional constraints on the input:
     37 
     38 * the sum of the lengths of strings $s$ over all test cases does not exceed $3 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, print one integer — the number of different strings that can be obtained after performing the operation.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 7
     50 
     51 001
     52 
     53 000
     54 
     55 010
     56 
     57 00010
     58 
     59 100111011
     60 
     61 001011010
     62 
     63 1111
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 1
     70 
     71 2
     72 
     73 2
     74 
     75 3
     76 
     77 3
     78 
     79 2
     80 
     81 2
     82 ```
     83 
     84 Note
     85 
     86 In the first test case, you may choose not to change any character or replace the second character. Before compression, the resulting strings are 001 and 011, respectively. After compression, both strings become 01, so the answer is $1$.
     87 
     88 In the fifth test case:
     89 
     90 * if no character is changed, after compression we get 10101;
     91 * if the second character is replaced, we get 110111011, and after compression — 10101;
     92 * if the fifth character is replaced, we get 100101011, and after compression — 1010101;
     93 * if the seventh character is replaced, we get 100111111, and after compression — 101.
     94 
     95 In total, three different strings can be obtained: 101, 10101, and 1010101.