The example game described in the problem statement.
Your family has been blessed with chocolate! A huge piece
of chocolate has been given to you and your sister to share.
However, as you gobbled up the large majority last time, your
parents have invented a game to keep things fair (and to keep
you occupied while they hide all the other chocolate). To keep
things interesting, they have given you a rectangular piece of
chocolate, which consists of little squares of both dark
chocolate and white chocolate in a chessboard pattern. While
you and your sister both love dark chocolate, you hate white
chocolate! So, both you and your sister want as much dark
chocolate as possible, while simultaneously obtaining as little
white chocolate as possible. Every dark piece of chocolate you
obtain gives you
meaningless unit of happiness, while a white piece lowers your
happiness by
meaningless unit (and the same holds for your sister). Now,
while you love your sister very much, there is always heavy
competition between siblings, so your goal is to maximize the
difference of your obtained happiness and her obtained
happiness (while she tries to do the opposite, obviously).
The game works as follows. Your parents place a -rectangle of the
aforementioned mixed chocolate on a table. You are situated on
the west side of the table and your sister on the south side.
The side of length is
parallel to the north-south line, while the side of length
is parallel to the
east-west line. Furthermore, the north-west square is made of
dark chocolate. Then, starting with yourself, you take turns
breaking off blocks of chocolate (which you can keep). You can
break off any positive number of entire columns from the west
side, while your sister breaks off any positive number of
entire rows from the south side. You repeat this process until
no more chocolate is left. Your sister is very smart and will
always play the game perfectly.
A game might proceed like this, for example: you and your
sister start with a -rectangle. You decide to break off columns, obtaining dark and white chocolate squares, netting a
happiness of zero. Your sister then breaks off row, obtaining dark and white squares as well, so no
happiness for her either. You then take a single column, which
nets you nothing again, after which your sister decides to
break off one row, which nets her happiness! You then take the last
piece, which makes you lose a unit of happiness, so your total
score is .
See the figure. (Note: the strategies used here might not be
optimal.)
Input
Given are two positive integers and , both at most , the height and width of the
chocolate rectangle.
Output
Output the largest possible difference (in your favour)
between your net happiness and your sister’s net happiness.
Sample Input 1 |
Sample Output 1 |
1 2
|
2
|
Sample Input 2 |
Sample Output 2 |
2 2
|
0
|
Sample Input 3 |
Sample Output 3 |
4 3
|
0
|