Skip to content

Instantly share code, notes, and snippets.

@dashohoxha
Last active December 17, 2015 00:19
Show Gist options
  • Save dashohoxha/5520262 to your computer and use it in GitHub Desktop.
Save dashohoxha/5520262 to your computer and use it in GitHub Desktop.
Solution for Problem A (Osmos), of Round1B, CodeJam 2013: https://code.google.com/codejam/contest/2434486/dashboard#s=p0
# Solution for Problem A (Osmos), of Round1B, CodeJam 2013:
# https://code.google.com/codejam/contest/2434486/dashboard#s=p0
def solve(a, mots)
# If the list of mots is empty, we are done.
return 0 if mots == []
# If a is 1, the only way to make it solvable
# is to delete all the mots, because it cannot
# absorb any mot and cannot inreasi its length.
return mots.length if a == 1
# If a > mots[0], we can absorb it
# without any additions or deletions.
if a > mots[0]
return solve(a + mots[0], mots[1..-1])
end
### At this point we have a <= mots[0] .
### We can either add mots (in front of mots[0])
### until we can absorb it, or delete all the
### remaining mots. Deletting just the first mot
### will not improve the situation, since the next
### one is not smaller than it. The same goes for
### deletting any other mots.
# Let's find the number of mots we have to insert
# in order to absorb mots[0].
nr = 0 # nr of mots we have to insert
while a <= mots[0]
nr += 1
a += a - 1
end
# If number of motes we have to insert is greater
# than the remaining mots, we better just delete
# the remaining mots, and then we are done.
return mots.length if nr >= mots.length
# Find the number of changes if we absorb the first mot and continue
nr1 = solve(a + mots[0], mots[1..-1])
# Return the smallest number of deleting all mots
# or absorbing the first one and continuing.
return [nr + nr1, mots.length].min
end
T = gets.to_i
for t in 1..T
a, n = gets.chomp.split.map &:to_i
mots = gets.chomp.split.map &:to_i
mots.sort!
puts "Case ##{t}: #{solve a, mots}"
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment