← 返回题目列表

AtCoder · agc044_e

E. 随机典当

中文机器翻译题面 查看原题

分数: 1300 点

问题陈述

您正在玩游戏,您的目标是最大化您的预期收益。 游戏开始时,棋子被均匀随机地放置在某个位置 p\in\{1,2,\dots, N\}.The N 位置排列在一个圆上(以便 1 介于 N 和 2).

游戏由回合组成。在每个回合,你都可以结束游戏,并获得 A_p 美元(其中 p 是棋子的当前位置),或者支付 B_p 美元继续玩。 如果您决定继续玩,棋子会随机移动到两个相邻位置之一 p-1, p+1 (带有标识 0 = N 和 N+1=1).

最优策略的预期收益是多少?

注意:“最优策略的期望收益”应定义为所有策略中期望收益的上限值,使得游戏以 有限 圈数。

约束

  • 2 \le N \le 200,000
  • 0 \le A_p \le 10^{12} 对于任何 p = 1,\ldots, N
  • 0 \le B_p \le 100 对于任何 p = 1, \ldots, N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

输出

打印一个实数,即最优策略的预期收益。 如果您的答案的相对或绝对误差不超过 10^{-10}.


样本输入 1

5
4 2 6 3 5
1 1 1 1 1

示例输出 1

4.700000000000

示例输入 2

4
100 0 100 0
0 100 0 100

示例输出 2

50.000000000000

示例输入 3

14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4

示例输出 3

7047.142857142857

示例输入 4

10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61

示例输出 4

815899161079.400024414062