← 返回题目列表

AtCoder · xmascon25_g

G. Gon 打包

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

配点 : 800 点(部分分数可得)

黑兔「https://codeforces.com/contest/1991/problem/F」

白兔「这个 n = 6 需要按分割 10 的方式全部搜索吗?」

黑兔「不是那样的」

白兔「意外地 1 即使跳过这么多方式也不会掉分啊」

黑兔「所以今年我带来了 171 道题」

白兔「请不要大量提交哦」

問題文

N 设为正整数。

集合 \{1, 2, \ldots, 2N\} 可以得到第 N 元集合 2 个的整体划分是 \mathcal{P} 。\lvert \mathcal{P} \rvert = \frac{1}{2} \binom{2N}{N} 。例如,N = 3 什么时候 \{ \{ 1, 5, 6 \}, \{ 2, 3, 4 \} \} \in \mathcal{P} 。

1 \le a_1 < a_2 < \cdots < a_{2N} 的一组整数 (a_1, a_2, \ldots, a_{2N}) , 定义好划分 它被称为是什么? 最小使得P \in \mathcal{P} ,并且对于任意的 I \in P ,存在边长集合为 \{ a_i \mid i \in I \} 的非退化简单 N 多边形。例如,N = 3 什么时候 \{ \{ 1, 5, 6 \}, \{ 2, 3, 4 \} \} 是良好划分的条件是a_1, a_5, a_6 是三角形的 3 边长并且成为 a_2, a_3, a_4 是三角形的 3 边长。给定

N 并且,P \in \mathcal{P} 。是否存在整数 P 使得恰好只有良好划分 1 \le a_1 < a_2 < \cdots < a_{2N} ?当存在时,可以证明存在这样的

  • 并且满足 (a_1, a_2, \ldots, a_{2N}) 。满足所有这些条件的 a_{2N} \le 10^{17} 不存在时,存在满足以下条件的非负整数 (a_1, a_2, \ldots, a_{2N}) 该值应乘以 1 找到一个。
  • 和划分 k 。 Q_1, Q_2, \ldots, Q_k \in \mathcal{P} 存在,因此在那些中找出 k 最小的 1 个:
    • j = 1, 2, \ldots, k , 定义Q_j \ne P.
    • 任何 1 \le a_1 < a_2 < \cdots < a_{2N} , 定义P 是好的分割的话,Q_1, Q_2, \ldots, Q_k 至少 1 个也是好的分割。

在输入输出中,\mathcal{P} 的元素用N 的 您可以创建一个包含 0 和 按字典顺序比较 N 的 您可以创建一个包含 1 组成结束是 一个字符串 1 的字符串表示。每个字符种类的索引集合表示分割的每个元素。例如,N = 3 什么时候 \{ \{ 1, 5, 6 \}, \{ 2, 3, 4 \} \} 该值应乘以 100011 代表。

制約

  • 3 \le N \le 5.

部分点

  • 满足约束条件的所有可能输入数据,每个包含 1 个。对于每个数据,如果正确答案,依据 N 点。 如果所有满足

入力

输入是按以下格式从标准输入给出的。

N P

出力

在问题文本中 2 的情况,以以下任一形式输出。

YES a_1 a_2 \cdots a_{2N}
NO k Q_1 Q_2 \cdots Q_k

入力例 1

3 100011

出力例 1

YES 2 4 6 8 10 11

P = \{ \{ 1, 5, 6 \}, \{ 2, 3, 4 \} \} 。

关于这个输出例,2, 10, 11 是三角形的 3 条边的长度,4, 6, 8 也是三角形的 3 条边的长度,所以P 是一个好的划分。也可以看出其他划分不能成为好的划分。


入力例 2

3 100101

出力例 2

NO 1 100011

P = \{ \{ 1, 4, 6 \}, \{ 2, 3, 5 \} \} 。

下面 3 条件 找出

  • 1 \le a_1 < a_2 < a_3 < a_4 < a_5 < a_6
  • a_1, a_4, a_6 是三角形的 3 成为边的长度 如果
  • a_2, a_3, a_5 是三角形的 3 成为边的长度 如果

成立,那么可以看出以下 2 条件 找出

  • a_1, a_5, a_6 是三角形的 3 成为边的长度 如果
  • a_2, a_3, a_4 是三角形的 3 成为边的长度 如果

也成立。