codeforces-scrape

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

2028B.md (3050B)


      1 Source: https://codeforces.com/problemset/problem/2028/B
      2 
      3 B. Alice's Adventures in Permuting
      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 Alice mixed up the words transmutation and permutation! She has an array $a$ specified via three integers $n$, $b$, $c$: the array $a$ has length $n$ and is given via $a_i = b\cdot (i - 1) + c$ for $1\le i\le n$. For example, if $n=3$, $b=2$, and $c=1$, then $a=[2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1] = [1, 3, 5]$.
     22 
     23 Now, Alice really enjoys permutations of $[0, \ldots, n-1]$$^{\text{∗}}$ and would like to transform $a$ into a permutation. In one operation, Alice replaces the maximum element of $a$ with the $\operatorname{MEX}$$^{\text{†}}$ of $a$. If there are multiple maximum elements in $a$, Alice chooses the leftmost one to replace.
     24 
     25 Can you help Alice figure out how many operations she has to do for $a$ to become a permutation for the first time? If it is impossible, you should report it.
     26 
     27 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $0$ to $n-1$ in arbitrary order. Please note, this is slightly different from the usual definition of a permutation. For example, $[1,2,0,4,3]$ is a permutation, but $[0,1,1]$ is not a permutation ($1$ appears twice in the array), and $[0,2,3]$ is also not a permutation ($n=3$ but there is $3$ in the array).
     28 
     29 $^{\text{†}}$The $\operatorname{MEX}$ of an array is the smallest non-negative integer that does not belong to the array. For example, the $\operatorname{MEX}$ of $[0, 3, 1, 3]$ is $2$ and the $\operatorname{MEX}$ of $[5]$ is $0$.
     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^5$). The description of the test cases follows.
     34 
     35 The only line of each test case contains three integers $n$, $b$, $c$ ($1\le n\le 10^{18}$; $0\le b$, $c\le 10^{18}$) — the parameters of the array.
     36 
     37 Output
     38 
     39 For each test case, if the array can never become a permutation, output $-1$. Otherwise, output the minimum number of operations for the array to become a permutation.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 7
     47 
     48 10 1 0
     49 
     50 1 2 3
     51 
     52 100 2 1
     53 
     54 3 0 1
     55 
     56 3 0 0
     57 
     58 1000000000000000000 0 0
     59 
     60 1000000000000000000 1000000000000000000 1000000000000000000
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 1
     68 50
     69 2
     70 -1
     71 -1
     72 1000000000000000000
     73 ```
     74 
     75 Note
     76 
     77 In the first test case, the array is already $[0, 1, \ldots, 9]$, so no operations are required.
     78 
     79 In the third test case, the starting array is $[1, 3, 5, \ldots, 199]$. After the first operation, the $199$ gets transformed into a $0$. In the second operation, the $197$ gets transformed into a $2$. If we continue this, it will take exactly $50$ operations to get the array $[0, 1, 2, 3, \ldots, 99]$.
     80 
     81 In the fourth test case, two operations are needed: $[1,1,1] \to [0,1,1] \to [0,2,1]$.
     82 
     83 In the fifth test case, the process is $[0,0,0] \to [1,0,0] \to [2,0,0] \to [1,0,0] \to [2,0,0]$. This process repeats forever, so the array is never a permutation and the answer is $-1$.