PROBLEM LINKS
Author:SRIKANT BADRI
DIFFICULTY:
SIMPLE
PROBLEM:
Two players are breaking a chocolate bar of size N×M into pieces. A player’s turn consists of choosing one piece and breaking it in two. Which player wins the game?
EXPLANATION:
This is a classic mathematical exercise. Notice that the number of pieces of chocolate increases by 1 in each player’s turn; initially, there’s only 1 piece and when the game ends, there have to be NM pieces (otherwise, there’s still some piece that can be broken). So the outcome of the game only depends on who makes the NM-th move - or equivalently, on the parity of NM. If NM is odd, the first player has to make the NM-th move and loses; otherwise, the second player has to make it and loses. Of course, this works in constant time.