2026C.md (2475B)
1 Source: https://codeforces.com/problemset/problem/2026/C 2 3 C. Action Figures 4 5 time limit per test 6 7 2.5 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 There is a shop that sells action figures near Monocarp's house. A new set of action figures will be released shortly; this set contains $n$ figures, the $i$-th figure costs $i$ coins and is available for purchase from day $i$ to day $n$. 22 23 For each of the $n$ days, Monocarp knows whether he can visit the shop. 24 25 Every time Monocarp visits the shop, he can buy any number of action figures which are sold in the shop (of course, he cannot buy an action figure that is not yet available for purchase). If Monocarp buys at least two figures during the same day, he gets a discount equal to the cost of the most expensive figure he buys (in other words, he gets the most expensive of the figures he buys for free). 26 27 Monocarp wants to buy exactly one $1$-st figure, one $2$-nd figure, ..., one $n$-th figure from the set. He cannot buy the same figure twice. What is the minimum amount of money he has to spend? 28 29 Input 30 31 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 Each test case consists of two lines: 34 35 * the first line contains one integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the number of figures in the set (and the number of days); 36 * the second line contains a string $s$ ($|s| = n$, each $s_i$ is either 0 or 1). If Monocarp can visit the shop on the $i$-th day, then $s_i$ is 1; otherwise, $s_i$ is 0. 37 38 Additional constraints on the input: 39 40 * in each test case, $s_n$ is 1, so Monocarp is always able to buy all figures during the $n$-th day; 41 * the sum of $n$ over all test cases does not exceed $4 \cdot 10^5$. 42 43 Output 44 45 For each test case, print one integer — the minimum amount of money Monocarp has to spend. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 1 55 56 1 57 58 6 59 60 101101 61 62 7 63 64 1110001 65 66 5 67 68 11111 69 ``` 70 71 Output 72 73 ``` 74 1 75 8 76 18 77 6 78 ``` 79 80 Note 81 82 In the first test case, Monocarp buys the $1$-st figure on the $1$-st day and spends $1$ coin. 83 84 In the second test case, Monocarp can buy the $1$-st and the $3$-rd figure on the $3$-rd day, the $2$-nd and the $4$-th figure on the $4$-th day, and the $5$-th and the $6$-th figure on the $6$-th day. Then, he will spend $1+2+5=8$ coins. 85 86 In the third test case, Monocarp can buy the $2$-nd and the $3$-rd figure on the $3$-rd day, and all other figures on the $7$-th day. Then, he will spend $1+2+4+5+6 = 18$ coins.