Player A and Player B play a game. On the middle of the table there is a pot ful
ID: 655504 • Letter: P
Question
Player A and Player B play a game. On the middle of the table there is a pot full of N apples of different weights. Player A starts first and choose an apple and start eating it. Losing no time player B do the same. When a player eats the whole apple, without losing time repeat the same procedure. In case both player have eaten the apple at the same time, Player A still have the advantage of choosing first. Note that both players eat with same speed
What apple should the Player A choose at first to ensure that with right tactics he'll eat as much as grams of apples possible if the player B plays optimally?
I thought that choosing the smallest or the biggest apple should do the job, but there are specific cases when this doesn't work.
This is C++ contest problem, so there should be a nice solution to this. I think that brute force maybe provide a solution, but this will require much time, because the number of apples is up to 10000.
I would rather like some hint on how to approach this question, how to find the optimal tactic or intuition rather than a code.
Explanation / Answer
A non-recursive answer: divide the apples into two piles, so they are as close as possible equal. Then, eat the smallest apple in the largest pile.
Halving the pile is left to the reader, but remember that the difference in pile size can be no larger than the smallest apple in the largest pile; if it is any larger, then moving that apple to the other pile will give you a closer answer. It can also not be larger than the difference between an apple in the larger pile, and the next smaller apple in the smaller pile - if the larger pile contains a 600 gramme apple, and the smaller pile contains a 500 gramme apple, and the difference between the two piles is more than 100 grammes, then you could swap those two apples and get closer.
For example, if you have 300+400+500 gramme, you should divide them into two piles, each being as close as possible to (300+400+500)/2=600 gramme. This comes out as one being 500 gramme, the other being 300+400=700 gramme. Eat the smallest apple from the largest (700 gramme) pile - i.e. the 300 gramme apple.
In the case of 100+200+300+900, the closest you can get to two piles of 750 grammes each is one pile of 900, the other of 600, eat the largest (and only) apple from the largest (900 gramme) pile.