codeforces-scrape

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

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.