← 返回题目列表

AtCoder · abc356_g

G. 自由泳

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

高桥可以游泳 N 不同的风格。
当他在水中游泳时 i第一种风格,他消耗 A_i 每秒耐力和进步 B_i 米每秒。

答案 Q 查询。的 i第查询如下:

  • 判断是否可以前进 D_i 米,同时保持总体力消耗最多 C_i。如果可能的话,找出所需的最小秒数。

在这里,他可以自由组合不同的泳姿,而且切换泳姿的时间可以忽略不计。
具体来说,他可以按照以下步骤游泳:

  • 选择一个正整数 m,正实数序列 t=(t_1,t_2,\dots,t_m) 长度 m,以及整数序列 x=(x_1,x_2,\dots,x_m) 长度 m 其中每个元素位于 1 和 N,包括在内。
  • 然后,在 x_i-第样式 t_i 秒顺序 总共 i=1,2,\dots,m.

约束

  • 所有输入值均为整数。
  • 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

输入

输入由标准输入按以下格式给出:

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第行如下:

  • 如果无法前进 D_i 米,同时保持总体力消耗最多 C_i,打印 -1.
  • 否则,打印所需的最短时间。如果打印值与真实答案之间的绝对或相对误差最多为,则输出被认为是正确的 10^{-9}.

示例输入 1

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

示例输出 1

3.000000000000000000
1.750000000000000000
-1
125.000000000000000000
1.500000000000000000

在此输入中,高桥可以以以下四种方式游泳:

  • 消耗 1 耐力和进步 2 米每秒。
  • 消耗 2 耐力和进步 3 米每秒。
  • 消耗 3 耐力和进步 3 米每秒。
  • 消耗 4 耐力和进步 4 米每秒。

此输入包含五个查询。

  • 对于第一个查询, C_1=4, D_1=7.
    • 选择 t=(1,2) 和 x=(2,1)。高桥的游泳方式如下:
      • 在第一个 1 第二,他消耗 2 耐力和进步 3 米。
      • 在接下来 2 秒,他消耗 2 耐力和进步 4 米。
    • 他总共消耗了 4 耐力和进步 7 米。所需时间为 3 秒,这是最小值。
  • 对于第二个查询, C_2=7, D_2=7.
    • 选择 t=(7/4) 和 x=(4)。高桥的游泳方式如下:
      • 在第一个 7/4 秒,他消耗 7 耐力和进步 7 米。
    • 他总共消耗了 7 耐力和进步 7 米。所需时间为 7/4 秒,这是最小值。
  • 对于第三个查询, C_3=49, D_3=100.
    • 无论高桥如何游动,都不可能晋级 100 米,同时保持总体力消耗最多 49.
  • 对于第四个查询, C_4=1000, D_4=500.
    • 选择 t=(125) 和 x=(4)。高桥的游泳方式如下:
      • 在第一个 125 秒,他消耗 500 耐力和进步 500 米。
    • 他总共消耗了 500 耐力和进步 500 米。所需时间为 125 秒,这是最小值。
  • 对于第五个查询, C_5=4, D_5=5.
    • 选择 t=(1/2,1) 和 x=(4,2)。高桥的游泳方式如下:
      • 在第一个 1/2 秒,他消耗 2 耐力和进步 2 米。
      • 在接下来 1 第二,他消耗 2 耐力和进步 3 米。
    • 他总共消耗了 4 耐力和进步 5 米。所需时间为 3/2 秒,这是最小值。