codeforces-scrape

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

870B.md (2299B)


      1 Source: https://codeforces.com/problemset/problem/870/B
      2 
      3 B. Maximum of Maximums of Minimums
      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 You are given an array *a*1, *a*2, ..., *a**n* consisting of *n* integers, and an integer *k*. You have to split the array into exactly *k* non-empty subsegments. You'll then compute the minimum integer on each subsegment, and take the maximum integer over the *k* obtained minimums. What is the maximum possible integer you can get?
     22 
     23 Definitions of subsegment and array splitting are given in notes.
     24 
     25 Input
     26 
     27 The first line contains two integers *n* and *k* (1 ≤ *k* ≤ *n* ≤  105) — the size of the array *a* and the number of subsegments you have to split the array to.
     28 
     29 The second line contains *n* integers *a*1,  *a*2,  ...,  *a**n* ( - 109  ≤  *a**i* ≤  109).
     30 
     31 Output
     32 
     33 Print single integer — the maximum possible integer you can get if you split the array into *k* non-empty subsegments and take maximum of minimums on the subsegments.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5 2  
     41 1 2 3 4 5
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 5
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 5 1  
     54 -4 -5 -3 -2 -1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 -5
     61 ```
     62 
     63 Note
     64 
     65 A subsegment [*l*,  *r*] (*l* ≤ *r*) of array *a* is the sequence *a**l*,  *a**l* + 1,  ...,  *a**r*.
     66 
     67 Splitting of array *a* of *n* elements into *k* subsegments [*l*1, *r*1], [*l*2, *r*2], ..., [*l**k*, *r**k*] (*l*1 = 1, *r**k* = *n*, *l**i* = *r**i* - 1 + 1 for all *i* > 1) is *k* sequences (*a**l*1, ..., *a**r*1), ..., (*a**l**k*, ..., *a**r**k*).
     68 
     69 In the first example you should split the array into subsegments [1, 4] and [5, 5] that results in sequences (1, 2, 3, 4) and (5). The minimums are *min*(1, 2, 3, 4) = 1 and *min*(5) = 5. The resulting maximum is *max*(1, 5) = 5. It is obvious that you can't reach greater result.
     70 
     71 In the second example the only option you have is to split the array into one subsegment [1, 5], that results in one sequence ( - 4,  - 5,  - 3,  - 2,  - 1). The only minimum is *min*( - 4,  - 5,  - 3,  - 2,  - 1) =  - 5. The resulting maximum is  - 5.