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$;