「WHOI-2」彗星蜜月

Luogu

IDLGP8431

Time1000ms

Memory128MB

DifficultyP4

模拟贪心二分洛谷原创O2优化枚举

定义 $f(x)$ 是 $x$ 的各位数码翻转以后形成的数。例如： - $f(12323)=32321$ - $f(114514)=415411$ - $f(250)=52$ --- 给定一个 $n$。求最大的 $k$，使得对于所有处于 $[1,k]$ 区间中的正整数 $m$，有 $f(m)\leq n$。 ## Input **本题多测** 第一行一个正整数 $T$ 表示测试点数目。接下来每个测试点一个正整数 $n$。 ## Output $T$ 行，对应每个测试点的答案。 [samples] ## Background ![](bilibili:BV11x411Q7PY) 看完这首 mv 的前奏之后你应该知道 $f$ 是什么鬼了（误）。 ## Note 对于测试样例 $1$： $f(1)=1,f(2)=2,f(3)=3,f(4)=4,f(5)=5,f(6)=6,f(7)=7,f(8)=8,f(9)=9,f(10)=1,f(11)=11,f(12)=21$。所以 $k$ 最大为 $11$。 --- **本题采用捆绑测试** - $\text{subtask1(10pts)}:1\leq T,n\leq10^3$。 - $\text{subtask2(30pts)}:1\leq n\leq10^6$。 - $\text{subtask3(40pts)}:1\leq n\leq10^9$。 - $\text{subtask4(20pts)}:$ 无特殊限制。对于 $100\%$ 的数据，$1\leq T\leq10^5,1\leq n\leq10^{18}$。提示：`unsigned long long` 可以储存 $0$ 到 $18,446,744,073,709,551,615(2^{64}-1)$ 的自然数。

Samples

Input #1

Output #1

11
298
100001

Input #2

2
99999
99998

Output #2

100000
99998

API Response (JSON)

{
  "problem": {
    "name": "「WHOI-2」彗星蜜月",
    "description": {
      "content": "定义 $f(x)$ 是 $x$ 的各位数码翻转以后形成的数。 例如： - $f(12323)=32321$ - $f(114514)=415411$ - $f(250)=52$ --- 给定一个 $n$。求最大的 $k$，使得对于所有处于 $[1,k]$ 区间中的正整数 $m$，有 $f(m)\\leq n$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8431"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义 $f(x)$ 是 $x$ 的各位数码翻转以后形成的数。\n\n例如：\n\n- $f(12323)=32321$\n- $f(114514)=415411$\n- $f(250)=52$\n---\n\n给定一个 $n$。求最大的 $k$，使得对于所有处于 $[1,k]$ 区间中的正整数 $m$，有 $f(m)\\leq n$。\n\n## Input\n\n**本题多测**\n\n第一行一个正整数 $T$ 表示测试点数目...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments