Problem 4C. Codeforces rating

Problem 4C. Codeforces rating

Problem 4C. Codeforces rating

题目描述

pzr 喜欢在知名编程网站 Codeforces 上打比赛。

在 Codeforces 网站上,每位参赛用户都有一个 rating 值,用来反映参赛选手的实力。

rating 的结算方法如下:

  • 每场比赛后,每位选手的排名会转换为表现分 P。

  • 比赛后的新 rating 的计算方法如下:

    • RR×34+P×14 R' \leftarrow R \times \frac{3}{4}+ P \times \frac{1}{4}

    • 其中 RR' 表示新 rating 值,RR 表示原来的 rating 值,PP 表示表现分。

    • 新的 rating 值允许为小数。

pzr 的初始 rating 为 rr,他非常希望增长他的 rating 值,于是使用魔法预知了他在未来 nn 场比赛的表现分 pip_i

  • ① 他可以 任意调换这些比赛的顺序
  • ② 他可以 选择不参加 某些比赛。

请问,这 nn 场比赛后,pzr 的最高可能 rating 是多少?

输入格式

第一行两个整数 n,rn, r,表示能够预知的比赛场数和初始 rating 值。

接下来一行 nn 个整数 pip_i,表示接下来 nn 场比赛的表现分。

输出格式

请将最高可能的 rating 值四舍五入为整数并输出。

样例输入1

4 100
50 200 100 150

样例输出1

134

样例1解释

先参加第四场比赛,再参加第二场比赛, rating 为 134.375。

数据范围及约定

对于 60%60\% 的数据,1n101\le n\le 10

对于 100%100\% 的数据,1n105,1r,pi1061\le n\le 10^5,1\le r,p_i\le 10^6

保证答案的小数部分 rr' 满足 r0.5>106|r'-0.5|>10^{-6},即细微的浮点误差不影响答案的正确性。

信息

ID
1532
难度
7
分类
(无)
标签
(无)
递交数
46
已通过
10
通过率
22%
上传者

相关

在下列训练计划中:

2023秋 悬赏令题单

在下列比赛中:

2023秋 悬赏令第四周