Internet Problem Solving Contest

IPSC 2006

Solution to Problem G – Gotta Pick'em All

Both the easy and the hard subproblem can be solved by calculating the answers for small values of N (let's say, up to N=20) by brute-force, looking at the results and guessing how will the progression continue.

Our approach will be somewhat more rigorous:

Let's take any fixed number of cards (N) and assume that we've picked as many cards as possible. Let M be the greatest one among them.

In both cases, M is obviously at most equal to N. Thus, the upper bound on the number of cards that can be taken is floor(N/2)+1. Taking the cards ceil(N/2),ceil(N/2)+1, ..., N shows that this bound can be attained. Therefore, the answer to the easy subproblem is floor(N/2)+1.

The hard subproblem is a bit more tricky. We'll consider two cases: