#1882. 格雷码

    ID: 1882 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及- 上传者: 标签>CTT赛事:contest1856来源:qoj.ac数据:公开样例分治枚举

格雷码

格雷码

题目描述

标题: 格雷码 - Problem - QOJ.ac

#9640. 格雷码

Statistics

The problem was used in the following contests:

题目描述

通常,人们习惯将所有 n 位二进制串按照字典序排列,例如所有 2 位二进制串按字典序从小到大排列为:00,01,10,11。

格雷码(Gray Code)是一种特殊的 n 位二进制串排列法,它要求相邻的两个二进制串间恰好有一位不同,特别地,第一个串与最后一个串也算作相邻。

设 ci 表示第 i 位作为相邻两个串的不同位的次数。

所有 2 位二进制串按格雷码排列的一个例子为:00,01,11,10。对应的 c 序列为:c1=2,c2=2。

n 位格雷码不止一种,你想求出 c 序列的极差最小的一种。特别的,如果有多种答案,输出任意一种。

输入格式

仅一行一个正整数 n,意义见题目描述。

输出格式

仅一行 2n 个正整数。∀1≤i<2n,第 i 个正整数表示你构造的第 i 个二进制串和第 i+1 个二进制串不同的位。第 2n 个正整数表示第一个串与最后一个串不同的位。

样例

样例输入 1
2
样例输出 1
1 2 1 2
样例输入 2
3
样例输出 2
1 3 1 2 1 3 1 2

数据范围与约定

本题采用自定义校验器(Special Judge)评测。

本题共 25 个测试点,每个测试点分值相同。第 T 个测试点满足 n=T。

对每个测试点,评分方式如下:

  • 如果你输出的方案是 n 位格雷码且 c 序列的极差最小,得到 100% 的该测试点分数;
  • 如果你输出的方案是 n 位格雷码但 c 序列极差并非最小,得到 20% 的该测试点分数;
  • 否则,得到 0% 的该测试点分数。

提示

本题输出数据较大,请使用较快的输出方式。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
1 2 1 2

样例 2

3
1 3 1 2 1 3 1 2