codeforces-scrape

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

998B.md (2170B)


      1 Source: https://codeforces.com/problemset/problem/998/B
      2 
      3 B. Cutting
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 There are a lot of things which could be cut — trees, paper, "the rope". In this problem you are going to cut a sequence of integers.
     22 
     23 There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.
     24 
     25 Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$ $\to$ two cuts $\to$ $[4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]$. On each segment the number of even elements should be equal to the number of odd elements.
     26 
     27 The cost of the cut between $x$ and $y$ numbers is $|x - y|$ bitcoins. Find the maximum possible number of cuts that can be made while spending no more than $B$ bitcoins.
     28 
     29 Input
     30 
     31 First line of the input contains an integer $n$ ($2 \le n \le 100$) and an integer $B$ ($1 \le B \le 100$) — the number of elements in the sequence and the number of bitcoins you have.
     32 
     33 Second line contains $n$ integers: $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 100$) — elements of the sequence, which contains the equal number of even and odd numbers
     34 
     35 Output
     36 
     37 Print the maximum possible number of cuts which can be made while spending no more than $B$ bitcoins.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 6 4  
     45 1 2 5 10 15 20
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 1
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 4 10  
     58 1 3 2 4
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 6 100  
     71 1 2 3 4 5 6
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 2
     78 ```
     79 
     80 Note
     81 
     82 In the first sample the optimal answer is to split sequence between $2$ and $5$. Price of this cut is equal to $3$ bitcoins.
     83 
     84 In the second sample it is not possible to make even one cut even with unlimited number of bitcoins.
     85 
     86 In the third sample the sequence should be cut between $2$ and $3$, and between $4$ and $5$. The total price of the cuts is $1 + 1 = 2$ bitcoins.