Alice mixed up the words transmutation and permutation! She has an array a specified via…
- User
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 ai=b⋅(i−1)+c for 1≤i≤n . For example, if n=3 , b=2 , and c=1 , then a=[2⋅0+1,2⋅1+1,2⋅2+1]=[1,3,5] .
Now, Alice really enjoys permutations of [0,…,n−1] ∗ and would like to transform a into a permutation. In one operation, Alice replaces the maximum element of a with the MEX † of a . If there are multiple maximum elements in a , Alice chooses the leftmost one to replace.
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.
∗ 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).
† The MEX of an array is the smallest non-negative integer that does not belong to the array. For example, the MEX of [0,3,1,3] is 2 and the MEX of [5] is 0 .
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105 ). The description of the test cases follows.
The only line of each test case contains three integers n , b , c (1≤n≤1018 ; 0≤b , c≤1018 ) — the parameters of the array.
Output 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.
Example InputCopy 7 10 1 0 1 2 3 100 2 1 3 0 1 3 0 0 1000000000000000000 0 0 1000000000000000000 1000000000000000000 1000000000000000000 OutputCopy 0 1 50 2 -1 -1 1000000000000000000 Note In the first test case, the array is already [0,1,…,9] , so no operations are required.
In the third test case, the starting array is [1,3,5,…,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,…,99] .
In the fourth test case, two operations are needed: [1,1,1]→[1,1,0]→[1,2,0] . type code in c++ please type quite shortest code
- Assistant
To solve this problem, we need to determine the minimum number of operations required to transform the given array
ainto a permutation of[0, 1, 2, ..., n-1]. The arrayais defined by the formulaa[i] = b*(i-1) + cfor1 ≤ i ≤ n.Alice's operation involves replacing the maximum element of the array with the MEX (Minimum EXcluded value) of the array. If the array can be transformed into the desired permutation, we need to calculate the minimum number of such operations. If it's impossible, we return
-1.Key Observations:
- Array Initialization: The initial array is an arithmetic progression, given by
a[i] = b*(i-1) + c. - MEX Definition: The MEX of an array is the smallest non-negative integer not present in the array.
- Permutation Requirements: For the array to be a permutation of
[0, 1, ..., n-1], all these numbers must be present exactly once.
Cases to Consider:
-
When
n = 1:- If
c = 0, the array is already[0], so no operations are needed. - If
c ≠ 0, one operation is required to replace the element with0.
- If
-
When
b = 0:- If
n > 1andc = 0, it's impossible to achieve a permutation since all elements are0. - If
n > 1andc > 0, the number of operations depends on whethercis less than or equal ton-1.- If
c ≤ n-1, the number of operations needed isn-1. - If
c > n-1, the number of operations needed isn.
- If
- If
-
General Case (
b > 0andn > 1):- The number of operations required is calculated using the formula
ceil((c + (b-1)*(n-1)) / b). - This formula ensures that the arithmetic progression can be transformed into a permutation by systematically replacing the maximum element with the appropriate MEX.
- The number of operations required is calculated using the formula
Implementation:
We handle large numbers using
unsigned __int128to prevent overflow, and we convert the result to a string for output purposes.Final Code:
#include <bits/stdc++.h> using namespace std; // Function to convert unsigned __int128 to string string uint128_to_string(unsigned __int128 x){ if(x == 0) return "0"; string s; while(x > 0){ char c = '0' + (x % 10); s += c; x /=10; } reverse(s.begin(), s.end()); return s; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ unsigned long long n, b, c; cin >> n >> b >> c; if(n ==1){ if(c ==0){ cout << "0\n"; } else{ cout << "1\n"; } } else{ if(b ==0){ if(c ==0){ cout << "-1\n"; } else{ if(c <= n-1){ cout << to_string((unsigned long long)(n-1)) << "\n"; } else{ cout << to_string((unsigned long long)(n)) << "\n"; } } } else{ __int128 numerator = (__int128)c + ((__int128)(b-1)) * ((__int128)(n-1)); // To compute ceil(numerator / b), which is (numerator + b -1 ) / b __int128 temp = numerator + (__int128)(b -1); unsigned __int128 ans = temp / b; // Convert ans to string string ans_str = uint128_to_string(ans); cout << ans_str << "\n"; } } } } - Array Initialization: The initial array is an arithmetic progression, given by