codeforces-scrape

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

1811C.md (2759B)


      1 Source: https://codeforces.com/problemset/problem/1811/C
      2 
      3 C. Restore the Array
      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 Kristina had an array $a$ of length $n$ consisting of non-negative integers.
     22 
     23 She built a new array $b$ of length $n-1$, such that $b_i = \max(a_i, a_{i+1})$ ($1 \le i \le n-1$).
     24 
     25 For example, suppose Kristina had an array $a$ = [$3, 0, 4, 0, 5$] of length $5$. Then she did the following:
     26 
     27 1. Calculated $b_1 = \max(a_1, a_2) = \max(3, 0) = 3$;
     28 2. Calculated $b_2 = \max(a_2, a_3) = \max(0, 4) = 4$;
     29 3. Calculated $b_3 = \max(a_3, a_4) = \max(4, 0) = 4$;
     30 4. Calculated $b_4 = \max(a_4, a_5) = \max(0, 5) = 5$.
     31 
     32 As a result, she got an array $b$ = [$3, 4, 4, 5$] of length $4$.
     33 
     34 You only know the array $b$. Find any matching array $a$ that Kristina may have originally had.
     35 
     36 Input
     37 
     38 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     39 
     40 The description of the test cases follows.
     41 
     42 The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$ that Kristina originally had.
     43 
     44 The second line of each test case contains exactly $n-1$ non-negative integer — elements of array $b$ ($0 \le b_i \le 10^9$).
     45 
     46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and that array $b$ was built correctly from some array $a$.
     47 
     48 Output
     49 
     50 For each test case on a separate line, print exactly $n$ non-negative integers — the elements of the array $a$ that Kristina originally had.
     51 
     52 If there are several possible answers — output any of them.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 11
     60 
     61 5
     62 
     63 3 4 4 5
     64 
     65 4
     66 
     67 2 2 1
     68 
     69 5
     70 
     71 0 0 0 0
     72 
     73 6
     74 
     75 0 3 4 4 3
     76 
     77 2
     78 
     79 10
     80 
     81 4
     82 
     83 3 3 3
     84 
     85 5
     86 
     87 4 2 5 5
     88 
     89 4
     90 
     91 3 3 3
     92 
     93 4
     94 
     95 2 1 0
     96 
     97 3
     98 
     99 4 4
    100 
    101 6
    102 
    103 8 1 3 5 10
    104 ```
    105 
    106 Output
    107 
    108 ```
    109 3 0 4 0 5
    110 2 2 1 1
    111 0 0 0 0 0
    112 0 0 3 4 3 3
    113 10 10
    114 3 3 3 1
    115 4 2 2 5 5
    116 3 3 3 3
    117 2 1 0 0
    118 2 4 4
    119 8 1 1 3 5 10
    120 ```
    121 
    122 Note
    123 
    124 The first test case is explained in the problem statement.
    125 
    126 In the second test case, we can get array $b$ = [$2, 2, 1$] from the array $a$ = [$2, 2, 1, 1$]:
    127 
    128 * $b_1 = \max(a_1, a_2) = \max(2, 2) = 2$;
    129 * $b_2 = \max(a_2, a_3) = \max(2, 1) = 2$;
    130 * $b_3 = \max(a_3, a_4) = \max(1, 1) = 1$.
    131 
    132 In the third test case, all elements of the array $b$ are zeros. Since each $b_i$ is the maximum of two adjacent elements of array $a$, array $a$ can only consist entirely of zeros.
    133 
    134 In the fourth test case, we can get array $b$ = [$0, 3, 4, 4, 3$] from the array $a$ = [$0, 0, 3, 4, 3, 3$] :
    135 
    136 * $b_1 = \max(a_1, a_2) = \max(0, 0) = 0$;
    137 * $b_2 = \max(a_2, a_3) = \max(0, 3) = 3$;
    138 * $b_3 = \max(a_3, a_4) = \max(3, 4) = 4$;
    139 * $b_4 = \max(a_4, a_5) = \max(4, 3) = 4$;
    140 * $b_5 = \max(a_5, a_6) = \max(3, 3) = 3$.