← 返回题目列表

AtCoder · keyence2021_d

D. 选择正面

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

分数: 700 点

问题陈述

让 N 是正整数。 考虑一场比赛,有两支球队,每支球队 2^{N-1} 玩家们,互相对战。

我们有 2^N 玩家编号 1 通过 2^N。 Snuke 教练可以任意多次执行以下操作:将玩家分成 A 和 B 两队,每队 2^{N-1} 玩家,让他们互相对战。

他想要执行一次或多次此操作,以便满足以下两个条件:

  1. 存在一个整数 n 这样,对于每个 (i, j) 这样 1 \leq i < j \leq 2^N,玩家 i 和玩家 j 属于 相同 团队完全 n 次。
  2. 存在一个整数 m 这样,对于每个 (i, j) 这样 1 \leq i < j \leq 2^N,玩家 i 和玩家 j 属于 不同 团队完全 m 次。

我们可以证明存在实现 Snuke 目标的操作序列。在这些序列中,呈现一个序列 最小可能的操作数.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 8

输入

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

N

输出

按以下格式打印一系列操作:

K
s_1
s_2
\vdots
s_K

在这里, K 表示序列的长度,并且 s_i 代表团队的划分 i-第次操作。 s_i 应该是一个长度的字符串 2^N 组成 A 和 B。在 i-第次操作,如果玩家 j 属于 A 队, {j}- 第一个字符 s_{i} 应该是 A;如果玩家 j 属于 B 队, {j}- 第一个字符 s_{i} 应该是 B。请注意 A 和 B 每个必须准确发生 每个 2^{N-1} 次 s_i.

您的输出将在以下情况下被接受: K 是实现目标的操作序列的最小可能长度,并且该序列实际上实现了目标。


示例输入 1

1

示例输出 1

1
AB
  • 我们只需一次操作即可满足目标。
  • 请注意,我们必须至少执行一项操作。