codeforces-scrape

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

2230B.md (1607B)


      1 Source: https://codeforces.com/problemset/problem/2230/B
      2 
      3 B. Digit String
      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$ consisting of digits from $1$ to $4$.
     22 
     23 Let's say that the string is beautiful if it is impossible to select some of its elements and write them out (in the same order as they appear in the string) to form a number that is a multiple of $4$. For example, the strings 31, 222, 213 are beautiful, while the strings 143, 3123, 1322 are not. The empty string is considered beautiful.
     24 
     25 Your task is to calculate the minimum possible number of elements in the string $s$ that need to be removed in order to make it beautiful.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 The only line of each test case contains a string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting of digits from $1$ to $4$.
     32 
     33 Additional constraint on the input: the sum of the lengths of $s$ over all test cases doesn't exceed $3 \cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, print a single integer — the minimum possible number of elements in the string $s$ that need to be removed in order to make it beautiful.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5
     45 
     46 4
     47 
     48 13
     49 
     50 3244123
     51 
     52 24424224242
     53 
     54 4132423432241231
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1
     61 
     62 0
     63 
     64 4
     65 
     66 5
     67 
     68 9
     69 ```
     70 
     71 Note
     72 
     73 In the first example, you have to delete the whole string.
     74 
     75 In the second example, the string is already beautiful.
     76 
     77 In the third example, you can delete the $1$-st, $3$-rd, $4$-th, and $6$-th characters, and you will get the string 213.