codeforces-scrape

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

2007C.md (2799B)


      1 Source: https://codeforces.com/problemset/problem/2007/C
      2 
      3 C. Dora and C++
      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 Dora has just learned the programming language C++!
     22 
     23 However, she has completely misunderstood the meaning of C++. She considers it as two kinds of adding operations on the array $c$ with $n$ elements. Dora has two integers $a$ and $b$. In one operation, she can choose one of the following things to do.
     24 
     25 * Choose an integer $i$ such that $1 \leq i \leq n$, and increase $c_i$ by $a$.
     26 * Choose an integer $i$ such that $1 \leq i \leq n$, and increase $c_i$ by $b$.
     27 
     28 Note that $a$ and $b$ are constants, and they can be the same.
     29 
     30 Let's define a range of array $d$ as $\max(d_i) - \min(d_i)$. For instance, the range of the array $[1, 2, 3, 4]$ is $4 - 1 = 3$, the range of the array $[5, 2, 8, 2, 2, 1]$ is $8 - 1 = 7$, and the range of the array $[3, 3, 3]$ is $3 - 3 = 0$.
     31 
     32 After any number of operations (possibly, $0$), Dora calculates the range of the new array. You need to help Dora minimize this value, but since Dora loves exploring all by herself, you only need to tell her the minimized value.
     33 
     34 Input
     35 
     36 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.
     37 
     38 The first line of each test case contains three integers $n$, $a$, and $b$ ($1 \leq n \leq 10^5$, $1 \leq a, b \leq 10^9$) — the length of the array $c$ and the constant values, respectively.
     39 
     40 The second line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the initial elements of the array $c$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, output a single integer — the minimum possible range of the array after any number of operations.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 10
     54 
     55 4 5 5
     56 
     57 1 3 4 4
     58 
     59 4 2 3
     60 
     61 1 3 4 6
     62 
     63 4 7 7
     64 
     65 1 1 2 6
     66 
     67 3 15 9
     68 
     69 1 9 5
     70 
     71 3 18 12
     72 
     73 1 4 5
     74 
     75 7 27 36
     76 
     77 33 13 23 12 35 24 41
     78 
     79 10 6 9
     80 
     81 15 5 6 9 8 2 12 15 3 8
     82 
     83 2 1 1000000000
     84 
     85 1 1000000000
     86 
     87 6 336718728 709848696
     88 
     89 552806726 474775724 15129785 371139304 178408298 13106071
     90 
     91 6 335734893 671469786
     92 
     93 138885253 70095920 456876775 9345665 214704906 375508929
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 3
    100 
    101 0
    102 
    103 3
    104 
    105 2
    106 
    107 3
    108 
    109 5
    110 
    111 1
    112 
    113 0
    114 
    115 17
    116 
    117 205359241
    118 ```
    119 
    120 Note
    121 
    122 In the first test case, we can increase $c_1 = 1$ by $a = 5$. The array $c$ will become $[6, 3, 4, 4]$, and the range is $3$. Note that there is more than one way to reach the answer.
    123 
    124 In the second test case, we can increase $c_1 = 1$ by $a = 2$ and then increase $c_1 = 3$ by $b = 3$. Also, we can increase $c_2 = 3$ by $b = 3$ and increase $c_3 = 4$ by $a = 2$. The array $c$ will become $[6, 6, 6, 6]$, and the range is $0$.