codeforces-scrape

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

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.