codeforces-scrape

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

2195D.md (1899B)


      1 Source: https://codeforces.com/problemset/problem/2195/D
      2 
      3 D. Absolute Cinema
      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 There is a hidden sequence $a_1,a_2,\ldots,a_n$ of $n$ integers ($n \ge 2$). It is guaranteed that $|a_i| \le 1000$ for all $1 \le i \le n$.
     22 
     23 Let's define a function $f(x)$ as follows:
     24 
     25 $$f(x)=\sum_{i=1}^n a_i \cdot |i-x|$$
     26 
     27 Given $n$ values $f(1),f(2),\ldots,f(n)$, please determine the values of $a_1,a_2,\ldots,a_n$.
     28 
     29 It is guaranteed that the values $a_1,a_2,\ldots,a_n$ can be determined uniquely.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($\color{red}{2} \le n \le 300\,000$).
     36 
     37 The second line of each test case contains $n$ integers $f(1),f(2),\ldots,f(n)$ ($-10^{14} \le f(i) \le 10^{14}$).
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,000$.
     40 
     41 Output
     42 
     43 For each test case, output $n$ integers $a_1,a_2,\ldots,a_n$ on a separate line ($|a_i| \le 1000$).
     44 
     45 It is guaranteed that the values $a_1,a_2,\ldots,a_n$ can be determined uniquely.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 4
     55 
     56 17 9 9 13
     57 
     58 6
     59 
     60 -37 -32 -15 4 27 42
     61 
     62 5
     63 
     64 -26 -32 -24 -4 2
     65 
     66 2
     67 
     68 420 -69
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 1 4 2 3
     75 
     76 3 6 1 2 -4 -7
     77 
     78 -6 7 6 -7 -6
     79 
     80 -69 420
     81 ```
     82 
     83 Note
     84 
     85 In the first test case, the hidden sequence is $a=[1,4,2,3]$.
     86 
     87 The values $f(1),f(2),\ldots,f(n)$ are as follows:
     88 
     89 * $f(1) = 1 \cdot |1-1| + 4 \cdot |2-1| + 2 \cdot |3-1| + 3 \cdot |4-1| = 0+4+4+9 = 17$;
     90 * $f(2) = 1 \cdot |1-2| + 4 \cdot |2-2| + 2 \cdot |3-2| + 3 \cdot |4-2| = 1+0+2+6 = 9$;
     91 * $f(3) = 1 \cdot |1-3| + 4 \cdot |2-3| + 2 \cdot |3-3| + 3 \cdot |4-3| = 2+4+0+3 = 9$;
     92 * $f(4) = 1 \cdot |1-4| + 4 \cdot |2-4| + 2 \cdot |3-4| + 3 \cdot |4-4| = 3+8+2+0 = 13$.