TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8914
  • 题目
  • P8914[模拟赛20211116]空间跳跃
    限制 : 时间限制 : - MS   空间限制 : 524288 KB  SPJ
    评测说明 : 1s,512MB
    问题描述

    牛妺在无穷多个平行宇宙中跳跃,每个宇宙都有一个整数编号,且对于每个整数 \(n \in \mathbb{Z}\) ,都有唯一一个宇宙的编号是 \(n\)

    牛妺掌握了三种空间跳跃技术,分别是:

    1. 如果当前在编号为 \(n\) 的宇宙,且 \(\min (|n|,|n-d|) \leq l\) ,则她可以跳跃到编号为 \(n-d\) 的宇宙,其中 \(d\)\(l\) 都是给定的正整数。
    2. 如果当前在编号为 \(n\) 的宇宙,则她可以跳跃到编号为 \(2 n\) 的宇宙。
    3. 如果当前在编号为 \(n\) 的宇宙,且 \(n \equiv 1(\bmod 3)\) ,(即 \(n=\ldots,-5,-2,1,4, \ldots\) 时)则她可以跳跃到编号为 \(\frac{n-1}{3}\) 的宇宙

    牛妺一开始在编号为 \(1\) 的宇宙中,她可以随意的使用这三种空间跳跃技术在宇宙中跳跃。她有 \(q\) 个想去的目的地 \(n_{1}, n_{2}, \ldots, n_{q}\) , 她想知道对于每个 \(i(1 \leq i \leq q)\) ,她需要怎么从编号为 \(1\) 的宇宙跳跃到编号为 \(n_{i}\) 的宇宙,请你帮她安排路线(你不用考虑她如何回去)。由于每次跳跃需要巨大的能量,所以每次牛妺只能跳跃不超过 \(1500\) 次。

    输入格式

    第一行三个整数 \(q, d, l\) ,以空格分离。

    接下来 \(q\) 行,第 \(i\) 行一个整数 \(n_{i}\) ,表示目的地宇宙的编号。

    输出格式

    输出 \(q\) 行,第 \(i\) 行输出 \(k_{i},\;o_{i, 0},\;o_{i, 1},\;\cdots,\; o_{i, k_{i}}\)

    其中 \(o_{i, 0}=1\)\(o_{i, k i}=n_{i}\) ,且可以通过三种空间跳跃技术之一从编号为 \(o_{i, j}\) 的宇宙跳跃到编号为 \(o_{i, j+1}\) 的宇宙 \(\left(0 \leq j<k_{i}\right)\)

    输出需要满足对于任意的 \(1 \leq i \leq q\)\(0 \leq j \leq k_{i}\)\(0 \leq k_{i} \leq 1500\)\(-10^{18} \leq o_{i, j} \leq 10^{18}\)

    输出任意一组满足上述所有条件的解即可,数据保证至少存在一组满足上述所有条件的解。

    样例输入

    5 3 10000
    10
    -9
    0
    -7
    1

    样例输出

    6 1 2 4 8 16 13 10
    4 1 0 -3 -6 -9
    1 1 0
    5 1 -2 -5 -10 -20 -7
    0 1

    提示

    数据范围

    对于 \(10\%\) 的数据,满足 \(\left|n_{i}\right| \leq 10^{3}\)\(d=1\)\(l=1500\)
    对于 \(30\%\) 的数据,满足 \(\left|n_{i}\right| \leq 10^{3}\)
    对于另外 \(10\%\) 的数据,满足 \(\left|n_{i}\right| \leq 10^{6}\)\(l=10^{6}\)
    对于另外 \(20\%\) 的数据,满足 \(\left|n_{i}\right| \leq 10^{6}\)
    对于 \(100\%\) 的数据,满足 \(\left|n_{i}\right| \leq 10^{7}\)\(1 \leq q \leq 20\)\(1 \leq d \leq 10^{6}\)\(10^{3} \leq l \leq 10^{6}\)