P17428 [ICPC 2018 Xuzhou R] Rikka with Ants

每当 Rikka 面对壮丽的自然景观时，她脑海中总会浮现出一队蚂蚁匆匆前行的队列。Rikka 喜爱蚂蚁，并在她的抽屉里饲养了庞大的两群蚂蚁。观察蚂蚁忙碌地移动已经支配了她的生活。 正因如此，她在抽屉里准备了 $n$ 个不同的蚁巢，而这些蚁巢之间的 $n$ 条无向通道构成了一个环形轨道。所有蚁巢按顺序从 $1$ 到 $n$ 编号，且每条通道的长度均为已知。第一群蚂蚁居住在第 $s_1$ 号蚁巢，第二群蚂蚁居住在第 $s_2$ 号蚁巢。 现在，蚂蚁们决定一同搬迁到新的蚁巢。这两群蚂蚁的新家将分别是第 $e_1$ 号蚁巢和第 $e_2$ 号蚁巢。 对于每一群蚂蚁，所有蚂蚁必须一个接一个地排成一列，沿着某条路径从起点爬向终点。它们不能分成多个小组沿不同的路径爬行。随后，它们可以通过所选路径上的通道总长度来衡量它们搬家计划的复杂度。 如果这两群蚂蚁选择的路径共享了一些公共通道，出于安全考虑，它们将会缓慢地通过这些通道。具体来说，对于每条公共通道，我们可以等效地认为其被计入的长度将变为原来的三倍。 蚂蚁们非常聪明，它们都希望最小化各自计划的复杂度。它们将在不进行协商的情况下各自选择对自己最优的策略。它们所知道的全部信息只有通道的长度，以及自己的蚁群和对方蚁群各自的起点和终点蚁巢。 Rikka 希望你能计算每一群蚂蚁的期望计划复杂度。关于最佳策略的更多细节，请参见说明。

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 5000$），表示测试数据的组数。 对于每组测试数据，第一行包含一个整数 $n$（$2 \le n \le 50$），表示蚁巢的数量，同时也是它们之间通道的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 50$），其中第 $i$ 个数 $a_i$ 表示连接第 $i$ 号蚁巢与第 $((i \bmod n) + 1)$ 号蚁巢的无向通道的长度。**保证这 $n$ 条通道的总长度为奇数。** 第三行包含四个整数 $s_1, e_1, s_2$ 和 $e_2$（$1 \le s_1, s_2, e_1, e_2 \le n$，$s_1 \ne e_1$，$s_2 \ne e_2$），分别表示这些蚂蚁原本居住的蚁巢和它们的新蚁巢。

对于每组测试数据，输出一行包含两个由空格分隔的数，分别表示第一群蚂蚁的期望复杂度与第二群蚂蚁的期望复杂度。若你的输出中每个数与 Rikka 答案中对应数的绝对误差或相对误差均不超过 $10^{-9}$，则视为正确。具体地，设你的某个答案为 $a$，Rikka 答案中对应的数为 $b$，若满足 $\frac{|a - b|}{\max(1, |b|)} \le 10^{-9}$，则你的答案被视为正确。

我们所讨论的策略、最佳策略以及期望，实际上都是关于纳什均衡和混合策略的内容。 在博弈论中，若一个参与人在其可用的行动集合上进行随机化选择，则称该参与人使用了一个混合策略。形式化地，一个混合策略是一个概率分布，它为每一个可用行动分配了一个被选中的可能性。如果只有一个行动以正概率被选中，则称该参与人使用了一个纯策略。在第一组样例中，两群蚂蚁的最佳策略都是纯策略。 一个混合策略组合是游戏中每个参与人各出一个策略所形成的列表。一个混合策略组合会在游戏的可能结果上诱导出一个概率分布或彩票。在本题中，这些组合就是我们之前讨论的那些计划。 一个纳什均衡（混合策略）是具有如下性质的策略组合：没有任何一个参与人能够通过单方面偏离到另一个策略，从而获得一个他或她认为严格更优的彩票。1950 年，数学家约翰·纳什证明了每一个具有有限参与人和有限行动的游戏都至少存在一个均衡。 在本题中，你需要寻找的正是这样一个纳什均衡。你可能会找出若干个不同的均衡。如果其中一些均衡具有相同的单方面策略，那么它们的收益必定是常数。 我们仍需讨论当存在多个不具有固定单方面策略的不同均衡时的情况。注意在这种情况下，我们有一个唯一的、混合而非纯策略的均衡。由于蚂蚁们喜欢炫耀它们的智慧，这个均衡恰好就是它们最终的选择。 在第二组测试用例中，尽管我们存在三个不同的均衡，其收益分别为 $(8,10)$、$(13,11)$ 和 $(14.666 \cdots,14.666 \cdots)$，但最后一个收益正是那个唯一的混合、非纯策略均衡的收益，因此也是我们所需要的答案。 翻译由 DeepSeek V4 Pro 完成