codeforces-scrape

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

1968C.md (1523B)


      1 Source: https://codeforces.com/problemset/problem/1968/C
      2 
      3 C. Assembly via Remainders
      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 You are given an array $x_2,x_3,\dots,x_n$. Your task is to find any array $a_1,\dots,a_n$, where:
     22 
     23 * $1\le a_i\le 10^9$ for all $1\le i\le n$.
     24 * $x_i=a_i \bmod a_{i-1}$ for all $2\le i\le n$.
     25 
     26 Here $c\bmod d$ denotes the remainder of the division of the integer $c$ by the integer $d$. For example $5 \bmod 2 = 1$, $72 \bmod 3 = 0$, $143 \bmod 14 = 3$.
     27 
     28 Note that if there is more than one $a$ which satisfies the statement, you are allowed to find any.
     29 
     30 Input
     31 
     32 The first line contains a single integer $t$ $(1\le t\le 10^4)$ — the number of test cases.
     33 
     34 The first line of each test case contains a single integer $n$ $(2\le n\le 500)$ — the number of elements in $a$.
     35 
     36 The second line of each test case contains $n-1$ integers $x_2,\dots,x_n$ $(1\le x_i\le 500)$ — the elements of $x$.
     37 
     38 It is guaranteed that the sum of values $n$ over all test cases does not exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case output any $a_1,\dots,a_n$ ($1 \le a_i \le 10^9$) which satisfies the statement.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 4
     52 
     53 2 4 1
     54 
     55 3
     56 
     57 1 1
     58 
     59 6
     60 
     61 4 2 5 1 2
     62 
     63 2
     64 
     65 500
     66 
     67 3
     68 
     69 1 5
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 3 5 4 9
     76 2 5 11
     77 5 14 16 5 11 24
     78 501 500
     79 2 7 5
     80 ```
     81 
     82 Note
     83 
     84 In the first test case $a=[3,5,4,9]$ satisfies the conditions, because:
     85 
     86 * $a_2\bmod a_1=5\bmod 3=2=x_2$;
     87 * $a_3\bmod a_2=4\bmod 5=4=x_3$;
     88 * $a_4\bmod a_3=9\bmod 4=1=x_4$;