PROBLEM LINK-: CLICK HERE
PROBLEM SETTERS-: @aliencoder_07 @dcpandey
EDITORIALIST-: @dcpandey
DIFFICULTY-: Medium
PREREQUISITES-: Dynamic Programming
PROBLEM-: Zen and Zenny decided to play a game.Game consist of P apples in a container B and they have also an array A with N elements.Game is played as follows , each player take turn to pick an element from the array and removes that number of apples from the container B, the player who is unable to remove the apples from the container looses the game. Zen start the game and if both players play optimally , your task is to determine the winner.
EXPLANATION-: If you are at position ‘x’, then you can win by forcing the opponent to be in a losing position if any of the set elements lead to a position ‘x-a[i]’ where he loses(or not wins). Thus we obtain a recursion in which memorisation would help.
SOLUTION-: CLICK HERE