{"raw_statement":[{"iden":"statement","content":"One university has just found out about a sport programming contest called ACM ICPC v2.0. This contest doesn't differ much from the well-known ACM ICPC, for example, the participants are not allowed to take part in the finals more than two times. However, there is one notable difference: the teams in the contest should consist of exactly _n_ participants.\n\nHaving taken part in several ACM ICPC v2.0 finals and having not won any medals, the students and the university governors realized that it's high time they changed something about the preparation process. Specifically, as the first innovation it was decided to change the teams' formation process. Having spent considerable amount of time on studying the statistics of other universities' performance, they managed to receive some interesting information: the dependence between the probability of winning a medal and the number of team members that participated in the finals in the past. More formally, we know _n_ + 1 real numbers _p_0 ≤ _p_1 ≤ ... ≤ _p__n_, where _p__i_ is the probability of getting a medal on the finals if the team has _i_ participants of previous finals, and other _n_ - _i_ participants arrived to the finals for the first time.\n\nDespite such useful data, the university governors are unable to determine such team forming tactics that would provide the maximum probability of winning a medal at ACM ICPC v2.0 finals on average (we are supposed to want to provide such result to the far future and we are also supposed to have an endless supply of students). And how about you, can you offer such optimal tactic? At the first stage the university governors want to know the value of maximum average probability.\n\nMore formally, suppose that the university sends a team to the _k_\\-th world finals. The team has _a__k_ participants of previous finals (0 ≤ _a__k_ ≤ _n_). Since each person can participate in the finals no more than twice, the following condition must be true: . Your task is to choose sequence so that the limit Ψ exists and it's value is maximal:\n\nAs is an infinite sequence, you should only print the maximum value of the Ψ limit."},{"iden":"input","content":"The first line contains an integer _n_ (3 ≤ _n_ ≤ 100), _n_ is the number of team participants. The second line contains _n_ + 1 real numbers with no more than 6 digits after decimal point _p__i_ (0 ≤ _i_ ≤ _n_, 0 ≤ _p__i_ ≤ 1) — the probability of that the team will win a medal if it contains _i_ participants who has already been on the finals. Also the condition _p__i_ ≤ _p__i_ + 1 should be fulfilled for all 0 ≤ _i_ ≤ _n_ - 1."},{"iden":"output","content":"Print the only real number — the expected average number of medals won per year if the optimal strategy is used. The result may have absolute or relative error 10 - 6."},{"iden":"examples","content":"Input\n\n3\n0.115590 0.384031 0.443128 0.562356\n\nOutput\n\n0.4286122500\n\nInput\n\n3\n1 1 1 1\n\nOutput\n\n0.9999999999"},{"iden":"note","content":"In the second test, no matter what participants the team contains, it is doomed to be successful."}],"translated_statement":[{"iden":"statement","content":"一所大学刚刚得知一项名为 ACM ICPC v2.0 的编程竞赛。该竞赛与广为人知的 ACM ICPC 差异不大，例如，参赛者最多只能参加两次决赛。然而，有一个显著的不同之处：竞赛中的队伍必须由恰好 #cf_span[n] 名成员组成。\n\n在多次参加 ACM ICPC v2.0 决赛却未赢得任何奖牌后，学生们和大学管理者意识到，是时候改变备赛策略了。作为首个创新，他们决定改变队伍的组建方式。经过大量时间研究其他大学的表现统计，他们获得了有趣的信息：赢得奖牌的概率与队伍中过去曾参加过决赛的成员数量之间的关系。更正式地，我们已知 #cf_span[n + 1] 个实数 #cf_span[p0 ≤ p1 ≤ ... ≤ pn]，其中 #cf_span[pi] 表示当队伍中有 #cf_span[i] 名过去曾参加过决赛的成员，其余 #cf_span[n - i] 名成员是首次参赛时，队伍赢得奖牌的概率。\n\n尽管拥有如此有用的数据，大学管理者仍无法确定一种能最大化平均获奖概率的队伍组建策略（我们假设目标是面向遥远的未来，且学生资源无限）。那么你呢？你能提供这种最优策略吗？在第一阶段，大学管理者希望知道最大平均概率的值。\n\n更正式地，假设大学向第 #cf_span[k] 届世界决赛派出一支队伍。该队伍包含 #cf_span[ak] 名过去曾参赛的成员（#cf_span[0 ≤ ak ≤ n]）。由于每人最多只能参赛两次，必须满足以下条件：。你的任务是选择一个序列  ，使得极限 #cf_span[Ψ] 存在且取值最大：\n\n由于  是一个无限序列，你只需输出极限 #cf_span[Ψ] 的最大值。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 100]），#cf_span[n] 是队伍成员数量。第二行包含 #cf_span[n + 1] 个实数，小数点后不超过 6 位数字 #cf_span[pi]（#cf_span[0 ≤ i ≤ n, 0 ≤ pi ≤ 1]）——表示当队伍包含 #cf_span[i] 名曾参加过决赛的成员时，队伍赢得奖牌的概率。同时，对所有 #cf_span[0 ≤ i ≤ n - 1]，必须满足条件 #cf_span[pi ≤ pi + 1]。\n\n输出一个实数——若采用最优策略，每年平均赢得奖牌的期望数量。结果的绝对误差或相对误差不得超过 #cf_span[10 - 6]。\n\n在第二个测试用例中，无论队伍由哪些成员组成，都注定会成功。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 100]），#cf_span[n] 是队伍成员数量。第二行包含 #cf_span[n + 1] 个实数，小数点后不超过 6 位数字 #cf_span[pi]（#cf_span[0 ≤ i ≤ n, 0 ≤ pi ≤ 1]）——表示当队伍包含 #cf_span[i] 名曾参加过决赛的成员时，队伍赢得奖牌的概率。同时，对所有 #cf_span[0 ≤ i ≤ n - 1]，必须满足条件 #cf_span[pi ≤ pi + 1]。"},{"iden":"output","content":"输出一个实数——若采用最优策略，每年平均赢得奖牌的期望数量。结果的绝对误差或相对误差不得超过 #cf_span[10 - 6]。"},{"iden":"examples","content":"输入30.115590 0.384031 0.443128 0.562356输出0.4286122500输入31 1 1 1输出0.9999999999"},{"iden":"note","content":"在第二个测试用例中，无论队伍由哪些成员组成，都注定会成功。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 100 $.  \nLet $ \\mathbf{p} = (p_0, p_1, \\dots, p_n) \\in [0,1]^{n+1} $ be a non-decreasing sequence: $ p_0 \\leq p_1 \\leq \\dots \\leq p_n $.  \n\nLet $ \\mathbf{a} = (a_1, a_2, \\dots) $ be an infinite sequence with $ a_k \\in \\{0, 1, \\dots, n\\} $ for all $ k \\geq 1 $, representing the number of veteran participants (those who previously participated) in the team sent to the $ k $-th finals.  \n\n**Constraints**  \n1. Each participant may appear in at most two finals.  \n   Thus, if a participant is selected in year $ k $, they may be selected again in year $ k+1 $, but not in year $ k+2 $.  \n   This imposes a global constraint on the evolution of veteran counts over time, governed by the selection rule.  \n\n2. The sequence $ \\mathbf{a} $ must be feasible under the \"at most two appearances\" rule:  \n   Let $ x_k^{(i)} $ denote the number of participants with exactly $ i $ prior appearances in year $ k $.  \n   Then:  \n   - $ x_k^{(0)} + x_k^{(1)} = n $,  \n   - $ a_k = x_k^{(1)} $,  \n   - Transition:  \n     $ x_{k+1}^{(0)} = x_k^{(0)} + (n - a_k) $,  \n     $ x_{k+1}^{(1)} = a_k $,  \n     $ x_{k+1}^{(2)} = 0 $ (since participants with two appearances are retired).  \n\n   Therefore:  \n   $$\n   a_{k+1} = a_k \\quad \\text{is not allowed unless } a_k = n.\n   $$  \n   Actually, the state evolves as:  \n   $$\n   a_{k+1} = a_k - r + s, \\quad \\text{where } r \\text{ is retired, } s \\text{ is new},\n   $$  \n   But since retired = those with 1 prior appearance who are not reselected, and new = $ n - a_k $,  \n   the correct recurrence is:  \n   $$\n   a_{k+1} = \\text{number of veterans reselected} \\leq a_k, \\quad \\text{and} \\quad a_{k+1} \\leq n - (n - a_k) = a_k?  \n   $$  \n\n   **Simpler state representation:**  \n   Let $ s_k = a_k $. Then the number of *new* participants in year $ k $ is $ n - s_k $.  \n   These $ n - s_k $ new participants become veterans in year $ k+1 $.  \n   The $ s_k $ veterans from year $ k $ can be reselected (at most $ s_k $ of them), but if reselected, they become *ex-veterans* (i.e., retired after this year).  \n   So in year $ k+1 $, the number of veterans is exactly the number of *new* participants from year $ k $ who were *not* reselected? No.  \n\n   **Correct state transition:**  \n   - At year $ k $:  \n     - $ s_k $ participants have 1 prior appearance (veterans).  \n     - $ n - s_k $ have 0 prior appearances (new).  \n   - After year $ k $:  \n     - The $ n - s_k $ new participants now have 1 appearance.  \n     - The $ s_k $ veterans now have 2 appearances → they are retired and cannot appear again.  \n   - So in year $ k+1 $, the only possible veterans are the $ n - s_k $ participants who were new in year $ k $.  \n   - Therefore:  \n     $$\n     s_{k+1} \\leq n - s_k\n     $$  \n     and $ s_{k+1} \\in \\{0, 1, \\dots, n - s_k\\} $.  \n\n   **Thus, the constraint is:**  \n   $$\n   s_{k+1} \\leq n - s_k, \\quad \\forall k \\geq 1.\n   $$  \n\n**Objective**  \nDefine the long-run average probability:  \n$$\n\\Psi = \\lim_{K \\to \\infty} \\frac{1}{K} \\sum_{k=1}^K p_{s_k}\n$$  \nWe wish to choose a feasible sequence $ \\mathbf{s} = (s_1, s_2, \\dots) $ satisfying $ s_k \\in \\{0,1,\\dots,n\\} $ and $ s_{k+1} \\leq n - s_k $ for all $ k $, such that $ \\Psi $ is maximized.  \n\n**Goal**  \nCompute $ \\max \\Psi $, the maximum possible value of the long-run average medal probability under the transition constraint.","simple_statement":null,"has_page_source":false}