Plate Parity
InterviewTime limit1sMemory limit512 MB
Count integers in [A, B] whose rightmost nonzero digit is odd versus even, where A and B go up to 10^16.
- Level
Medium4 of 10
- Topics
- Math, Implementation, Combinatorics, Prefix sum
- Solved
- No attempts yet
Problem
Odd-even rationing is a common method to restrict resource consumption to half the population on any given day. For example, a private vehicle is allowed to drive, park, or buy gasoline only on alternating days depending on whether its license plate is odd or even. Jakarta enforced this policy to reduce traffic jams during the 2018 Asian Games: odd-plate private vehicles could drive on certain restricted roads during certain hours only on odd dates, and even-plate private vehicles only on even dates.
Despite its effectiveness, some people do not know that zero (0) is an even number, which can cause confusion. That is why we need to investigate a variant of odd-even rationing.
In this problem, whether a license plate is even or odd is determined by its rightmost non-zero digit. If that digit is odd, the license plate is odd; otherwise, the license plate is even. For example:
- License plate 701038 is even because 8 is even.
- License plate 701803 is odd because 3 is odd.
- License plate 801350 is odd because 5 is odd.
- License plate 3800 is even because 8 is even.
The smallest license plate number is 1, as in the presidential plate "RI 1".
Your task is to determine how many integers between A and B (inclusive) are odd plates and how many are even plates.
Input
The input contains two integers A B (1 ≤ A ≤ B ≤ 10^16), representing the interval [A, B] of plates to investigate.
Output
Output one line with two integers O E separated by a single space: the number of odd plates and the number of even plates.