codeforces-scrape

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

1066B.md (2949B)


      1 Source: https://codeforces.com/problemset/problem/1066/B
      2 
      3 B. Heaters
      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 Vova's house is an array consisting of $n$ elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The $i$-th element of the array is $1$ if there is a heater in the position $i$, otherwise the $i$-th element of the array is $0$.
     22 
     23 Each heater has a value $r$ ($r$ is the same for all heaters). This value means that the heater at the position $pos$ can warm up all the elements in range $[pos - r + 1; pos + r - 1]$.
     24 
     25 Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater.
     26 
     27 Vova's target is to warm up the whole house (all the elements of the array), i.e. if $n = 6$, $r = 2$ and heaters are at positions $2$ and $5$, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first $3$ elements will be warmed up by the first heater and the last $3$ elements will be warmed up by the second heater).
     28 
     29 Initially, all the heaters are off.
     30 
     31 But from the other hand, Vova didn't like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.
     32 
     33 Your task is to find this number of heaters or say that it is impossible to warm up the whole house.
     34 
     35 Input
     36 
     37 The first line of the input contains two integers $n$ and $r$ ($1 \le n, r \le 1000$) — the number of elements in the array and the value of heaters.
     38 
     39 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$) — the Vova's house description.
     40 
     41 Output
     42 
     43 Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 6 2  
     51 0 1 1 0 0 1
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 3
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 5 3  
     64 1 0 0 0 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 2
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 5 10  
     77 0 0 0 0 0
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 -1
     84 ```
     85 
     86 Input
     87 
     88 ```
     89 10 3  
     90 0 0 1 1 0 1 0 0 0 1
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 3
     97 ```
     98 
     99 Note
    100 
    101 In the first example the heater at the position $2$ warms up elements $[1; 3]$, the heater at the position $3$ warms up elements $[2, 4]$ and the heater at the position $6$ warms up elements $[5; 6]$ so the answer is $3$.
    102 
    103 In the second example the heater at the position $1$ warms up elements $[1; 3]$ and the heater at the position $5$ warms up elements $[3; 5]$ so the answer is $2$.
    104 
    105 In the third example there are no heaters so the answer is -1.
    106 
    107 In the fourth example the heater at the position $3$ warms up elements $[1; 5]$, the heater at the position $6$ warms up elements $[4; 8]$ and the heater at the position $10$ warms up elements $[8; 10]$ so the answer is $3$.