1043B.md (2476B)
1 Source: https://codeforces.com/problemset/problem/1043/B 2 3 B. Lost 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 Bajtek, known for his unusual gifts, recently got an integer array $x_0, x_1, \ldots, x_{k-1}$. 22 23 Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array $a$ of length $n + 1$. As a formal description of $a$ says, $a_0 = 0$ and for all other $i$ ($1 \le i \le n$) $a_i = x_{(i-1)\bmod k} + a_{i-1}$, where $p \bmod q$ denotes the remainder of division $p$ by $q$. 24 25 For example, if the $x = [1, 2, 3]$ and $n = 5$, then: 26 27 * $a_0 = 0$, 28 * $a_1 = x_{0\bmod 3}+a_0=x_0+0=1$, 29 * $a_2 = x_{1\bmod 3}+a_1=x_1+1=3$, 30 * $a_3 = x_{2\bmod 3}+a_2=x_2+3=6$, 31 * $a_4 = x_{3\bmod 3}+a_3=x_0+6=7$, 32 * $a_5 = x_{4\bmod 3}+a_4=x_1+7=9$. 33 34 So, if the $x = [1, 2, 3]$ and $n = 5$, then $a = [0, 1, 3, 6, 7, 9]$. 35 36 Now the boy hopes that he will be able to restore $x$ from $a$! Knowing that $1 \le k \le n$, help him and find all possible values of $k$ — possible lengths of the lost array. 37 38 Input 39 40 The first line contains exactly one integer $n$ ($1 \le n \le 1000$) — the length of the array $a$, excluding the element $a_0$. 41 42 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$). 43 44 Note that $a_0$ is always $0$ and is not given in the input. 45 46 Output 47 48 The first line of the output should contain one integer $l$ denoting the number of correct lengths of the lost array. 49 50 The second line of the output should contain $l$ integers — possible lengths of the lost array in increasing order. 51 52 Examples 53 54 Input 55 56 ``` 57 5 58 1 2 3 4 5 59 ``` 60 61 Output 62 63 ``` 64 5 65 1 2 3 4 5 66 ``` 67 68 Input 69 70 ``` 71 5 72 1 3 5 6 8 73 ``` 74 75 Output 76 77 ``` 78 2 79 3 5 80 ``` 81 82 Input 83 84 ``` 85 3 86 1 5 3 87 ``` 88 89 Output 90 91 ``` 92 1 93 3 94 ``` 95 96 Note 97 98 In the first example, any $k$ is suitable, since $a$ is an arithmetic progression. 99 100 Possible arrays $x$: 101 102 * $[1]$ 103 * $[1, 1]$ 104 * $[1, 1, 1]$ 105 * $[1, 1, 1, 1]$ 106 * $[1, 1, 1, 1, 1]$ 107 108 In the second example, Bajtek's array can have three or five elements. 109 110 Possible arrays $x$: 111 112 * $[1, 2, 2]$ 113 * $[1, 2, 2, 1, 2]$ 114 115 For example, $k = 4$ is bad, since it leads to $6 + x_0 = 8$ and $0 + x_0 = 1$, which is an obvious contradiction. 116 117 In the third example, only $k = n$ is good. 118 119 Array $[1, 4, -2]$ satisfies the requirements. 120 121 Note that $x_i$ may be negative.