311270: CF1958H. Composite Spells
Description
Monocarp plays a fantasy RPG. His character is a mage, so he casts spells. There are two types of spells he knows — basic spells and composite spells.
There are $n$ basic spells in Monocarp's spell book, numbered from $1$ to $n$. Each basic spell simply changes the health of the target: either decreases it or increases it. The $i$-th basic spell changes the target's health value by $b_i$ (increases by $b_i$ if $b_i$ is non-negative, or decreases by $|b_i|$ if $b_i$ is negative). If the target's health value goes to $0$ or below, it dies, and all next spells cast at it do nothing.
There are also $m$ composite spells in the spell book, numbered from $n+1$ to $n+m$. Each composite spell is a sequence of other spells, cast in specific order. A composite spell can consist both of basic spells and composite spells; the $i$-th spell consists of $s_i$ other spells, and each of those spells has index strictly less than $i$ (so there is no situation that composite spells infinitely cast each other). So, actually, each composite spell can be considered a finite sequence of basic spells, although its length might be huge. Note that the same spell can appear in a composite spell multiple times.
Monocarp has decided to cast the $(n+m)$-th spell from his spell book. The target of this spell is a monster with an initial health value of $hp$. Monocarp wants to know whether the monster will be killed or not, and if it will be killed, which basic spell will kill it.
InputThe first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
Each test case is given as follows:
- the first line contains two integers $n$ and $hp$ ($1 \le n \le 5000$; $1 \le hp \le 10^{9}$) — the number of basic spells and the initial health value of the monster;
- the second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — the descriptions of basic spells;
- the third line contains one integer $m$ ($1 \le m \le 5000$) — the number of composite spells;
- then $m$ lines follow, the $i$-th of these lines describes the $(n+i)$-th spell: it begins with an integer $s_{n+i}$ ($1 \le s_{n+i} \le 5000$) denoting the length of the spell (the number of spells it consists of); then a sequence of integers from $1$ to $(n+i-1)$ follows, denoting the sequence of spells.
Additional constraints on the input:
- the sum of $n$ over all test cases does not exceed $5000$;
- the sum of $m$ over all test cases does not exceed $5000$;
- the total length of all composite spells over all test cases does not exceed $5000$.
For each test case, print one integer:
- if the monster dies, print the index of the basic spell that kills the monster;
- otherwise, print $-1$.
4 4 9 1 -2 3 -4 3 3 1 4 3 4 1 2 1 2 6 6 5 6 5 6 5 4 9 1 -2 3 -4 3 3 1 4 3 4 1 2 1 2 7 6 5 6 5 6 6 5 3 31 -10 -20 30 1 6 1 2 3 1 2 3 6 20 -1 -5 -9 -7 -1 -1 4 3 6 5 2 4 3 3 7 6 6 4 8 4 4 6 7 3 6 5 7Output
4 4 -1 -1
Output
Monocarp 在玩一个幻想角色扮演游戏,他的角色是一个法师,可以施展法术。他知道的法术有两种——基础法术和复合法术。
在他的法术书中,有 n 个基础法术,编号从 1 到 n。每个基础法术都会改变目标的生命值:要么减少,要么增加。第 i 个基础法术会改变目标的生命值 by b_i(如果 b_i 非负,则增加 b_i;如果 b_i 为负,则减少 |b_i|)。如果目标的生命值降至 0 或以下,它就会死亡,之后对其施展的所有法术都不会起作用。
法术书中还有 m 个复合法术,编号从 n+1 到 n+m。每个复合法术都是其他法术的序列,按特定顺序施展。复合法术可以同时包含基础法术和复合法术;第 i 个法术由 s_i 个其他法术组成,且这些法术的索引严格小于 i(所以不存在复合法术无限互相施展的情况)。实际上,每个复合法术都可以被视为基础法术的有限序列,尽管其长度可能很大。注意,相同的法术可以在复合法术中出现多次。
Monocarp 决定施展他的法术书中的第 (n+m) 个法术。这个法术的目标是一个初始生命值为 hp 的怪物。Monocarp 想知道怪物是否会死亡,如果会死亡,哪个基础法术会杀死它。
输入输出数据格式:
输入:
- 第一行包含一个整数 t(1 ≤ t ≤ 1000)——测试用例的数量。
- 每个测试用例的格式如下:
- 第一行包含两个整数 n 和 hp(1 ≤ n ≤ 5000;1 ≤ hp ≤ 10^9)——基础法术的数量和怪物的初始生命值。
- 第二行包含 n 个整数 b_1, b_2, …, b_n(-10^9 ≤ b_i ≤ 10^9)——基础法术的描述。
- 第三行包含一个整数 m(1 ≤ m ≤ 5000)——复合法术的数量。
- 接下来 m 行,每行描述第 (n+i) 个法术:首先是一个整数 s_{n+i}(1 ≤ s_{n+i} ≤ 5000),表示法术的长度(它由多少个法术组成);然后是一个由 1 到 (n+i-1) 的整数序列,表示法术序列。
输出:
- 对于每个测试用例,打印一个整数:
- 如果怪物死亡,打印杀死怪物的基础法术的索引。
- 否则,打印 -1。
示例输入输出已给出。题目大意: Monocarp 在玩一个幻想角色扮演游戏,他的角色是一个法师,可以施展法术。他知道的法术有两种——基础法术和复合法术。 在他的法术书中,有 n 个基础法术,编号从 1 到 n。每个基础法术都会改变目标的生命值:要么减少,要么增加。第 i 个基础法术会改变目标的生命值 by b_i(如果 b_i 非负,则增加 b_i;如果 b_i 为负,则减少 |b_i|)。如果目标的生命值降至 0 或以下,它就会死亡,之后对其施展的所有法术都不会起作用。 法术书中还有 m 个复合法术,编号从 n+1 到 n+m。每个复合法术都是其他法术的序列,按特定顺序施展。复合法术可以同时包含基础法术和复合法术;第 i 个法术由 s_i 个其他法术组成,且这些法术的索引严格小于 i(所以不存在复合法术无限互相施展的情况)。实际上,每个复合法术都可以被视为基础法术的有限序列,尽管其长度可能很大。注意,相同的法术可以在复合法术中出现多次。 Monocarp 决定施展他的法术书中的第 (n+m) 个法术。这个法术的目标是一个初始生命值为 hp 的怪物。Monocarp 想知道怪物是否会死亡,如果会死亡,哪个基础法术会杀死它。 输入输出数据格式: 输入: - 第一行包含一个整数 t(1 ≤ t ≤ 1000)——测试用例的数量。 - 每个测试用例的格式如下: - 第一行包含两个整数 n 和 hp(1 ≤ n ≤ 5000;1 ≤ hp ≤ 10^9)——基础法术的数量和怪物的初始生命值。 - 第二行包含 n 个整数 b_1, b_2, …, b_n(-10^9 ≤ b_i ≤ 10^9)——基础法术的描述。 - 第三行包含一个整数 m(1 ≤ m ≤ 5000)——复合法术的数量。 - 接下来 m 行,每行描述第 (n+i) 个法术:首先是一个整数 s_{n+i}(1 ≤ s_{n+i} ≤ 5000),表示法术的长度(它由多少个法术组成);然后是一个由 1 到 (n+i-1) 的整数序列,表示法术序列。 输出: - 对于每个测试用例,打印一个整数: - 如果怪物死亡,打印杀死怪物的基础法术的索引。 - 否则,打印 -1。 示例输入输出已给出。