2009E.md (1276B)
1 Source: https://codeforces.com/problemset/problem/2009/E 2 3 E. Klee's SUPER DUPER LARGE Array!!! 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 Klee has an array $a$ of length $n$ containing integers $[k, k+1, ..., k+n-1]$ in that order. Klee wants to choose an index $i$ ($1 \leq i \leq n$) such that $x = |a_1 + a_2 + \dots + a_i - a_{i+1} - \dots - a_n|$ is minimized. Note that for an arbitrary integer $z$, $|z|$ represents the absolute value of $z$. 22 23 Output the minimum possible value of $x$. 24 25 Input 26 27 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 28 29 Each test case contains two integers $n$ and $k$ ($2 \leq n, k \leq 10^9$) — the length of the array and the starting element of the array. 30 31 Output 32 33 For each test case, output the minimum value of $x$ on a new line. 34 35 Example 36 37 Input 38 39 ``` 40 4 41 42 2 2 43 44 7 2 45 46 5 3 47 48 1000000000 1000000000 49 ``` 50 51 Output 52 53 ``` 54 1 55 5 56 1 57 347369930 58 ``` 59 60 Note 61 62 In the first sample, $a = [2, 3]$. When $i = 1$ is chosen, $x = |2-3| = 1$. It can be shown this is the minimum possible value of $x$. 63 64 In the third sample, $a = [3, 4, 5, 6, 7]$. When $i = 3$ is chosen, $x = |3 + 4 + 5 - 6 - 7| = 1$. It can be shown this is the minimum possible value of $x$.