CareerCup

Let's work backwards. In order to ensure there's precisely one coin left, we have to be the one to start the pile. That is, if a pile has K coins, and one person picks up K-1 of them, they will win since there is only 1 coin left.

So, we know that the winner of the game is the one who starts the last pile, therefore optimal plays says they will both want to start a pile.

How do you start a pile? Ensure there is just one coin left on the previous pile.

Seems to me, like we have an answer. The person who goes first will always win. They simply have to remove all but 1 coin on the first pile. Their opponent can only remove the final coin because that pile is the leftmost non-empty.

The person who goes first can now repeat this process. Eventually, their opponent will have to pick up the last coin, on the last pile.

The person who goes first will always win except for a case when first pile contain only 1 coin.
In that case first one of both who reach to a pile with coins>1 will win.

For Ex. 1 1 1 2 3 1 1 3
in this case if alice plays first then bob will reach to pile[3] first which is >1,hence bob will win.

Alice will win always except for one case ie as follows
If there are odd number of continuous piles which contain only 1 coin each and this sequence of continuous piles start from the first pile itself then Bob will win.

take N stacks, each having having equal no of elements. then take two arrays alice[ ] and bob[ ]. pop elements from the stack and insert them into alice[ ] and bob [] alternatively. when only one element in the last stack is remaining, check to see which array (alice [ ] or bob[ ]) has more no of elements. the array with the more no of elements wins !!

This is similar to the game of Nim. en dot wikipedia dot org/wiki/Nim

Winner( piles[], n){
totalattempts=0;
for(i=1; i<=n; i++)
totalattempts += piles[i] / i;
if(totalattempts &1)
print Bob winner
else print Alice winner
}

i think if we assume that no pile has 1coin then first player will always in.
as explained above the first player will always pick k-1 coing from ith pile if it has k coins.

> presence of 1 coin in a pile makes it interesting such that winning probability is inverted. i.e. if there is 1 pile having 1 coin then , the player playing second will win.

> so every pile having single coin initially inverts the winning possibility.

the solution should be: count the number of piles with 1 coin and and if they are odd second player wins and if they are even first player wins.

B always wins the game even if number of piles are odd or even

Alice can decide if she wants to play first or second ,which way she can win. If she wants to go first in next pile,then in current pile it should go first if no. of coins in current pile is more than 1 picking all except 1 so that Bob picks the left one and she starts first in next pile. If she wants to go second in next pile,which means Bob should go first in next pile so it must go first in this pile and pick all coins so Bob starts in first place in next pile. By doing so upto first pile if going first is what Alice wishes ,then she wins as she starts the game else Bob wins. so it can be solved using Dynamic Programming.See the code:

#define F 1        //first
#define S 2       //second

bool winner(int arr[],int n)
{
    //arr[i] is no. of coins in ith pile
    //n is the no. of piles
    int Alice[n],state,i;   //doing for alice
    Alice[n-1] = ((arr[n-1] > 1)?F:S);
    for(i = n-2; i >= 0; i--)
    {
        if(Alice[i+1] == F)
        state = ((arr[i] > 1)?F:S);
        else     //Alice going second in (i+1)th pile
        state = F;     //pick all here
        Alice[i] = state;
    }
    //in game Alice is starting first
    if(Alice[0] == F)
    return true;
    else
    return false;      //bob wins
}

Alice wins iff the number of piles with 1 coin is odd. Bob otherwise.
Alice always take A[i]-1 (if A[i] > 1) coins from every pile. If pile i has only one coin then she has to take at least one coin per pile and then Bob will lead the game (he is capable now to take A[j] -1 coin first and leave Alice with just one coin to be picked up. Same Reasoning holds now for Bob.

cnt = number of 1s before the first non-one integer.
if cnt is odd : Bob Wins
else : Alice wins