#P1047. 新年的打折

新年的打折

楽马在购物,有 $T$ 件想要的商品。

第 $i$ 件商品的原价是 $b_i$,但楽马想以恰好 $a_i$ 的价格购买。

这个商场接受一种写着数字的打折券,写着 $x$ 的打折券能让商品价格减少当前价格的 $\frac{1}{x}$。

楽马有 $x=2\sim10^9$ 的打折券各无限张,但购买一件商品的时候至多使用 $100$ 张打折券。

请对每件商品构造一个使用打折券的方案,可以证明一定有解。

输入格式

第一行输入一个正整数 $T$。

接下来每行输入两个正整数 $a_i,b_i$,保证 $a_i< b_i$。

输出格式

对于每件商品,第一行输出使用的打折券数量 $m$,第二行输出使用的 $m$ 张打折券。

3
1 8
8 15
799 864
3
2 2 2 
2
3 5 
3
800 26 27

数据范围

$1\leq T \leq 1000, 1\leq a_i< b_i \leq 10^9$。

子任务编号 特殊性质 分值
$1$ $b_i\leq 5$ $9$
$2$ $b_i\leq 100$ $13$
$3$ $b_i\leq 1000$ $17$
$4$ $b_i-a_i\leq 100$ $18$
$5$ $a_i=1$ $19$
$6$ $24$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

校验器

为了方便选手测试,附加文件中我们给出了名为 checker.cpp 的文件,选手可以编译该程序,并使用它校验自己的输出文件。你不需要关心其代码的具体内容。

编译命令为:g++ -std=c++14 checker.cpp −o checker。此外,附加文件中有还有名为 testlib.h 的文件,在编译时,请确保该文件与 checker.cpp 在同一子目录下。

在终端中,checker 的使用方式为:checker <输入文件名> <输出文件名> <输出文件名>。如果你的输入文件名为 price.in,输出文件名为 price.out,则正确的使用方式为 checker price.in price.out price.out

若你的方案正确,校验器会给出 ok 并输出你最多使用的打折券数量,否则,该校验器会给出简要的错误信息。