P16736 [GKS 2019 #E] Code-Eat Switcher

Umon 是一个吃货程序员。你知道他最喜欢的两项活动是什么吗？当然是编码和吃饭！他整天只做这两件事。不过，他认为一天中的某些时段更适合编码，而另一些时段更适合吃饭。 为了说明这个问题，Umon 将一天划分为 $S$ 个时间段。在第 $i$ 个时间段，如果 Umon 将 $100\%$ 的时间用于编码，他将获得 $C_i$ 单位的编码量；反之，如果他将 $100\%$ 的时间用于吃饭，他将获得 $E_i$ 单位的饭量。当然，Umon 也可以只使用一部分时间编码，剩余时间吃饭。形式化地说，他会选择一个实数 $f$（$0 \le f \le 1$），用 $f$ 的时间编码，剩下的 $(1-f)$ 的时间吃饭。这样，他将获得 $f \times C_i$ 单位的编码量和 $(1-f) \times E_i$ 单位的饭量。Umon 一天获得的总编码量就是他在每个时间段获得的编码量之和。总饭量同理计算。 Umon 需要规划接下来 $D$ 天的日程。在第 $i$ 天，他需要至少达到总编码量 $A_i$ 和总饭量 $B_i$。对于每一天，判断是否存在一种方式使 Umon 达到他的目标。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $D$ 和 $S$，分别表示天数和一天中的时间段数。 随后 $S$ 行，每行描述一个时间段。第 $i$ 行包含两个整数 $C_i$ 和 $E_i$，分别表示如果 Umon 在该时间段 $100\%$ 编码所能获得的编码量，以及如果 $100\%$ 吃饭所能获得的饭量。 接着 $D$ 行，每行描述一天。第 $i$ 行包含两个整数 $A_i$ 和 $B_i$，表示当天需要达到的最小总编码量和总饭量。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个长度为 $D$ 的字符串，其中第 $i$ 个字符为 `Y` 如果存在一种日程安排能实现第 $i$ 天的目标，否则为 `N`。

在第一个样例中，有 $4$ 天，每天有 $2$ 个时间段。 - 对于第 $1$ 天，Umon 可以在两个时间段都 $100\%$ 吃饭，因此获得总编码量 $0$ 和总饭量 $8+10=18$，达到目标。 - 对于第 $2$ 天，Umon 可以在第一个时间段 $100\%$ 吃饭，在第二个时间段用 $50\%$ 的时间编码、$50\%$ 的时间吃饭，从而获得总编码量 $0 \times 3 + 0.5 \times 6 = 3$，总饭量 $1 \times 8 + 0.5 \times 10 = 13$，达到目标。 - 对于第 $3$ 天，无法获得总编码量 $10$。 - 对于第 $4$ 天，存在无穷多种方式达到目标。一种可能的策略是：在第一个时间段编码 $42\%$（吃饭 $58\%$），在第二个时间段编码 $98.76\%$（吃饭 $1.24\%$）。该策略给出总编码量 $0.42 \times 3 + 0.9876 \times 6 = 7.1856$，总饭量 $0.58 \times 8 + 0.0124 \times 10 = 4.764$。 因此，答案应为 `YYNY`。 在第二个样例中，注意不同时间段的特征值不一定互不相同。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le C_i \le 10^4$。 对于所有 $i$，$1 \le E_i \le 10^4$。 对于所有 $i$，$0 \le A_i \le 10^8$。 对于所有 $i$，$0 \le B_i \le 10^8$。 **测试集 1（可见）** $1 \le S \le 2$。 $1 \le D \le 10$。 **测试集 2（隐藏）** 对于至少 $75\%$ 的测试用例： $1 \le S \le 10^3$。 $1 \le D \le 10^3$。 对于所有测试用例： $1 \le S \le 10^5$。 $1 \le D \le 10^5$。 翻译由 DeepSeek V4 Pro 完成