0

You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

e.g

5 bricks

999 1 1 1 0

maximum score you can get = 1001 (choose first three bricks)

if 5 bricks are :

0 1 1 1 999

maximum score will be : 999 (choose first brick then friend have to choose next 3, then you choose last brick).

if there are 6 bricks say:

1 2 4 8 9 100

my maximum score will be 103(1+2+100) . As I will choose initially 2 bricks 1,2 . Then my friend will have maximum score if he will choose 4,8 and 9 . Then I will choose remaining 100 .

How to approach such problem ? It always exhaust my mind .

user139256
  • 3
  • Why does the frind have to choose the next 3 bricks in your second example ? What about the numbers ? Why they are 0,1 and 999 ? – callculus42 Oct 02 '15 at 05:30
  • because both me and my friends try to maximize our score. If I choose first number (i.e 0) in 2nd example , then friend can choose at most 3 brick He will choose next 3 bricks because it is the only way he can maximize his profit (1+1+1 = 3) . Then I will choose remaining brick i.e 999 . And numbers are just to give example . It can be any number . – user139256 Oct 02 '15 at 05:37

0 Answers0