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  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 