P13249 [GCJ 2014 #1A] Proper Shuffle

一个大小为 $N$ 的排列是一个长度为 $N$ 的序列，其中每个数字都在 $0$ 到 $N-1$ 之间，且每个数字恰好出现一次。它们可以以任意顺序排列。 一共有很多（准确来说是 $N!$ 个，但在本题中这并不重要）大小为 $N$ 的排列。有时候我们希望**均匀随机**地选出一个排列：即每个排列被选中的概率完全相同。 下面是一个能达到这一目标的算法伪代码（我们在后文称之为 **GOOD** 算法）： ``` for k in 0 .. N-1: a[k] = k for k in 0 .. N-1: p = randint(k .. N-1) swap(a[k], a[p]) ``` 在上面的代码中，`randint(a .. b)` 表示在 $a$ 到 $b$（包括两端）之间均匀随机地选取一个整数。 用文字描述这个算法：我们从一个初始排列开始，即 $0$ 到 $N-1$ 按升序排列。接着，对于每一个 $k$ 从 $0$ 到 $N-1$，我们在区间 $[k, N-1]$ 中随机选择一个整数 $p_k$，然后交换排列中第 $k$ 个位置（从 $0$ 开始编号）和第 $p_k$ 个位置上的元素。 来看一个 $N=4$ 的例子。初始排列为： $$0 \ 1 \ 2 \ 3$$ 当 $k=0$ 时，我们在 $0$ 到 $3$ 之间随机选择 $p_0$，假设选中 $2$。交换第 $0$ 个和第 $2$ 个元素，排列变为： $$2 \ 1 \ 0 \ 3$$ 接着 $k=1$，在 $1$ 到 $3$ 之间随机选择 $p_1$，假设选中 $2$。交换第 $1$ 个和第 $2$ 个元素，排列变为： $$2 \ 0 \ 1 \ 3$$ 当 $k=2$ 时，在 $2$ 到 $3$ 之间随机选择 $p_2$，假设选中 $3$。交换第 $2$ 个和第 $3$ 个元素，排列变为： $$2 \ 0 \ 3 \ 1$$ 当 $k=3$ 时，只能选 $3$，交换第 $3$ 个和第 $3$ 个元素，排列不变： $$2 \ 0 \ 3 \ 1$$ 至此，生成的随机排列结束。 还有许多其他算法可以生成均匀随机的排列。然而，也存在很多与上面算法看似相似，但并不均匀的算法——这些算法生成某些排列的概率会比其他排列高。 下面给出一个此类「坏」算法（我们在后文称之为 **BAD** 算法）。它与 **GOOD** 算法非常相似，但在每一步中，$p_k$ 不再从 $[k, N-1]$ 区间中选择，而是从 $[0, N-1]$ 区间中随机选择。这看似是一个小改动，但结果是某些排列会更容易被生成！ 下面是该算法的伪代码： ``` for k in 0 .. N-1: a[k] = k for k in 0 .. N-1: p = randint(0 .. N-1) swap(a[k], a[p]) ``` 在每个测试用例中，你会获得一个由以下方式生成的排列：首先，我们以 $50\%$ 的概率选择 **GOOD** 算法或 **BAD** 算法，然后使用选中的算法生成一个排列。你需要根据给定的排列，猜测它是由哪个算法生成的。 这道题在 Code Jam 中比较特别。你将会得到 $T = 120$ 个大小为 $N = 1000$ 的排列，并需要为每个排列输出一个答案——这部分流程是常规的。然而，你并不需要全部答对！只要你猜对至少 $G = 109$ 个测试用例，整体答案就会被判定为正确。但无论是否正确，你仍需按照格式输出所有答案。如果出错，唯一允许的错误是把 **GOOD** 错猜成 **BAD** 或反之；但是对于每个测试用例，你都必须打印 "GOOD" 或 "BAD"。 保证给出的每个排列都严格按照上述方法独立生成。 这道题涉及随机性，因此即使是最优策略，也有可能在某次提交中因为概率原因导致答对数不足 $109$ 个而失败。如果发生这种情况，可以再次提交相同的策略尝试，因为每次重新提交可能运气不同。不过注意，若因为错误提交而重新提交，即使仅仅是运气导致错误，也会产生常规的 4 分钟罚时。 在我们的经验中，确实出现过由于概率原因导致答案错误的情况；因此，如果你确信自己的方案正确，但未通过，合理的策略是再次尝试相同方案。 祝你好运！

输入的第一行是测试用例数 $T$（始终为 $120$）。每个测试用例包含两行：第一行是单个整数 $N$（始终为 $1000$），第二行是 $N$ 个用空格分隔的整数，表示一个由两种算法之一生成的排列。

对于每个测试用例，输出一行 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 "GOOD" 或 "BAD"（不包含引号）。若你猜测该排列由题目中第一个描述的算法（**GOOD** 算法）生成，则输出 "GOOD"；否则输出 "BAD"。

**样例说明** 示例输入不符合题面中的大小限制——实际测试输入会更大。 ## 限制条件（45 分） - $T = 120$ - $G = 109$ - $N = 1000$ - 每个排列中的数字都在 $0$ 到 $N-1$ 之间，且 $0$ 到 $N-1$ 每个数字恰好出现一次。 翻译由 ChatGPT-4o 完成。