Skip to content

Instantly share code, notes, and snippets.

@hickford hickford/osmos.py
Created May 7, 2013

Embed
What would you like to do?
Attempted solution to Google Code Jam's Osmos problem. Turned out to be incorrect. https://code.google.com/codejam/contest/2434486/dashboard
#!python
# https://code.google.com/codejam/contest/2434486/dashboard
# Armin is playing Osmos, a physics-based puzzle game developed by Hemisphere Games. In this game, he plays a "mote", moving around and absorbing smaller motes.
# lemma if we delete a mote size x, we should delete all motes greater than size x
import fileinput
f = fileinput.input()
T = int(f.readline())
def solve(A, motes):
motes.sort()
N = len(motes)
best_deletion_strategy = N # delete all
if A == 1:
# can't eat any ever.
return N
operations = 0
while motes:
m = motes.pop(0)
if m < A:
# eat!
A += m
else:
# too big to eat.
# what if we deleted? we'd delete it and all others bigger (by the lemma)
deletion_strategy = operations + 1 + len(motes)
best_deletion_strategy = min(best_deletion_strategy, deletion_strategy)
# Let's add motes until we can eat it.
while A <= m:
A += A-1
operations += 1
return min(operations, best_deletion_strategy)
for case in range(1,T+1):
A, N = [int(x) for x in f.readline().split()]
motes = [int(x) for x in f.readline().split()]
assert len(motes) == N
answer = solve(A, motes)
print "Case #%d: %d" % (case, answer)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.