We have given, n coins with each having some face value k.
Now, there are two players, nick and james playing the game with alternating turn. In each turn, a player can choose any coin and replace it with more than one coins having sum of face value equal to replaced coin. Each of the new coins must be having same equal face value. Integer p is also given, which is the limit denotes that a player can't use the coin for replacement having face value less than p. All players have given unlimited number of coins with unlimited face values.
So sample input will be n,k,p and where n is no. of coin with each face value is k and limit p is described above. If both play optimally, and nick starts first who will win the game. A player loose the game if he can't able to play its turn (means can't able to replace any of the coin).
Is it game of nim problem or DP? How can we solve this?
This is definitely the kind of game which Nim is the right way to think about: it is a two-player game, it is perfect information meaning both players know the full game state at all times, there is no element of chance, it is an impartial game meaning the same moves are available to both players, and you lose if you are unable to move. So the Sprague–Grundy theorem applies to this game; every position in the game is equivalent to a nimber. We can solve a position to find who will win given optimal play, by computing the nimber for the position; a position is a first-player-win if and only if the nimber is not zero.
However, that turns out to be completely unnecessary for this specific problem, because all of the coins in the starting position have the same value.
If there are an even number of coins, then player 2 wins by a mirror strategy. Match the coins in pairs, and then whatever move the opponent plays on one coin, mirror that move on the other one. Match the resulting coins in pairs and continue mirroring on them.
If there are an odd number of coins, then player 1 wins by splitting one of them into coins of the smallest possible value >= p, such that no more moves can be made on those coins. Then player 1 adopts the mirror strategy given above for the remaining coins, which there are an even number of.
There is a special case: if the coins' face value is already such that player 1 cannot make any move, then player 2 always wins, regardless of whether the number of coins is odd or even.
So the answer is: player 1 wins if and only if n is odd and k has a factor >= p. Clearly there is not going to be a more efficient solution.