Last active
December 17, 2015 00:19
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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