codeforces-scrape

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

940D.md (2282B)


      1 Source: https://codeforces.com/problemset/problem/940/D
      2 
      3 D. Alena And The Heater
      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 "We've tried solitary confinement, waterboarding and listening to Just In Beaver, to no avail. We need something extreme."
     22 
     23 "Little Alena got an array as a birthday present..."
     24 
     25 The array *b* of length *n* is obtained from the array *a* of length *n* and two integers *l* and *r* (*l* ≤ *r*) using the following procedure:
     26 
     27 *b*1 = *b*2 = *b*3 = *b*4 = 0.
     28 
     29 For all 5 ≤ *i* ≤ *n*:
     30 
     31 * *b**i* = 0 if *a**i*, *a**i* - 1, *a**i* - 2, *a**i* - 3, *a**i* - 4 > *r* and *b**i* - 1 = *b**i* - 2 = *b**i* - 3 = *b**i* - 4 = 1
     32 * *b**i* = 1 if *a**i*, *a**i* - 1, *a**i* - 2, *a**i* - 3, *a**i* - 4 < *l* and *b**i* - 1 = *b**i* - 2 = *b**i* - 3 = *b**i* - 4 = 0
     33 * *b**i* = *b**i* - 1 otherwise
     34 
     35 You are given arrays *a* and *b*' of the same length. Find two integers *l* and *r* (*l* ≤ *r*), such that applying the algorithm described above will yield an array *b* equal to *b*'.
     36 
     37 It's guaranteed that the answer exists.
     38 
     39 Input
     40 
     41 The first line of input contains a single integer *n* (5 ≤ *n* ≤ 105) — the length of *a* and *b*'.
     42 
     43 The second line of input contains *n* space separated integers *a*1, ..., *a**n* ( - 109 ≤ *a**i* ≤ 109) — the elements of *a*.
     44 
     45 The third line of input contains a string of *n* characters, consisting of 0 and 1 — the elements of *b*'. Note that they are not separated by spaces.
     46 
     47 Output
     48 
     49 Output two integers *l* and *r* ( - 109 ≤ *l* ≤ *r* ≤ 109), conforming to the requirements described above.
     50 
     51 If there are multiple solutions, output any of them.
     52 
     53 It's guaranteed that the answer exists.
     54 
     55 Examples
     56 
     57 Input
     58 
     59 ```
     60 5  
     61 1 2 3 4 5  
     62 00001
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 6 15
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 10  
     75 -10 -9 -8 -7 -6 6 7 8 9 10  
     76 0000111110
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 -5 5
     83 ```
     84 
     85 Note
     86 
     87 In the first test case any pair of *l* and *r* pair is valid, if 6 ≤ *l* ≤ *r* ≤ 109, in that case *b*5 = 1, because *a*1, ..., *a*5 < *l*.