Freestyle

题目描述

Takahashi 可以用 $N$ 种不同的泳姿游泳。
当他使用第 $i$ 种泳姿时，每秒消耗 $A_i$ 体力并前进 $B_i$ 米。
回答 $Q$ 个查询。第 $i$ 个查询如下：

判断是否有可能在总消耗体力不超过 $C_i$ 的情况下前进 $D_i$ 米。如果可能，求所需的最少秒数。

在这里，他可以自由组合不同的泳姿，且切换泳姿的时间可以忽略不计。
具体地，他可以按以下步骤游泳：

选择正整数 $m$，长度为 $m$ 的正实数序列 $t=(t_1,t_2,\dots,t_m)$，以及长度为 $m$ 的整数序列 $x=(x_1,x_2,\dots,x_m)$，其中每个元素在 $1$ 到 $N$ 之间（含）。 然后，按顺序 $i=1,2,\dots,m$ 在第 $x_i$ 种泳姿下游 $t_i$ 秒。

输入格式

输入按下述格式由标准输入给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$ $Q$ $C_1$ $D_1$ $C_2$ $D_2$ $\vdots$ $C_Q$ $D_Q$

输出格式

共输出 $Q$ 行。
对于第 $i$ 个查询，在第 $i$ 行输出答案如下：

如果在总消耗体力不超过 $C_i$ 的情况下无法前进 $D_i$ 米，则输出 $-1$。 否则，输出所需的最少时间。当打印值与真实答案的绝对或相对误差不超过 $10^{-9}$ 时，视为正确。

4
1 2
2 3
3 3
4 4
5
4 7
7 7
49 100
1000 500
4 5

3.000000000000000000
1.750000000000000000
-1
125.000000000000000000
1.500000000000000000

提示

所有输入值均为整数。 $1 \le N \le 2 \times 10^5$ $1 \le A_i, B_i \le 10^9$ $1 \le Q \le 2 \times 10^5$ $1 \le C_i, D_i \le 10^9$在此输入中，Takahashi 可以使用以下四种泳姿：

每秒消耗 $1$ 体力并前进 $2$ 米。 每秒消耗 $2$ 体力并前进 $3$ 米。 每秒消耗 $3$ 体力并前进 $3$ 米。 每秒消耗 $4$ 体力并前进 $4$ 米。

该输入包含五个查询。

对于第一个查询，$C_1=4, D_1=7$。 选择 $t=(1,2)$ 和 $x=(2,1)$。Takahashi 的游泳过程如下： 在前 $1$ 秒，他消耗 $2$ 体力并前进 $3$ 米。 在接下来的 $2$ 秒，他消耗 $2$ 体力并前进 $4$ 米。

总共，他消耗 $4$ 体力并前进 $7$ 米。所需时间为 $3$ 秒，这是最少的。

对于第二个查询，$C_2=7, D_2=7$。 选择 $t=(7/4)$ 和 $x=(4)$。Takahashi 的游泳过程如下： 在前 $7/4$ 秒，他消耗 $7$ 体力并前进 $7$ 米。

总共，他消耗 $7$ 体力并前进 $7$ 米。所需时间为 $7/4$ 秒，这是最少的。

对于第三个查询，$C_3=49, D_3=100$。 无论 Takahashi 如何游泳，都无法在总消耗体力不超过 $49$ 的情况下前进 $100$ 米。

对于第四个查询，$C_4=1000, D_4=500$。 选择 $t=(125)$ 和 $x=(4)$。Takahashi 的游泳过程如下： 在前 $125$ 秒，他消耗 $500$ 体力并前进 $500$ 米。

总共，他消耗 $500$ 体力并前进 $500$ 米。所需时间为 $125$ 秒，这是最少的。

对于第五个查询，$C_5=4, D_5=5$。 选择 $t=(1/2,1)$ 和 $x=(4,2)$。Takahashi 的游泳过程如下： 在前 $1/2$ 秒，他消耗 $2$ 体力并前进 $2$ 米。 在接下来的 $1$ 秒，他消耗 $2$ 体力并前进 $3$ 米。

总共，他消耗 $4$ 体力并前进 $5$ 米。所需时间为 $3/2$ 秒，这是最少的。

标签: AtCoder|abc356G

来源

AtCoder|abc356G