#G1083. [GESP202412 四级] Recamán

[GESP202412 四级] Recamán

[GESP202412 四级] Recamán

题目描述

小杨最近发现了有趣的 Recamán 数列,这个数列是这样生成的:

  • 数列的第一项 a1a_1 是 11;
  • 如果 ak−1−ka_{k-1} - k 是正整数并且没有在数列中出现过,那么数列的第 kk 项 aka_k 为 ak−1−ka_{k-1} - k,否则为 ak−1+ka_{k-1} + k。

小杨想知道 Recamán 数列的前 nn 项从小到大排序后的结果。手动计算非常困难,小杨希望你能帮他解决这个问题。

输入格式

第一行,一个正整数 nn。

输出格式

一行,nn 个空格分隔的整数,表示 Recamán 数列的前 nn 项从小到大排序后的结果。

样例 #1

样例输入 #1

5

样例输出 #1

1 2 3 6 7

样例 #2

样例输入 #2

8

样例输出 #2

1 2 3 6 7 12 13 20

样例解释

对于样例 1,n=5n = 5:

  • a1=1a_1 = 1;
  • a1−2=−1a_1 - 2 = -1,不是正整数,因此 a2=a1+2=3a_2 = a_1 + 2 = 3;
  • a2−3=0a_2 - 3 = 0,不是正整数,因此 a3=a2+3=6a_3 = a_2 + 3 = 6;
  • a3−4=2a_3 - 4 = 2,是正整数,且没有在数列中出现过,因此 a4=2a_4 = 2;
  • a4−5=−3a_4 - 5 = -3,不是正整数,因此 a5=a4+5=7a_5 = a_4 + 5 = 7。

a1,a2,a3,a4,a5a_1, a_2, a_3, a_4, a_5 从小到大排序后的结果为 1 2 3 6 7。

数据范围

  • 对于所有数据点,保证 1≤n≤30001 ≤ n ≤ 3000。

时间限制:1.0 s。内存限制:512.0 MB。