codeforces-scrape

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

2040B.md (2463B)


      1 Source: https://codeforces.com/problemset/problem/2040/B
      2 
      3 B. Paint a Strip
      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 have an array of zeros $a_1, a_2, \ldots, a_n$ of length $n$.
     22 
     23 You can perform two types of operations on it:
     24 
     25 1. Choose an index $i$ such that $1 \le i \le n$ and $a_i = 0$, and assign $1$ to $a_i$;
     26 2. Choose a pair of indices $l$ and $r$ such that $1 \le l \le r \le n$, $a_l = 1$, $a_r = 1$, $a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil$, and assign $1$ to $a_i$ for all $l \le i \le r$.
     27 
     28 What is the minimum number of operations of the first type needed to make all elements of the array equal to one?
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     33 
     34 The only line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array.
     35 
     36 Note that there is no limit on the sum of $n$ over all test cases.
     37 
     38 Output
     39 
     40 For each test case, print one integer — the minimum number of needed operations of first type.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 4
     48 
     49 1
     50 
     51 2
     52 
     53 4
     54 
     55 20
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 1
     62 2
     63 2
     64 4
     65 ```
     66 
     67 Note
     68 
     69 In the first test case, you can perform an operation of the $1$st type with $i = 1$.
     70 
     71 In the second test case, you can perform the following sequence of operations:
     72 
     73 1. Operation of $1$st type, $i = 1$. After performing this operation, the array will look like this: $[1, 0]$.
     74 2. Operation of $1$st type, $i = 2$. After performing this operation, the array will look like this: $[1, 1]$.
     75 
     76  The sequence of operations in the second test case ![](https://espresso.codeforces.com/156bcaf373269893d42705e3faa6481b95059ee8.png) 
     77 
     78 In the third test case, you can perform the following sequence of operations:
     79 
     80 1. Operation of $1$st type, $i = 1$. After performing this operation, the array will look like this: $[1, 0, 0, 0]$.
     81 2. Operation of $1$st type, $i = 4$. After performing this operation, the array will look like this: $[1, 0, 0, 1]$.
     82 3. Operation of $2$nd type, $l = 1$, $r = 4$. On this segment, $a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2$, which is not less than $\lceil\frac{r - l + 1}{2}\rceil = 2$. After performing this operation, the array will look like this: $[1, 1, 1, 1]$.
     83 
     84  The sequence of operations in the third test case ![](https://espresso.codeforces.com/1a624ace7fad723b5b9be1e51701849df1b17172.png)