codeforces-scrape

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

427B.md (1716B)


      1 Source: https://codeforces.com/problemset/problem/427/B
      2 
      3 B. Prison Transfer
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 The prison of your city has *n* prisoners. As the prison can't accommodate all of them, the city mayor has decided to transfer *c* of the prisoners to a prison located in another city.
     22 
     23 For this reason, he made the *n* prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.
     24 
     25 Then, the mayor told you to choose the *c* prisoners, who will be transferred to the other prison. He also imposed two conditions. They are,
     26 
     27 * The chosen *c* prisoners has to form a contiguous segment of prisoners.
     28 * Any of the chosen prisoner's crime level should not be greater then *t*. Because, that will make the prisoner a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer.
     29 
     30 Find the number of ways you can choose the *c* prisoners.
     31 
     32 Input
     33 
     34 The first line of input will contain three space separated integers *n* (1 ≤ *n* ≤ 2·105), *t* (0 ≤ *t* ≤ 109) and *c* (1 ≤ *c* ≤ *n*). The next line will contain *n* space separated integers, the *i**th* integer is the severity *i**th* prisoner's crime. The value of crime severities will be non-negative and will not exceed 109.
     35 
     36 Output
     37 
     38 Print a single integer — the number of ways you can choose the *c* prisoners.
     39 
     40 Examples
     41 
     42 Input
     43 
     44 ```
     45 4 3 3  
     46 2 3 1 1
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 1 1 1  
     59 2
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 0
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 11 4 2  
     72 2 2 0 7 3 2 2 4 9 1 4
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 6
     79 ```