Triway Cup '18 Summer B - Beautiful Water Pearl

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type

SuSu is a fox spirit who is on her first matchmaking assignment. As a fox spirit, she must help to reunite reincarnated soulmates to fall in love again. Moreover, she must restore their memories by combining the two halves of their "sacrificial artifact" which they were reincarnated with.

However, when she is looking for their sacrificial artifact, the magical water pearl, SuSu realizes there is a problem: she doesn't know what the pearl looks like. Thus, she interrupted Bai Yuechu's speed dating to ask him for help. After promising him candy, he accepted her offer.

SuSu leads him to a row of 2^{30} half-pearls, with a runic inscription of the numbers 0 \dots 2^{30}-1 on each respective pearl. Bai Yuechu has done some research and knows that the numbers on the two half pearls he is looking for fits the following constraints:
Let the two numbers be A and B
A+B = C (Bitwise OR of A and B is C)
A \cdot B = D (Bitwise AND of A and B is D)
A \oplus B = E (Bitwise XOR of A and B is E)

The definitions for bitwise OR, AND and XOR are at the bottom of the problem statement if you do not know these terms already.

Given C, D, E in the input, Bai Yuechu wants you to determine the number of ordered pairs (A, B) such that the conditions are satisfied.

Input Specification

Line 1: 3 integers C, D, and E (0 \le C, D, E < 2^{30})

Sample Input

110 44 66

Sample Output



The four pairs which satisfy the problem are (44, 110), (46, 108), (108, 46), (110, 44).


All three functions use the binary representation of the number. In binary representation, each digit is one or zero, and each digits' value is worth twice the previous digit. (Note that in our regular decimal number system, each digit is worth ten times the previous digit).

To perform each of these functions, first convert the numbers to binary. Then, compare each bit of the numbers.

The i^{th} bit of A+B is one if the i^{th} bit of either A or B is 1.
The i^{th} bit of A \cdot B (A and B) is one if the i^{th} bit of both A and B is 1.
The i^{th} bit of A \oplus B (A xor B) is one if the i^{th} bit of A is different from the i^{th} bit of B.

Note that these functions already exist in nearly every programming language.
For example, in C++, Java, Python and Pascal, bitwise OR is |, bitwise AND is & and bitwise XOR is ^.


There are no comments at the moment.