We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Array Construction
  5. Discussions

Array Construction

  • TChalla
     + 2 comments

    PyPy 3 solution

    def Solve(n, s, k, l = 0):
    m = s % n
    if k < (m * (n - m)):
        return False
    if (n - 1) * s < k: 
        return False
    h = n + (s << 6) + (k << 14) + (l << 25)
    if n == 1:
        if k: 
            return False
        dp[h] = s
    if h in dp:
        if dp[h] == -1: 
            return False
        return True
    for i in range(l, s // n + 1):
        p = k - ((s - i) - i * (n - 1))
        if p < 0:
            continue
        if Solve(n - 1, s - i, p, i):
            dp[h] = i
            return True
    dp[h] = -1
    return False

dp = {}
for i in range(int(input())):
    n, s, k = map(int, input().split())
    if Solve(n, s, k):
        i = 0
        h = n + (s << 6) + (k << 14) + (i << 25)
        while h in dp:
            i = dp[h]
            k -= ((s - i) - i * (n - 1))
            n -= 1
            s -= i
            h = n + (s << 6) + (k << 14) + (i << 25)
            print(i, end = " ")
        print("")
    else:
        print(-1)