← 返回题目列表

AtCoder · abc347_d

G. Popcount 和 XOR

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你非负整数 a, b,和 C。 判断是否存在一对非负整数 (X, Y) 满足以下所有五个条件。如果存在这样的一对,则打印一个。

  • 0 \leq X < 2^{60}
  • 0 \leq Y < 2^{60}
  • \operatorname{popcount}(X) = a
  • \operatorname{popcount}(Y) = b
  • X \oplus Y = C

在这里, \oplus 表示按位异或。

如果多对 (X, Y) 满足条件,可以打印其中任意一个。

popcount是什么?

对于非负整数 x,popcount x 是数量 1s 的二进制表示形式 x。 更准确地说,对于非负整数 二进制的 x 这样 \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace),我们有 \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.

例如, 13 是 1101,所以 \operatorname{popcount}(13)=3.
什么是按位异或?

对于非负整数 x, y,按位异或 x \oplus y 定义如下。

  • 的 2^k的地方 \ (k\geq0) 的二进制表示形式 x \oplus y is 1 如果恰好是其中之一 2^k的地点 \ (k\geq0) 的二进制表示形式 二进制的 x 和 y is 1,和 0 否则。

例如, 9 和 3 是 1001 和 0011分别是 9 \oplus 3 = 10 (二进制, 1010).

约束

  • 0 \leq a \leq 60
  • 0 \leq b \leq 60
  • 0 \leq C < 2^{60}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

a b C

输出

如果有一对满足条件的非负整数,则选择其中的一对 (X, Y) 并打印 X 和 Y 按此顺序,中间有一个空格。 如果不存在这样的对,则打印 -1.


示例输入 1

3 4 7

示例输出 1

28 27

这对 (X, Y) = (28, 27) 满足条件。 在这里, X 和 Y 是 11100 和 11011。

  • X 是 11100,所以 \operatorname{popcount}(X) = 3.
  • Y 是 11011,所以 \operatorname{popcount}(Y) = 4.
  • X \oplus Y 是 00111,所以 X \oplus Y = 7.

如果多对非负整数满足条件,则可以打印其中任意一个,因此打印 例如, 42 45也将被接受。


示例输入 2

34 56 998244353

示例输出 2

-1

没有一对非负整数满足条件。


示例输入 3

39 47 530423800524412070

示例输出 3

540431255696862041 10008854347644927

请注意,要打印的值可能不适合 32- 位整数。