# Code Jam 2010 Africa – Problem C

Whoa, that was a tough problem. Ironically it’s called Qualification Round:

You’ve just advanced from the Qualification Round of Google Code Jam Africa 2010, and you want to know how many of your fellow contestants advanced with you. To give yourself a challenge, you’ve decided only to look at how many people solved each problem.

The Qualification Round consisted of P problems; the ith problem was fully solved by Scontestants. Contestants had to solve C problems in order to advance to the next round. Your job is to figure out, using only that information, the maximum number of contestants who could have advanced.

Well, at first it seems pretty simple, but there is quite some math involved. The first case of the example input is easy to solve, but the second will most likely get you scratching your head thinking “where the #\$%* that number came from” (at least I did). 🙂 Well the secret is that you should not look at the inputs as they are, but instead, find the maximum amount of solved problem combinations there are.

I studied a bit but still could not solve it, and surrendered by checking the contest analysis. It was quite complicated to understand, until they wrote about a clever solution from the winning candidate: it consisted in lowering the possible scores to max at the division of the scores by the amount of needed problems. Just do it (don’t ask why) until there are no scores over the result of that division. That same result will be the answer. Creepy! Python code time:

```for case in range(1,int(raw_input())+1):          # For all test cases
info = map(int, raw_input().split(" "))       # Get test case information
problems = info[0]                            # Fetch number of problems
needed = info[1]                              # Fetch number of needed problems to pass
results = info[2:]                            # Fetch results for each problem

qualified = 0                                 # Initialize our results

if (problems == needed):                      # For this case, we can expect
results.sort()                            # as many contestants as the
qualified = results[len(results)-needed]  # least solved problem

else:                                         # For this case, we use a solution
out = False                               # similar to the winning one
while not out:
out = True
qualified = sum(results)/needed       # Reduce the number of possible qualifiers
for i in range(len(results)):         # And for all results
if results[i] > qualified:        # Limit their values to the current qualifiers
results[i] = qualified
out = False                   # Until they all "match" the qualifiers number

print "Case #%d: %s" % (case, str(qualified)) # Report results
```

Interestingly enough, this code is smaller than the last, and solves a more complicated problem (at least in my opinion). I don’t think I could have done a better job on this one. 🙂 That’s the beauty in learning!