codeforces-scrape

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

1872D.md (2902B)


      1 Source: https://codeforces.com/problemset/problem/1872/D
      2 
      3 D. Plus Minus Permutation
      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 You are given $3$ integers — $n$, $x$, $y$. Let's call the score of a permutation$^\dagger$ $p_1, \ldots, p_n$ the following value:
     22 
     23 $$(p_{1 \cdot x} + p_{2 \cdot x} + \ldots + p_{\lfloor \frac{n}{x} \rfloor \cdot x}) - (p_{1 \cdot y} + p_{2 \cdot y} + \ldots + p_{\lfloor \frac{n}{y} \rfloor \cdot y})$$
     24 
     25 In other words, the score of a permutation is the sum of $p_i$ for all indices $i$ divisible by $x$, minus the sum of $p_i$ for all indices $i$ divisible by $y$.
     26 
     27 You need to find the maximum possible score among all permutations of length $n$.
     28 
     29 For example, if $n = 7$, $x = 2$, $y = 3$, the maximum score is achieved by the permutation $[2,\color{red}{\underline{\color{black}{6}}},\color{blue}{\underline{\color{black}{1}}},\color{red}{\underline{\color{black}{7}}},5,\color{blue}{\underline{\color{red}{\underline{\color{black}{4}}}}},3]$ and is equal to $(6 + 7 + 4) - (1 + 4) = 17 - 5 = 12$.
     30 
     31 $^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but the array contains $4$).
     32 
     33 Input
     34 
     35 The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 Then follows the description of each test case.
     38 
     39 The only line of each test case description contains $3$ integers $n$, $x$, $y$ ($1 \le n \le 10^9$, $1 \le x, y \le n$).
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the maximum score among all permutations of length $n$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 8
     51 
     52 7 2 3
     53 
     54 12 6 3
     55 
     56 9 1 9
     57 
     58 2 2 2
     59 
     60 100 20 50
     61 
     62 24 4 6
     63 
     64 1000000000 5575 25450
     65 
     66 4 4 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 12
     73 -3
     74 44
     75 0
     76 393
     77 87
     78 179179179436104
     79 -6
     80 ```
     81 
     82 Note
     83 
     84 The first test case is explained in the problem statement above.
     85 
     86 In the second test case, one of the optimal permutations will be $[12,11,\color{blue}{\underline{\color{black}{2}}},4,8,\color{blue}{\underline{\color{red}{\underline{\color{black}{9}}}}},10,6,\color{blue}{\underline{\color{black}{1}}},5,3,\color{blue}{\underline{\color{red}{\underline{\color{black}{7}}}}}]$. The score of this permutation is $(9 + 7) - (2 + 9 + 1 + 7) = -3$. It can be shown that a score greater than $-3$ can not be achieved. Note that the answer to the problem can be negative.
     87 
     88 In the third test case, the score of the permutation will be $(p_1 + p_2 + \ldots + p_9) - p_9$. One of the optimal permutations for this case is $[9, 8, 7, 6, 5, 4, 3, 2, 1]$, and its score is $44$. It can be shown that a score greater than $44$ can not be achieved.
     89 
     90 In the fourth test case, $x = y$, so the score of any permutation will be $0$.