QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 256 MB Total points: 100 Hackable ✓

#7244. 埃尔维斯·普雷斯利

Statistics

考虑一个可能无限的有向无环图 $G = (V, E)$(即对于每一条边 $(u, v) \in E$,都有 $u \neq v$)。定义其传递闭包 $G^+ = (V, E^+)$ 为一个与 $G$ 具有相同顶点集 $V$ 的有向图,其边集包含所有满足 $u \neq v$ 且存在有限路径 $u = p_0, p_1, p_2, \dots, p_{k-1}, p_k = v$(其中对于所有 $i = 1, 2, \dots, k$ 均有 $(p_{i-1}, p_i) \in E$)的顶点对 $(u, v)$。

反链(antichain)是一个(可能无限的)集合 $A \subseteq V$,使得对于任意两个不同的顶点 $u, v \in A$,边 $(u, v)$ 和 $(v, u)$ 均不在 $G^+$ 中。

考虑一个集合 $U$ 以及定义在其所有子集上的某种性质 $P$(例如,对于 $G = (V, E)$ 的子集 $A$,性质 $P$ 可以是“$A$ 是否为图 $G$ 的反链”)。如果子集 $S \subseteq U$ 的大小 $|S|$(可能等于 $\infty$)达到最大可能值,则称 $S$ 为满足性质 $P$ 的最大(maximum)子集。如果不存在其他满足性质 $P$ 的子集 $T$ 使得 $S \subsetneq T$(即 $S$ 无法扩展为满足相同性质的更大子集),则称 $S$ 为满足性质 $P$ 的极大(maximal)子集。 注意这两个定义是不同的:如果满足性质 $P$ 的最大子集存在且是有限的,那么它显然也是极大的;但满足性质 $P$ 的极大子集不一定是最大的。

我们以类似的方式定义满足性质 $P$ 的最小(minimal)和最小(minimum)子集。

定义一个 EP-图:$EP = (V_{EP}, E_{EP})$,其顶点集为 $V_{EP} = \mathbb{N} = \{1, 2, 3, \dots\}$,边集为 $E_{EP} = \{(v, 2v) : v \in \mathbb{N}\} \cup \{(v, 2v + 1) : v \in \mathbb{N}\}$。

给定 $V$ 中的两个不同顶点 $a$ 和 $b$。请找到一个包含 $a$ 和 $b$ 的最小极大反链,或者确定不存在这样的反链。如果存在多个可能的答案,输出其中任意一个。

更正式地: $AC = \{A \subseteq V_{EP} : A \text{ 是 } EP \text{ 中的反链}\}$。 $MaxAC = \{A \in AC : A \text{ 是极大的}\}$。 $MinMaxAC = \{A \in MaxAC : |A| = \min_{S \in MaxAC} |S|\}$。

你的任务是找到 $MinMaxAC$ 中的任意一个元素。

输入格式

输入的第一行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le 10^9, a \neq b$)。

输出格式

如果不存在包含 $a$ 和 $b$ 的最小极大反链,或者该反链是无限的,输出 $-1$。否则,按升序输出包含 $a$ 和 $b$ 的任意一个最小极大反链中的元素。

样例

样例 1

输入

2 7

输出

2 6 7

样例 2

输入

1 2

输出

-1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.