Stick Game Problem | faceprep

Stick Game Problem | faceprep

The stick game problem is described as follows.

Stick Game Problem


After winning gold and silver in Indian Computing Olympiad 2014, Arun Gupta and Mani Iyer want to have some fun.

Now they are playing a game on a grid made of n horizontal and m vertical sticks.

An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.In the grid shown below,n = 3 and m = 3. There are n+m= 6 sticks in total. There are nm = 9 intersection points, numbered from 1 to 9.

The rules of the game are very simple. The players move in turns. Arun Gupta won gold, so he makes the first move.

During his/her move, a player must choose any remaining intersection point and remove from the grid all sticks which pass through this point.

A player will lose the game if he cannot make a move (i.e. there are no intersection points remaining on the grid at his move).

Assume that both players play optimally. Who will win the game?

Input Format:

The first line of input contains two space-separated integers,n, and m(1 ?n,m? 100).

Output Format:

Print a single line containing “Arun Gupta” or “Mani Iyer” (without the quotes), depending on the winner of the game.


Sample Input 1:

2 2


Sample Output 1:

Mani Iyer


Sample Input 2:

2 3


Sample Output 2:

Mani Iyer


Sample Input 3:

3 3


Sample Output 3:

Arun Gupta


Explanation of the first sample:

The grid has four intersection points, numbered from 1 to 4.

If Arun Gupta chooses intersection point 1, then he will remove two sticks (1 – 2 and 1 – 3). 

Now there is only one remaining intersection point (i.e. 4). Mani Iyer must choose it and remove both remaining sticks. After his move, the grid will be empty.

In the empty grid, Arun Gupta cannot make any move, hence he will lose.

Since all 4 intersection points of the grid are equivalent, Arun Gupta will lose no matter which one he picks.


face prep pro ad bannerClick here to learn more about FACE Prep PRO


Algorithm – Stick game problem

  • Input m and n grids.
  • if(n < m)
  • res = n
  • else
  • res = m
  • if(res % 2 == 0)
  • Print “Mani Iyer”
  • else
  • Print “Arun Gupta”


Program for the Stick game problem

@@coding::1@@


Program for the Stick game problem using pointers

#include<stdio.h>n#include<stdlib.h>nint main()n{nint n,m,x;nscanf(“%d %d”,&n,&m);nif(n<m)nx=n;nelsenx=m;nif(x%2==0)nprintf(“Mani Iyer”);nelsenprintf(“Arun Gupta”);nreturn 0;n}n


Stick Game Problem