循环删除数字

题目描述

给定一个长度为 n 的数组。

数组中的数字从左到右依次为：

1 2 3 ... n

现在进行循环删除操作。

每一天执行一次操作：

1. 从当前数组的第一个数字开始扫描；
2. 删除第 1 个、第 4 个、第 7 个……位置上的数字；
3. 没有被删除的数字保持原来的相对顺序；
4. 删除完成后，剩余数字重新组成一个新的数组；
5. 第二天继续进行相同的删除操作。

直到数组中只剩下一个数字。

请你输出：

最后剩下的数字是多少。

---

输入格式

输入一个整数：

n

表示初始数组的长度。

---

输出格式

输出一个整数：

ans

表示最后剩余的数字。

---

数据范围

1 ≤ n ≤ 10000

---

样例

输入

8

---

样例解释

初始数组：

1 2 3 4 5 6 7 8

---

第一天

删除第：

1 4 7

个数字：

1 4 7

剩余：

2 3 5 6 8

---

第二天

当前数组：

2 3 5 6 8

位置重新计算：

位置：

1 2 3 4 5

数字：

2 3 5 6 8

删除第：

1 4

个数字：

2 6

剩余：

3 5 8

---

第三天

当前数组：

3 5 8

删除：

第1个
第4个不存在

所以删除：

3

剩余：

5 8

---

第四天

当前数组：

5 8

删除第1个：

5

剩余：

8

所以：

最后剩余数字：

8

---

输出

8

---

样例2

输入

5

---

过程：

初始：

1 2 3 4 5

第一天删除：

1 4

剩余：

2 3 5

第二天删除：

2

剩余：

3 5

第三天删除：

3

剩余：

5

输出：

5

---

解题提示

本题属于数组模拟类问题。

可以使用两个数组：

a数组：
保存当前数组


b数组：
保存删除后的新数组

每一天：

1. 遍历 a；
2. 判断当前位置是否需要删除；
3. 没删除的数字加入 b；
4. 用 b 更新 a；
5. 直到 a 中只剩一个数字。

---

注意事项

删除的是位置，不是数字大小

例如：

当前数组：

2 3 5 6 8

重新编号：

位置：

1 2 3 4 5

删除：

第1个、第4个

实际删除：

2 6

不是删除：

1 4 7

因为数组中的数字已经发生变化。

测试点编号	n	标准输出	难度层级	特殊性质	设计目的
1			弱数据	最小规模	不进入循环，直接输出
2				一轮结束	检查最小删除过程
3		3			检查 i % 3 == 0 删除位置
4				两轮变化	卡“只删一次”的错误
5		5		小规模奇数	检查保留序列重排
6				小规模偶数	检查多元素压缩
7			正常数据	删除边界相邻	覆盖第 7 个被删的情况
8		8		结果在末尾	检查末尾元素保留
9				3 的倍数	卡按固定原下标删除的错误
10				3 的倍数 + 1	覆盖长度变化边界
11				3 的倍数 + 2
12	27			3 的幂	多轮删除，规律性强
13	100	93		百级规模	检查循环稳定性
14	9999	8091	极限数据	接近上限	检查大规模多轮处理
15	10005			数组最大安全规模	覆盖原数组上限