#P11384. Maximum Removals in Even Sum Game
Maximum Removals in Even Sum Game
Maximum Removals in Even Sum Game
Bajtazar loves to play the following single-player game. He writes down all natural numbers from a to b on a board, forming the sequence:
$$a,\; a+1,\; a+2,\; \ldots,\; b-1,\; b$$
He then performs zero or more operations. In each operation, he chooses two numbers still on the board such that their sum is even, and removes both of them from the board. The objective of the game is to remove as many elements as possible. Your task is to help Bajtazar compute the maximum number of elements that can be removed.
Hint: The sum of two numbers is even if and only if both numbers are even or both are odd. Therefore, separately count the number of even and odd numbers in the sequence and pair them as much as possible.
inputFormat
The input consists of a single line containing two integers a and b (1 ≤ a ≤ b ≤ 10^9
) separated by a space.
a is the starting number and b is the ending number of the sequence.
outputFormat
Output a single integer — the maximum number of elements that can be removed from the board.
sample
1 2
0