3021. Alice and Bob Playing Flower Game
Description
Alice and Bob are playing a turn-based game on a circular field surrounded by flowers. The circle represents the field, and there are x
flowers in the clockwise direction between Alice and Bob, and y
flowers in the anti-clockwise direction between them.
The game proceeds as follows:
- Alice takes the first turn.
- In each turn, a player must choose either the clockwise or anti-clockwise direction and pick one flower from that side.
- At the end of the turn, if there are no flowers left at all, the current player captures their opponent and wins the game.
Given two integers, n
and m
, the task is to compute the number of possible pairs (x, y)
that satisfy the conditions:
- Alice must win the game according to the described rules.
- The number of flowers
x
in the clockwise direction must be in the range[1,n]
. - The number of flowers
y
in the anti-clockwise direction must be in the range[1,m]
.
Return the number of possible pairs (x, y)
that satisfy the conditions mentioned in the statement.
Example 1:
Input: n = 3, m = 2 Output: 3 Explanation: The following pairs satisfy conditions described in the statement: (1,2), (3,2), (2,1).
Example 2:
Input: n = 1, m = 1 Output: 0 Explanation: No pairs satisfy the conditions described in the statement.
Constraints:
1 <= n, m <= 105
Solutions
Solution 1: Mathematics
According to the problem description, in each move, the player will choose to move in a clockwise or counterclockwise direction and then pick a flower. Since Alice moves first, when $x + y$ is odd, Alice will definitely win the game.
Therefore, the number of flowers $x$ and $y$ meet the following conditions:
- $x + y$ is odd;
- $1 \le x \le n$;
- $1 \le y \le m$.
If $x$ is odd, $y$ must be even. At this time, the number of values of $x$ is $\lceil \frac{n}{2} \rceil$, the number of values of $y$ is $\lfloor \frac{m}{2} \rfloor$, so the number of pairs that meet the conditions is $\lceil \frac{n}{2} \rceil \times \lfloor \frac{m}{2} \rfloor$.
If $x$ is even, $y$ must be odd. At this time, the number of values of $x$ is $\lfloor \frac{n}{2} \rfloor$, the number of values of $y$ is $\lceil \frac{m}{2} \rceil$, so the number of pairs that meet the conditions is $\lfloor \frac{n}{2} \rfloor \times \lceil \frac{m}{2} \rceil$.
Therefore, the number of pairs that meet the conditions is $\lceil \frac{n}{2} \rceil \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lceil \frac{m}{2} \rceil$, which is $\lfloor \frac{n + 1}{2} \rfloor \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lfloor \frac{m + 1}{2} \rfloor$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 |
|
1 2 3 4 5 |
|
Solution 2: Mathematics (Optimized)
The result obtained from Solution 1 is $\lfloor \frac{n + 1}{2} \rfloor \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lfloor \frac{m + 1}{2} \rfloor$.
If both $n$ and $m$ are odd, then the result is $\frac{n + 1}{2} \times \frac{m - 1}{2} + \frac{n - 1}{2} \times \frac{m + 1}{2}$, which is $\frac{n \times m - 1}{2}$.
If both $n$ and $m$ are even, then the result is $\frac{n}{2} \times \frac{m}{2} + \frac{n}{2} \times \frac{m}{2}$, which is $\frac{n \times m}{2}$.
If $n$ is odd and $m$ is even, then the result is $\frac{n + 1}{2} \times \frac{m}{2} + \frac{n - 1}{2} \times \frac{m}{2}$, which is $\frac{n \times m}{2}$.
If $n$ is even and $m$ is odd, then the result is $\frac{n}{2} \times \frac{m - 1}{2} + \frac{n}{2} \times \frac{m + 1}{2}$, which is $\frac{n \times m}{2}$.
The above four cases can be combined into $\lfloor \frac{n \times m}{2} \rfloor$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 |
|