QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+4]

# 8705. 圣遗物

统计

你给八重神子宫司大人刷了三个月的圣遗物。不出意外的,你的圣遗物一如既往的烂,副词条不是小生命就是防御力。

你想起了行秋的极品暴击头,神里的极品攻击沙,胡桃的极品大攻击羽毛。刷圣遗物带给了你很多的悲伤,但是你仍然想要找一套圣遗物,使得在这套圣遗物下八重神子宫司大人的期望输出能够最大化。

problem_8705_1.png problem_8705_2.png problem_8705_3.png

Fig 1. 一些寄品圣遗物.

在游戏设定中,每位角色最多可以佩戴 L 个位置的圣遗物,每个位置只能佩戴至多一个圣遗物。角色有基础暴击率 A 和基础暴击伤害 B。假设佩戴的所有圣遗物提供暴击率之和为 a,暴击伤害之和为 b,则你的输出仅仅和 (A+a)(B+b) 相关(这里我们简化了设定,实际游戏当中期望伤害和攻击力,元素精通,敌人防御力等许多元素相关)。该值越高,你的输出越高。

你在第 i 个位置刷了 ni 个圣遗物,第 i 个位置的第 j 个圣遗物的暴击率为 ai,j,暴击伤害为 bi,j。你想要知道,在角色基础暴击率为 A,基础暴击伤害为 B 的前提条件下,通过配置圣遗物能够达到的最大的 (A+a)(B+b) 的值。由于你有着众多的角色,你需要回答多组询问。

在单次大招上伤害百万的前提下你并不关心几百的伤害差距,因此你不需要给出最优解的精确的数字。你只需要返回一个足够接近最优解的方案即可。

Input

本题有多组测试数据。

第一行两个数字 tid,T,分别表示测试包编号和表示测试数据组数。对于样例则有 tid=0

对于每组测试数据:

第一行一个数字 L,表示圣遗物位置的个数。

接下来 L 行,每两行形容在某一个位置上你刷出来的所有圣遗物。

对于每个位置,第一行一个正整数 ni

接下来一行 2×ni 个浮点数,第 2×j12×j 个数字分别表示 ai,j,bi,j 的值。

接下来一个数字 Q

接下来 Q 行,一行两个浮点数 A,B,表示一次询问。

输入保证浮点数在小数点后最多保留两位数字。

Ouptput

对于每次询问,一行 L 个数字,第 i 个数字 ai 表示在第 i 个位置上你选择的圣遗物恰好是输入的第 i 组的第 ai 个圣遗物,这里我们认为圣遗物编号从 1 开始。

你的答案被认为是正确的当且仅当:

  • 假定你给出的方案中 (A+a)(B+b) 的值为 x, 参考解给出的值为 y, 最优解给出的值为 z
  • 你的答案被认为是正确的当且仅当 |xy|2500
  • 我们保证 |yz|2500,因此我们保证 zx2500 时候,你的答案一定被判断为正确。

Examples

Input 1

0 1
2
2
1 2 3 4
2
1 4 3 2
2
1 1
5 1

Output 1

2 2 
2 1

Notes 1

在第一个类的圣遗物之中,由于第一个圣遗物双爆属性都没有第二个好,因此最优方案中必定会选择第二个圣遗物。在第二个圣遗物选择第一个的时候,暴击加成为 4,爆伤加成为 8; 在第二个圣遗物选择第二个的时候,暴击加成为 6,爆伤加成为 6

在第一个询问的时候,两种方案得到的乘积分别是 (4+1)×(8+1)=45(6+1)×(6+1)=49,因此我们选择第二种。

在第二个询问的时候,两种方案得到的乘积分别是 (4+5)×(8+1)=81(6+5)×(6+1)=77,因此我们选择第一种。

Input 2

0 1
4
2
1 2 3 4
2
1 4 3 2
2
1 10 5 1
2
1 5 10 1
5
1 1
5 1
10 1
10 2
100 3

Output 2

2 2 1 2 
2 1 1 2 
2 1 1 2 
2 1 1 2 
2 1 1 1

Scoring

Subtask 1 (15%): L5,n3。保证 ai,j,bi,j 为整数,且在范围内均匀随机生成。

Subtask 2 (20%): L30。保证 ai,j,bi,j 为整数,且在范围内均匀随机生成。

Subtask 3 (15%): L500。保证 ai,j,bi,j 为整数,且在范围内均匀随机生成。

Subtask 4 (15%): 保证 ai,j+bi,j=100

Subtask 5 (35%): 无特殊限制。

对于所有测试数据,满足 1T100,1L50000,1n,Q10,0<ai,j,bi,j100,1A,B107。数据保证浮点数 ai,bi 保留至最多小数点后两位。

\end{problem}