[GESP202412 四级] Recamán

Luogu

IDLGB4068

Time1000ms

Memory512MB

DifficultyP2

递推2024排序GESP

小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的： - 数列的第一项 $a_1$ 是 $1$； - 如果 $a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 $a_k$ 为 $a_{k-1}-k$，否则为 $a_{k-1}+k$。小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。 ## Input 第一行，一个正整数 $n$。 ## Output 一行，$n$ 个空格分隔的整数，表示 Recamán 数列的前 $n$ 项从小到大排序后的结果。 [samples] ## Background 对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1168> ## Note #### 样例解释对于样例 1，$n=5$： - $a_1=1$； - $a_1-2=-1$，不是正整数，因此 $a_2=a_1+2=3$； - $a_2-3=0$，不是正整数，因此 $a_3=a_2+3=6$； - $a_3-4=2$，是正整数，且没有在数列中出现过，因此 $a_4=a_3-4=2$； - $a_4-5=-3$，不是正整数，因此 $a_5=a_4+5=7$。 $a_1,a_2,a_3,a_4,a_5$ 从小到大排序的结果为 $1,2,3,6,7$。 #### 数据范围对于所有数据点，保证 $1\le n\le 3\, 000$。

Samples

Input #1

Output #1

1 2 3 6 7

Input #2

Output #2

1 2 3 6 7 12 13 20

API Response (JSON)

{
  "problem": {
    "name": "[GESP202412 四级] Recamán",
    "description": {
      "content": "小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的： - 数列的第一项 $a_1$ 是 $1$； - 如果 $a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 $a_k$ 为 $a_{k-1}-k$，否则为 $a_{k-1}+k$。 小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4068"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：\n\n- 数列的第一项 $a_1$ 是 $1$；\n- 如果 $a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 $a_k$ 为 $a_{k-1}-k$，否则为 $a_{k-1}+k$。\n\n小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments