DMOPC '18 Contest 5 P1 - A Painting Problem

View as PDF

Submit solution


Points: 3 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Mimi is taking both art and computer science this semester! Inspired, she decides to make an art piece based on the binary representation of two positive integers, N and M.

Mimi takes a strip of paper, and draws K stripes on it. The i^{\text{th}} stripe is blue if 2^{i-1} appears in the binary representation of either N or M, but not both. Otherwise, it is painted purple.

Can you tell Mimi how many blue and purple stripes there are?

Constraints

1 \leq N, M \leq 10^9
1 \leq K \leq 30

Input Specification

The first and only line of input will contain 3 space separated integers: N, M, and K.

Output Specification

The output should contain two space-separated integers: the number of stripes that are painted blue, and the number of stripes that are painted purple, respectively.

Sample Input

3 1 2

Sample Output

1 1

Explanation for Sample Output

The binary representation of 3 is 2^1 + 2^0, and the binary representation of 1 is 2^0.
Both representations have 2^0, so the first stripe is painted purple.
Since only 3 has 2^1 in its binary representation, the second stripe is painted blue.


Comments

There are no comments at the moment.