SP9970 EGYPAR - The Egyptian Parliament

今年，埃及正面临极具挑战的时刻。议会选举即将按照新颁布的选举法举行，议会席位将采用政党名单比例代表制的方式进行分配。在此选举中，选民投票支持政党而非个人候选人。每个政党赢得的席位数量取决于他们获得的总票数。 你是 ACM 党的主席，希望你的政党在即将到来的选举中赢得最多的席位。凭借你的预测能力，你已经知道每个政党（包括你的政党）能获得的票数。 目前，有两种待定的选举方式（之后将会具体解释），你可以通过人脉影响最终采用哪种方式。假设你的预测完全准确，问题在于找出哪种选举方式能让你的政党获得更多席位。 **选举方式 1：D'Hondt 方法** 这种方法在土耳其、日本和西班牙等国家使用。设有 $P$ 个政党和 $S$ 个席位，此方法生成一个 $P$ 行 $S$ 列的表格。表格中，第 $i$ 行第 $j$ 列的值为第 $i$ 个政党的票数除以 $j$。首个席位给表格中值最大的政党，依次类推。如果有多个条目值相同，席位将授予输入中排在最前的政党。 例如：如果要分配 5 个席位，每个政党的票数分别除以 1、2、3、4 和 5，结果如下表。表中加粗的数字是前五个最大的数值。由于 B 党和 D 党出现平局，但因 B 党在输入中排在前面，故将席位给 B 党。对每个加粗的值，对应的政党获得一个席位。 | 政党 | 获得票数 (V) | V/1 | V/2 | V/3 | V/4 | V/5 | 赢得席位 | |------|--------------|-----|-----|-----|-----|-----|----------| | A | 70 | **70** | **35** | 23.3 | 17.5 | 14 | 2 | | B | 60 | **60** | **30** | 20 | 15 | 12 | 2 | | C | 50 | **50** | 25 | 16.7 | 12.5 | 10 | 1 | | D | 30 | 30 | 15 | 10 | 7.5 | 6 | 0 | **选举方式 2：Sainte-Laguë 方法** 这一方法在挪威、瑞典和德国等国家使用，对小政党更为有利。选票计数后，议会席位逐一分配给商数最高的政党。政党的商数通过下面公式计算：**quot = V / (2s+1)** 其中： - **V** 是该政党获得的总票数， - **s** 是该政党已分配的席位数，起初为 0。 如果多个政党商数相同，席位优先给输入中排先的政党。每分配一个席位后，重新计算商数，直到所有席位分配完毕。 例如，使用之前的例子： | 政党 | 获得票数 (V) | 第 1 轮 quot | 第 2 轮 quot | 第 3 轮 quot | 第 4 轮 quot | 第 5 轮 quot | 赢得席位 | |------|--------------|--------------|--------------|--------------|--------------|--------------|----------| | A | 70 | **70** | 23.3 | 23.3 | 23.3 | **23.3** | 2 | | B | 60 | 60 | **60** | 20 | 20 | 20 | 1 | | C | 50 | 50 | 50 | **50** | 16.7 | 16.7 | 1 | | D | 30 | 30 | 30 | 30 | **30** | 10 | 1 | 表中加粗的数字表示当前轮次的最高商数，对应政党赢得一个席位。

输入的第一行为测试用例的数量 $T$。随后是 $T$ 个测试用例。每个测试用例的第一行为两个整数 $N$ 和 $S$，用一个空格分隔。$N$ 表示政党的数量，$S$ 表示要分配的席位数。接下来的 $N$ 行中，每行包含一个唯一的政党组名，长度不超过 20 的英文字母，后跟一个空格，再接一个整数 $V[i]$，表示该政党预期的票数。

对于每个测试用例，输出一行，格式为 `Case K: Method`，其中 $K$ 表示测试用例编号；`Method` 选择 `"S"`、`"D"` 或 `"No difference"`。 - `Method = "D"` 如果 D'Hondt 方法让 ACM 党赢得更多席位； - `Method = "S"` 如果 Sainte-Laguë 方法让 ACM 党赢得更多席位； - 若两种方法结果相同，则 `Method = "No difference"`。

- $1 \le T \le 100$ - $2 \le N \le 100$ - $1 \le S \le 100$ - $0 \le V[i] \le 10^6$ **本翻译由 AI 自动生成**