#P190. [User Entry] Program of atom(x) 2027
[User Entry] Program of atom(x) 2027
版权声明
题目来源:https://www.luogu.com.cn/problem/P10038
题目描述
以下是某量子密码锁的说明书:
在密码锁中,有一条长度为 (不能更改, 的具体取值见密码锁铭牌)的链,链上共有 个结点。每个结点上可以存放至多一个原子。初始时, 号原子以某个顺序(可以由用户自行调整)被存放在其中,每个结点存放一个原子。
定义 号原子的电荷量为 。
现有一个计时器 (单位为秒),其初值为 。
密码锁被加热后,以下事件依次循环发生,直至达成终止条件:
- 位于链两端的原子被移除(这不会使链变短),不再对后续事件产生影响;
- 判定终止条件:
- 若此时链中剩下不多于 个原子(也可以是 个),则达成终止条件,密码锁瘫痪(此时计时器 的值不会增加 );
- 否则,将计时器 的值增加 。
- 给每个原子标定运动方向(标定的运动方向是临时的,只生效一次,在下一次标定前会被重置):
- 计算它左边所有原子的电荷量之和,设计算结果为 ;
- 计算它右边所有原子的电荷量之和,设计算结果为 ;
- 如果 ,则标定方向为「向左」;
- 如果 ,则标定方向为「向右」;
- 可以证明,。
- 所有原子按照所标定的运动方向,移动一条边的距离,来到相邻的结点。
现在已经从铭牌上读取到了 的值,定义密码锁的瘫痪用时为它瘫痪时 的值。请恰当排列密码锁中 个原子的初始顺序,最大化密码锁的瘫痪用时。
输入格式
一行一个正整数 。
输出格式
一行 个正整数,一个 的排列,表示你给 krjt 规划的排列方案:从左到右(或者从右到左,可以证明它们的瘫痪用时相等)依次输出 个原子的编号。
答案可能有多个,输出一个即可。
样例
1
1
2
1 2
3
2 1 3
4
4 2 3 1
5
5 4 1 2 3
6
2 4 5 1 6 3
样例解释
个样例的瘫痪用时分别为 秒。
实际上,枚举可知:当 时,输出任何一个 的排列都能 AC。
下面对样例 进行模拟。在链的描述中:
- 表示该结点为空;
- 表示该结点上存放着 号原子;
- 为计算结果。
- 初始的链为 ;
- 初始为 ;
- 位于两端的原子被移除,链变为 ;
- 增加至 ;
- 计算, 个原子(从左向右)的结果分别为 $\color{black}(\color{red}0\color{black},841),(\color{red}24\color{black},721),(\color{red}144\color{black},720),(145,\color{red}0\color{black})$;
- 根据结果,左边 个原子()向左运动,最右边的原子()向右运动,链变为 ;
- 位于两端的原子被移除,链变为 ;
- 增加至 ;
- 计算, 个原子(从左向右)的结果分别为 $\color{black}(\color{red}0\color{black},1),(120,\color{red}0\color{black})$;
- 根据结果,左边的原子()向左运动,右边的原子()向右运动,链变为 ;
- 位于两端的原子被移除,链变为 ;
- 此时链中只剩下 个原子(),反应结束,密码锁瘫痪。
综上,样例 的瘫痪用时为 秒。
下发文件
请在这里下载下发文件。
这是一份可视化工具。
数据范围
本题共有 个测试点,分别有 ,每个 分。
对于 的数据,。