Alice is madly in love with Bob and she hopes to impress him by beating him in yet another chocolate game.
Alice and Bob are supergenius, perfectly rational grandmaster prodigies who always make the optimal move in any game they play. Alice considers a game to be WINNABLE if there is some strategy she can follow so that she is guaranteed to win no matter what Bob does (so long as Alice plays correctly). Alice considers a game UNWINNABLE if Bob has a strategy he can follow so that she is guaranteed to lose no matter what she does (so long as Bob is playing correctly).
Bob is madly in love with Cindy, so he places $$$M$$$ cookies in the left pile and $$$N$$$ cookies in the right pile, since $$$M$$$ and $$$N$$$ are Cindy's favorite numbers.
Cindy is madly in love with Alice, so she will rig the game such that it will be WINNABLE for Alice, by taking some number of cookies from each pile. So that Bob does not notice the changes, she can only take at most $$$X$$$ cookies from the left pile, and at most $$$Y$$$ cookies from the right pile. Cindy can also choose not to take any cookies from either pile. You are also assured that $$$X < M$$$ and $$$Y < N$$$.
How many different ways can Cindy rig the game in Alice's favor? Formally, count the number of ordered pairs of integers $$$(x,y)$$$ such that $$$0 \leq x \leq X$$$ and $$$0 \leq y \leq Y$$$, and a game that initially begins with piles of size $$$M-x$$$ and $$$N-y$$$ is WINNABLE for Alice.
Input consists of a single line with four space-separated integers $$$M$$$, $$$N$$$, $$$X$$$, and $$$Y$$$.
Output a single integer, the number of different ways that Cindy can rig the game in Alice's favor.
It is recommended that Python users submit to PyPy for this problem.
$$$0 \leq X < M$$$
$$$0 \leq Y < N$$$
Subtask 1 (30 points):
$$$1 \leq M,N \leq 10$$$
Subtask 2 (20 points):
$$$1 \leq M,N \leq 100$$$
Subtask 3 (20 points):
$$$1 \leq M,N \leq 1000$$$
Subtask 4 (15 points):
$$$1 \leq M,N \leq 5\cdot 10^4$$$
Subtask 5 (15 points):
$$$1 \leq M,N \leq 5\cdot 10^6$$$
5 10 1 2
4
10 10 9 9
66
In the first sample test case, suppose Cindy took $$$x=0$$$ cookies from the left pile and $$$y=1$$$ cookies from the right pile. Then, the game will have pile sizes $$$5$$$ and $$$9$$$, which we can show is WINNABLE for Alice.
First, she eats $$$6$$$ cookies from the right pile, which she can do because $$$9-6 = 3$$$ and $$$3$$$ is a positive divisor of $$$9$$$.
Now, the pile sizes are $$$5$$$ and $$$3$$$. If Bob eats from the left pile, his only choice is to eat $$$4$$$ cookies from it; then, Alice eats $$$2$$$ cookies from the right pile. If Bob eats from the right pile, his only choice is to eat $$$2$$$ cookies it; then, Alice eats $$$4$$$ cookies from the left pile.
In either case, there is only $$$1$$$ cookie left in each pile on Bob's turn, so he loses.
We can show that the full list of solutions are $$$(0,0)$$$, $$$(0,1)$$$, $$$(0,2)$$$, and $$$(1,2)$$$ for the first sample test case.
Name |
---|