a.PieProgress.py 1.2 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
  1. import numpy as np
  2. def calcCost(sol, S):
  3. res = 0
  4. for i, n in enumerate(sol):
  5. for j in range(n):
  6. # print('res+=', S[i][j])
  7. res += S[i][j]
  8. if n > 0:
  9. # print('resb+=', pow(2, n), n)
  10. res += pow(n, 2)
  11. return res
  12. def solveRec(N, M, S):
  13. if N == 0:
  14. return []
  15. else:
  16. sol = solveRec(N-1, M, S)
  17. sol.append(0)
  18. minCost = -1
  19. for i in range(N):
  20. if sol[i] >= len(S[i]):
  21. continue
  22. newSol = list(sol)
  23. newSol[i] += 1
  24. newCost = calcCost(newSol, S)
  25. if newCost < minCost or minCost == -1:
  26. minCost = newCost
  27. bestSol = newSol
  28. return bestSol
  29. def solve(N, M, S):
  30. # print("N={0}, M={1}".format(N, M))
  31. # print(S)
  32. sol = solveRec(N,M,S)
  33. # print(sol)
  34. return calcCost(sol, S)
  35. if __name__ == "__main__":
  36. import fileinput
  37. f = fileinput.input()
  38. T = int(f.readline())
  39. for case in range(1, T+1):
  40. N, M = [int(i) for i in f.readline().split()]
  41. S = [sorted([int(i) for i in f.readline().split()]) for x in range(N)]
  42. solution = solve(N, M, S)
  43. print("Case #{0}: {1}".format(case, solution))