#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 并输出你最多使用的打折券数量,否则,该校验器会给出简要的错误信息。