luogu#P10038. 「FAOI-R2」Program of atom(x) 2027 (D)
「FAOI-R2」Program of atom(x) 2027 (D)
题目背景
这是来自 年的 FAOI 的一道题目,是一道带有 SPJ 的传统题。
自从 krjt 上次被 人 JC 后,他换了一个「量子密码锁」,并用它锁上了自己的电脑包——打不开密码锁,就取不出包里的电脑。理论上,一旦 krjt 忘了密码,就连造这把锁的人也打不开。
然而,这把锁并非固若金汤。有一天,krjt 突然对化学产生了浓厚的兴趣。他拿起那把锁,放在酒精灯上加热,结果发现: 在高温环境下,这把锁内的原子(严格来说是「离子」,下同)排布变得不稳定,这将导致它瘫痪。
题目描述
krjt 找来了密码锁的说明书:
在密码锁中,有一条长度为 (不能更改, 的具体取值见密码锁铭牌)的链,链上共有 个结点。每个结点上可以存放至多一个原子。初始时, 号原子以某个顺序(可以由用户自行调整)被存放在其中,每个结点存放一个原子。
定义 号原子的电荷量为 。
现有一个计时器 (单位为秒),其初值为 。
密码锁被加热后,以下事件依次循环发生,直至达成终止条件:
- 位于链两端的原子被移除(这不会使链变短),不再对后续事件产生影响;
- 判定终止条件:
- 若此时链中剩下不多于 个原子(也可以是 个),则达成终止条件,密码锁瘫痪(此时计时器 的值不会增加 );
- 否则,将计时器 的值增加 。
- 给每个原子标定运动方向(标定的运动方向是临时的,只生效一次,在下一次标定前会被重置):
- 计算它左边所有原子的电荷量之和,设计算结果为 ;
- 计算它右边所有原子的电荷量之和,设计算结果为 ;
- 如果 ,则标定方向为「向左」;
- 如果 ,则标定方向为「向右」;
- 可以证明,。
- 所有原子按照所标定的运动方向,移动一条边的距离,来到相邻的结点。
此外,krjt 从铭牌上读取到了 的值。
krjt 定义,密码锁的瘫痪用时,为它瘫痪时 的值。当然,krjt 希望密码锁尽量安全,因此他想最大化密码锁的瘫痪用时。
为了不让更多人再次 JC krjt,请问:他该如何排列密码锁中 个原子的初始顺序?
输入格式
一行一个正整数,。
输出格式
一行 个正整数,一个 的排列,表示你给 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{red}0\color{black},841),(\color{red}24\color{black},721),(\color{red}144\color{black},720),(145,\color{red}0\color{black})$;
- 根据结果,左边 个原子()向左运动,最右边的原子()向右运动,链变为 ;
- 位于两端的原子被移除,链变为 ;
- 增加至 ;
- 计算, 个原子(从左向右)的结果分别为 $(\color{red}0\color{black},1),(120,\color{red}0\color{black})$;
- 根据结果,左边的原子()向左运动,右边的原子()向右运动,链变为 ;
- 位于两端的原子被移除,链变为 ;
- 此时链中只剩下 个原子(),反应结束,密码锁瘫痪。
综上,样例 的瘫痪用时为 秒。
本题共 个测试点,分别有 ,每个 分。
对于 的数据,。