GreedyPirates

pirates.py

import math
def distributionWithNPirates(n):
  if (n == 1): # Base case
    return [100]
  numberOfVotesRequired = int(math.ceil(n / 2.0))
  # Pirate n will vote for his proposal regardless
  numberOfVotesRequired -= 1
  distributionIfPirateNKilled = distributionWithNPirates(n - 1)
  piratesThatGetTheLeastIfPirateNIsKilled = sorted(range(len(distributionIfPirateNKilled)), key=distributionIfPirateNKilled.__getitem__)
  minimumDistribution = [0] * (n - 1)
  totalBribes = 0
  for pirateToBribe in piratesThatGetTheLeastIfPirateNIsKilled[:numberOfVotesRequired]:
    bribeAmount = distributionIfPirateNKilled[pirateToBribe] + 1
    minimumDistribution[pirateToBribe] = bribeAmount
    totalBribes += bribeAmount
  remainderForPirateN = 100 - totalBribes
  minimumDistribution.append(remainderForPirateN)
  return minimumDistribution

import sys
n = int(sys.argv[1])
print distributionWithNPirates(n)