DMOPC '22 Contest 3 P1 - Holiday Colouring

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

To celebrate New Year's, Red and Green are playing a traditional holiday colouring game on an N by M grid of gray squares. Red uses a red crayon, and Green uses a green crayon. Both players take turns colouring gray squares, with Red going first. For each player on their first turn, they can colour any gray square. On every turn after their first, they must colour a gray square which is horizontally or vertically touching another square of the colour they use, or pass the turn if they are unable to move. The game ends when both players are unable to move. The score of the player is the number of squares they have coloured. Assuming both players play optimally to maximize their scores, find the scores of both players.


1 \le N, M \le 10^9

Subtask 1 [20%]

N = 1

Subtask 2 [80%]

No additional constraints.

Input Specification

The first and only line contains 2 space-separated integers N and M.

Output Specification

Output two space-separated integers R and G, which represent the scores of Red and Green respectively when they play optimally to maximize their scores.

Sample Input

3 2

Sample Output

3 3


There are no comments at the moment.