MEXanized Array (Codeforces 1870A)
Tags: Math, constructive algorithms

You are given three non-negative integers $$$n$$$, $$$k$$$, and $$$x$$$. Find the maximum possible sum of elements in an array consisting of non-negative integers, which has $$$n$$$ elements, its MEX is equal to $$$k$$$, and all its elements do not exceed $$$x$$$. If such an array does not exist, output $$$-1$$$.The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:  The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.  The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.  The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not. 

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Then follows the description of the test cases.The only line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq n, k, x \leq 200$$$).

Output: For each test case, output a single number — the maximum sum of elements in a valid array, or $$$-1$$$, if such an array does not exist.

Note: In the first test case, the maximum sum is $$$7$$$, and one of the valid arrays is $$$[0, 1, 2, 2, 2]$$$.In the second test case, there are no valid arrays of length $$$n$$$.In the third test case, the maximum sum is $$$57$$$, and one of the valid arrays is $$$[0, 1, 28, 28]$$$.

Sample Inputs:
9
5 3 3
4 7 5
4 2 28
12 10 6
57 51 122
200 1 200
2 2 1
3 2 1
4 7 10

Sample Outputs:
7
-1
57
-1
2007
39800
1
2
-1

Solution (Python):
for _ in range(int(input())):
    (n, k, x) = map(int, input().split())
    if n >= k and k <= x + 1:
        print((k - 1) * k // 2 + (n - k) * (x if x != k else x - 1))
    else:
        print(-1)

Solution (Python):
for _ in range(int(input())):
    (n, k, x) = map(int, input().split())
    if k > x + 1 or n < k:
        print(-1)
    elif k == x:
        print((x - 1) * (n - k) + (k - 1) * k // 2)
    else:
        print(x * (n - k) + k * (k - 1) // 2)

Solution (Python):
R = []
for i in range(int(input())):
    (n, k, x) = map(int, input().split())
    if n < k or k - 1 > x:
        R.append(-1)
        continue
    else:
        p = k - 1
        if k == x:
            x = k - 1
        R.append(int(p * (p + 1) / 2 + (n - k) * x))
for i in R:
    print(i)