Advertisement
MagicWinnie

4

Jan 14th, 2022
1,101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.45 KB | None | 0 0
  1. #
  2. # Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  3. # Date: 2013.11.15
  4. #
  5. # Comment: O(d^2), try only +-500, no overflow
  6. #   looks at pair and gets the third value optimal possible
  7. #
  8.  
  9. import sys
  10.  
  11. NAME = "sweets"
  12.  
  13. inf = open(NAME + ".in", "r")
  14. out = open(NAME + ".out", "w")
  15.  
  16. n, a, b, c = list(map(int, inf.readline().split()))
  17.  
  18. def relax(x, y, z, tmp_shift):
  19.   global best, shift, rx, ry, rz
  20.   tmp = x * y * z
  21.   if (tmp > best or (tmp == best and tmp_shift < shift)):
  22.     best, rx, ry, rz, shift = tmp, x, y, z, tmp_shift
  23.  
  24. x0 = n // (3 * a)
  25. y0 = n // (3 * b)
  26. z0 = n // (3 * c)
  27. best = x0 * y0 * z0
  28. shift = 0
  29. rx, ry, rz = x0, y0, z0
  30.  
  31. M = 500
  32. r = range(-M, M + 1)
  33.  
  34. dx = dy = dz = 0
  35.  
  36. for dx in r:
  37.   for dy in r:
  38.     x, y, z = x0 + dx, y0 + dy, z0 + dz
  39.     if ((1 <= x) and (1 <= y) and (1 <= z)):
  40.       if (a * x + b * y <= n): relax(x, y, (n - a * x - b * y) // c, max(abs(dx), abs(dy)))
  41.  
  42. for dy in r:
  43.   for dz in r:
  44.     x, y, z = x0 + dx, y0 + dy, z0 + dz
  45.     if ((1 <= x) and (1 <= y) and (1 <= z)):
  46.       if (c * z + b * y <= n): relax((n - c * z - b * y) // a, y, z, max(abs(dz), abs(dy)))
  47.  
  48. for dx in r:
  49.   for dz in r:
  50.     x, y, z = x0 + dx, y0 + dy, z0 + dz
  51.     if ((1 <= x) and (1 <= y) and (1 <= z)):
  52.       if (a * x + c * z <= n): relax(x, (n - a * x - c * z) // b, z, max(abs(dx), abs(dz)))
  53.  
  54. print(rx * a, ry * b, rz * c, file=out)
  55. sys.stderr.write("optimal shift: " + str(shift) + "\n")
  56.  
  57. inf.close()
  58. out.close()
  59.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement