{"problem":{"name":"K. Rikka with Ants","description":{"content":"Every time when Rikka faces to a great nature sight, she will recall a line of ants moving in a hurry. Rikka loves ants and keeps two large colonies of ants in her drawer. Observing ants hurrying in m","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10201K"},"statements":[{"statement_type":"Markdown","content":"Every time when Rikka faces to a great nature sight, she will recall a line of ants moving in a hurry. Rikka loves ants and keeps two large colonies of ants in her drawer. Observing ants hurrying in moving has controlled her life.\n\nThat is why she prepares $n$ different nests in her drawer, and $n$ undirected channels between these nests form a circular orbit. All nests are numbered by $1$ to $n$ in order, and the lengths of channels are known. The first colony of ants is living in the $s_1$-th nest, and the second colony is living in the $s_2$-th nest.\n\nNow, ants decide to move to new nests together. The new home for these two colonies of ants will be the $e_1$-th nest and the $e_2$-th nest respectively.\n\nFor each colony, all ants should queue up one by one to crawl from the origin to the destination along a path. They cannot be split into several groups crawling moving along different paths. Then, they can measure the complexity of their plan moving to new nest using the total length of channels in the path selected.\n\nIf these two colonies of ants select paths sharing some common channels, they will walk through these channels slowly for security. Specifically, for each common channel, we can consider equivalently that its measured length will be tripled.\n\nAnts are highly intelligent and they all want to minimize the complexities of their plan. They will choose the best strategies for themselves respectively without negotiation. All they know are the lengths of channels, and the nests where their colony and the other one will start and end respectively.\n\nRikka wants you to calculate the expected complexities of plans for each colony of ants. For more details about the best strategy, please refer to note.\n\nThe input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 5000$), the number of test cases.\n\nFor each test case, the first line contains a single integer $n$ ($2 <= n <= 50$), the number of nests and also the number of channels between them.\n\nThe second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n$ ($1 <= a_i <= 50$), where the $i$-th one, $a_i$, represents the length of the undirected channel between the $i$-th nest and the $((i bmod n) + 1)$-th nest. It is guaranteed that the total length of the $n$ channels is odd.\n\nThe third line contains four integers $s_1, e_1, s_2$ and $e_2$ ($1 <= s_1, s_2, e_1, e_2 <= n$, $s_1 != e_1$, $s_2 != e_2$), representing the original nests where these ants live and their new nests.\n\nFor each test case, output a line with two space-separated numbers, representing the expected complexity for the first colony of ant and the expected complexity for the second colony respectively. Your answer is considered correct if the absolute or relative error between each number in your output and the corresponding one in Rikka's answer does not exceed $10^(-9)$. Formally, let a number of your answer be $a$, and the corresponding number of Rikka's answer be $b$. Your answer is considered correct if $frac(| a -b |, max (1 , | b |)) <= 10^(-9)$.\n\nWhat we are talking about including strategies, best strategies and expectations are actually what about Nash Equilibrium and mixed strategies.\n\nIn the theory of games, a player is said to use a mixed strategy whenever the player chooses to randomize over the set of available actions. Formally, a mixed strategy is a probability distribution that assigns to each available action a likelihood of being selected. If only one action has a positive probability of being selected, the player is said to use a pure strategy. In the first sample case, the best strategies for both colonies are pure strategies.\n\nA mixed strategy profile is a list of strategies, one for each player in the game. A mixed strategy profile induces a probability distribution or lottery over the possible outcomes of the game. In this problem, the profiles are those plans that we discussed before.\n\nA Nash equilibrium (mixed strategy) is a strategy profile with the property that no single player can, by deviating unilaterally to another strategy, induce a lottery that he or she finds strictly preferable. In $1950$, the mathematician John Nash proved that every game with a finite set of players and actions has at least one equilibrium.\n\nIn this problem, a Nash equilibrium is what you need to find. You may find out several different equilibriums. If some of them have the same unilateral strategy, their earnings must be constant.\n\nWe still need to discuss when several different equilibriums without fixed unilateral strategy exist. Notice that in this case, we have a unique equilibrium with mixed, impure strategies. Since ants like to show-off their intelligence, this equilibrium is exactly their final choices.\n\nIn the second test case, though we have three different equilibriums whose earnings are $(8, 10)$, $(13, 11)$ and $(14. 666 \\\\\\\\cdots, 14. 666 \\\\\\\\cdots)$, the last one is the earnings for the only equilibrium with mixed, impure strategies and thus is what we need.\n\n## Input\n\nThe input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 5000$), the number of test cases.For each test case, the first line contains a single integer $n$ ($2 <= n <= 50$), the number of nests and also the number of channels between them.The second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n$ ($1 <= a_i <= 50$), where the $i$-th one, $a_i$, represents the length of the undirected channel between the $i$-th nest and the $((i bmod n) + 1)$-th nest. It is guaranteed that the total length of the $n$ channels is odd.The third line contains four integers $s_1, e_1, s_2$ and $e_2$ ($1 <= s_1, s_2, e_1, e_2 <= n$, $s_1 != e_1$, $s_2 != e_2$), representing the original nests where these ants live and their new nests.\n\n## Output\n\nFor each test case, output a line with two space-separated numbers, representing the expected complexity for the first colony of ant and the expected complexity for the second colony respectively. Your answer is considered correct if the absolute or relative error between each number in your output and the corresponding one in Rikka's answer does not exceed $10^(-9)$. Formally, let a number of your answer be $a$, and the corresponding number of Rikka's answer be $b$. Your answer is considered correct if $frac(| a -b |, max (1 , | b |)) <= 10^(-9)$.\n\n[samples]\n\n## Note\n\nWhat we are talking about including strategies, best strategies and expectations are actually what about Nash Equilibrium and mixed strategies.In the theory of games, a player is said to use a mixed strategy whenever the player chooses to randomize over the set of available actions. Formally, a mixed strategy is a probability distribution that assigns to each available action a likelihood of being selected. If only one action has a positive probability of being selected, the player is said to use a pure strategy. In the first sample case, the best strategies for both colonies are pure strategies.A mixed strategy profile is a list of strategies, one for each player in the game. A mixed strategy profile induces a probability distribution or lottery over the possible outcomes of the game. In this problem, the profiles are those plans that we discussed before.A Nash equilibrium (mixed strategy) is a strategy profile with the property that no single player can, by deviating unilaterally to another strategy, induce a lottery that he or she finds strictly preferable. In $1950$, the mathematician John Nash proved that every game with a finite set of players and actions has at least one equilibrium.In this problem, a Nash equilibrium is what you need to find. You may find out several different equilibriums. If some of them have the same unilateral strategy, their earnings must be constant.We still need to discuss when several different equilibriums without fixed unilateral strategy exist. Notice that in this case, we have a unique equilibrium with mixed, impure strategies. Since ants like to show-off their intelligence, this equilibrium is exactly their final choices.In the second test case, though we have three different equilibriums whose earnings are $(8, 10)$, $(13, 11)$ and $(14. 666 \\\\\\\\cdots, 14. 666 \\\\\\\\cdots)$, the last one is the earnings for the only equilibrium with mixed, impure strategies and thus is what we need.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of nests and channels, arranged in a cycle.  \nLet $ a_i \\in \\mathbb{R}^+ $ for $ i \\in \\{1, \\dots, n\\} $ denote the length of the channel between nest $ i $ and nest $ (i \\bmod n) + 1 $.  \nLet $ s_1, e_1, s_2, e_2 \\in \\{1, \\dots, n\\} $ be the start and end nests for colony 1 and colony 2, respectively, with $ s_1 \\ne e_1 $, $ s_2 \\ne e_2 $.  \n\nLet $ P_1 $ and $ P_2 $ denote the set of simple paths from $ s_1 $ to $ e_1 $ and from $ s_2 $ to $ e_2 $ along the cycle, respectively.  \nEach path is uniquely determined by its direction (clockwise or counterclockwise) due to the cycle structure.  \n\nLet $ L(p) = \\sum_{e \\in p} a_e $ denote the length of path $ p $.  \nFor a pair of paths $ (p_1, p_2) \\in P_1 \\times P_2 $, define the **cost** for colony 1 as:  \n$$\nC_1(p_1, p_2) = L(p_1) + 2 \\cdot \\sum_{e \\in p_1 \\cap p_2} a_e\n$$  \nand for colony 2 as:  \n$$\nC_2(p_1, p_2) = L(p_2) + 2 \\cdot \\sum_{e \\in p_1 \\cap p_2} a_e\n$$  \n(since shared edges are tripled, adding an extra 2× their length).  \n\n**Constraints**  \n1. $ 1 \\le T \\le 5000 $  \n2. $ 2 \\le n \\le 50 $  \n3. $ 1 \\le a_i \\le 50 $ for all $ i $  \n4. Total length $ \\sum_{i=1}^n a_i $ is odd  \n5. $ s_1 \\ne e_1 $, $ s_2 \\ne e_2 $  \n\n**Objective**  \nFind the unique Nash equilibrium in mixed strategies. Since each colony has at most two pure strategies (clockwise or counterclockwise path), the game is a $ 2 \\times 2 $ bimatrix game.  \n\nLet the two pure strategies for colony 1 be $ p_1^{\\text{cw}}, p_1^{\\text{ccw}} $, and for colony 2 be $ p_2^{\\text{cw}}, p_2^{\\text{ccw}} $.  \nConstruct the payoff matrix $ (C_1, C_2) $ for all 4 strategy pairs.  \n\nDue to the structure of the cycle and the odd total length, the game has a **unique** mixed-strategy Nash equilibrium (as guaranteed by the problem).  \n\nLet $ x \\in [0,1] $ be the probability that colony 1 chooses its clockwise path, and $ y \\in [0,1] $ the probability that colony 2 chooses its clockwise path.  \n\nThe equilibrium $ (x^*, y^*) $ satisfies:  \n- Colony 1 is indifferent between its two pure strategies given $ y^* $:  \n  $$\n  C_1(p_1^{\\text{cw}}, y^*) = C_1(p_1^{\\text{ccw}}, y^*)\n  $$  \n- Colony 2 is indifferent between its two pure strategies given $ x^* $:  \n  $$\n  C_2(x^*, p_2^{\\text{cw}}) = C_2(x^*, p_2^{\\text{ccw}})\n  $$  \n\nSolve for $ x^* $ and $ y^* $, then compute the expected costs:  \n$$\n\\mathbb{E}[C_1] = x^* y^* C_1(p_1^{\\text{cw}}, p_2^{\\text{cw}}) + x^* (1 - y^*) C_1(p_1^{\\text{cw}}, p_2^{\\text{ccw}}) + (1 - x^*) y^* C_1(p_1^{\\text{ccw}}, p_2^{\\text{cw}}) + (1 - x^*) (1 - y^*) C_1(p_1^{\\text{ccw}}, p_2^{\\text{ccw}})\n$$  \n$$\n\\mathbb{E}[C_2] = x^* y^* C_2(p_1^{\\text{cw}}, p_2^{\\text{cw}}) + x^* (1 - y^*) C_2(p_1^{\\text{cw}}, p_2^{\\text{ccw}}) + (1 - x^*) y^* C_2(p_1^{\\text{ccw}}, p_2^{\\text{cw}}) + (1 - x^*) (1 - y^*) C_2(p_1^{\\text{ccw}}, p_2^{\\text{ccw}})\n$$  \n\nOutput $ \\mathbb{E}[C_1] $ and $ \\mathbb{E}[C_2] $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10201K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}