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*.