← 返回题目列表

AtCoder · jag2017summer_day3_j

J. 和源检测

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

问题陈述

JAG成员开始了一场整数游戏。 游戏由 $N + M + 1$ 玩家组成:$N$ 公开号码持有者、$M$ 秘密号码持有者和一名应答者,即您。

在准备过程中,一个整数$K$被告知所有$N+M+1$玩家。 $N + M$ 号码持有者可以根据以下限制选择每人自己的整数:

  • 每个持有者拥有一个正整数。
  • 所有整数的总和等于 $K$。
  • 秘密号码持有者拥有的每个整数都严格小于公开号码持有者拥有的任何整数。

选择后,$N$ 开放数字持有者向回答者展示他们的整数 $O_{1}, \dots, O_{N}$,而秘密数字持有者则不会。

游戏有 $Q$ 轮。每轮开始时,$M$秘密号码持有者可以在上述限制下更改号码,而公开号码持有者则不能。然后$N+M$个号码持有者从其中任意选择部分成员,计算所选成员拥有的整数之和$X$,并将$X$告诉回答者。对于每一轮,回答者尝试从信息$K$、$X$和$O_{1}、\dots、O_{N}$中识别明确选择的开放号码持有者:回答者将在答案中为每个实际选择的开放号码持有者获得分数。另一方面,如果答案包含至少一个未选择的成员,您将失去本轮中获得的分数。因此,应答者(即您)必须仅回答开放号码持有者,以便明确选择持有者。

在这个问题中,你的任务是编写一个程序来确定所有开放数字持有者,其整数对于每轮的总和来说是必需的,以便最大化你的分数。


输入

输入由单个测试用例组成,格式如下。

$N$ $M$ $K$ $Q$ $O_{1}$ $\cdots$ $O_{N}$ $X_{1}$ $\cdots$ $X_{Q}$

第一行由四个整数 $N$、$M$、$K$ 和 $Q$ 组成。 $N$和$M$分别是公开号码持有者和秘密号码持有者的数量$(1 \le N, 0 \le M, N + M \le 40)$。 $K$ 是一个整数 $(1 \le K \le 200{,}000)$。 $Q$ 是游戏的轮数 $(1 \le Q \le 10{,}000)$。

第二行包含 $N$ 个整数 $O_{1}, \cdots, O_{N}$,因为第 $i$ 个开放号码持有者拥有 $O_{i}$ ($1 \le O_{1} \le \dots \le O_{N} \le K$)。

第三行表示$Q$整数$X_{1}, \cdots, X_{Q}$ $(0 \le X_{i} \le K)$。 $X_{i}$ 是第 $i$ 轮中所选成员拥有的整数总和。

保证至少有一种方法来组成$X_{i}$。换句话说,你可以假设至少有一个整数序列 $S_{1}, \dots, S_{M}$,代表秘密数字持有者拥有的整数,满足以下条件:

  • $0 < S_{j} < O_{1}$ 对于 $1 \le j \le M$。请注意 $O_{1} = \min_{1 \le k \le N} O_{k}$ 成立。
  • $\sum_{j=1}^{N} O_{j} + \sum_{k=1}^{M} S_{k} = K$。
  • 至少有一对子集 $U \subseteq \{1, \dots, N\}$ 和 $V \subseteq \{1, \dots, M\}$ 使得 $\sum_{j \in U} O_{j} + \sum_{k \in V} S_{k} = X_{i}$ 成立。

输出

在每个总和 $X_{i}$ 上,打印需要其整数来组成 $X_{i}$ 的开放数字持有者的索引。每个总和的输出必须按升序打印在一行中,并用一个空格分隔。如果不存在其整数肯定用于$X_{i}$的开放数字持有者,则在一行中打印$-1$。


样本输入 1

2 2 23 2
7 10
9 10

样本输入 1 的输出

1
-1

第一个金额 $9$ 只能通过第一个开放号码持有者的 $7$ 加上秘密号码持有者的 $2$ 来获得。在这种情况下,秘密号码持有者有 $2$ 和 $4$。 第二个开放号码持有者的 $10$ 是第二笔 $10$ 的候选者。第一个开放持有者的 $7$ 加 $3$ 也是可能的,因为秘密号码持有者有两个 $3$。


示例输入 2

1 1 100 3
51
49 51 100

样本输入 2 的输出

-1
1
1

唯一的秘密号码持有者拥有 49 美元。第一个总和的输出是 $-1$,因为未选择开放号码持有者的 $51$。


示例输入 3

2 1 58152 4
575 57500
575 57577 77 0

样本输入 3 的输出

1
2
-1
-1

在这种情况下,唯一的秘密号码持有者肯定有 $77$。 最后一个和 $0$ 的输出是 $-1$,因为不需要开放数字持有者的整数来形成 $0$。


示例输入 4

3 2 1500 1
99 300 1000
99

样本输入 4 的输出

1

组成 $99$ 的唯一方法是仅选择第一个开放号码持有者;秘密数字持有者有两个介于 $1$ 和 $98$ 之间的整数,而它们的总和必须为 $101$。


示例输入 5

3 2 20 19
3 3 11
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20

样本输入 5 的输出

-1
-1
-1
-1
-1
-1
1 2
1 2
1 2
3
3
3
3
3
3
3
1 2 3
1 2 3
1 2 3

两个秘密号码持有者拥有的号码是 $1$ 和 $2$。 至少需要一个开放号码持有者的$3$分别组成$5$和$6$,但无法确定明确选择的开放号码持有者。另一方面,$7$ 需要两个都拥有 $3$ 的开放号码持有者。