## Capgemini Interview Question for Interns

- 0of 0 votes

Answerplease help me out!!..Its not striking me.

- guptaabhinav206 January 22, 2014 in India

Ramesh and Suresh get a box full of five stars on lottery each. Since both the boxes need not have the same number of chocolates, they decide to play a game. The winner gets to have both the boxes of chocolates. They play alternatively and Suresh starts the game. Given the number of chocolates in both the boxes, let them be c1 and c2, the player takes either c1 or c2 number of chocolates and divide the remaining box of chocolates to two boxes (these two boxes need not have the same number of chocolates). The player who cannot make such a move loses. Input

First line of input contains a number T(1<=T<=1000), the number of test cases. Then follows T lines each containing two space separated integers c1 and c2

(1<=c1<=c2<=10000).

Output For each test case print "Ramesh" or "Suresh" depending on who is the winner.

Input: 2 3 1 4 5

Output: Ramesh Suresh| Report Duplicate | Flag | PURGE

Capgemini Intern Algorithm

**Country:**India

**Interview Type:**In-Person

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Not sure if I understand the problem correctly, here's what I gather: The game starts with two boxes, each containing different amount (not 0) of chocolates. At each turn a player takes all the chocolates from one of the boxes and divides the chocolates in the other box to two non-equal boxes (in terms of chocolate amount). If at some turn the player cannot select a box and divide the other box into two non-equal sized boxes then this player loses.

The solution to the problem as I described above is as follows:

To see why this solution works, let us define the following:

- IvgenyNovo January 22, 2014N - The set of natural numbers (N={1,2,3,...})

L = {1+3k | k in N} union {1,2}

W = N\L = {3k | k in N} union {3k+2 | k in N}

Claim: Given (c1,c2) in N^2 (the boxes) where c1!=c2 and a player x whose turn is the current turn, the following hold:

1. If c1 and c2 are in L then the second player has a winning strategy.

2. If c1 in W or c2 in W then player x has a winning strategy.

Proof: Using induction on n=max{c1,c2}.

Base: To cover the base we can check the following cases:

n=2 : (c1,c2)=(1,2),(2,1). In all these cases no matter which box player x takes, he cannot divide the second box to two non-equal boxes (1 cannot be divided at all and 2 can only be divided to two equal boxes containg one chocolate).

n=3: In this case at least one of the boxes contains 3 chocolates. Player x takes the second box to himself and divides the remaining 3 chocolates to two boxes: (1,2). Using the case of n=2 we deduce that the second player loses no matter what he does and hence player x wins.

Induction step: Assume correctness for every 3<=k<n and let us prove correctness for n=max{c1,c2}. Let us consider the following cases:

1. n in W. There are two possibilities here:

1.1. n = 3m = 3*(m-1) + 3 = (3*(m-1) + 2) + 1. In this case player x takes the box which does not contain n chocolates. He then divides the remaining n chocolates to the following boxes: (3*(m-1)+2,1) which by the induction assumption means that the second player loses.

1.2. n = 3m+2 = 3m+1 + 1. In this case player x takes the box which does not contain n chocolates. He then divides the remaining n chocolates to the following boxes: (3m+1,1) which by the induction assumption means that the second player loses.

2. n in L but the other box contains k>=1 chocolates and k is in W. In this cases we use the same proof as in (1) to show that player x has a winning strategy (just replace n with k).

3. n in L and the other box contains k>=1 chocolates and k is in L as well. For the sake of contradiction, assume that there exist a,b in L such that n = a+b. By the definition of L:

3.1. a = 1 + 3m, b = 1 + 3l where m,l>=1. In this case n = a+b = 1+3m+1+3l=3(l+m)+2 in W which is a contradiction to the fact that n is in L.

3.2. a = 1 + 3m, b = 1. In this case n = a+b = 3m+2 in W and yet again we get a contradiction to the fact that n is in L.

3.3. a = 1 + 3m, b = 2. In this case n = a+b = 3m+3 = 3(m+1) in W which is also a contradiction to the fact that n is in L.

3.4. The other cases are similar and result in a contradiction as well (notice that the case of a=2 and b=2 is not possible).

3.1 - 3.4 show that it is not possible to divide n chocolates to two non-equal boxes with both of them containing a and b chocolates respectively where a and b are in L. The same applies for k (the number of chocolates in the other box) as well. This observation combined with the induction assumption implies that no matter what player x does the second player will win regardless (he has a winning strategy for every move player x makes). Thus, in this case the second player has a winning strategy.

This completes the proof.

An alternative (but expensive) approach can be to use dynamic programming in order to calculate the winner (basically, in each turn the player selects the best move for himself out of all possible moves).