QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8227. 圆

统计

小德是北京大学的一名学生助教。现在一学期的课程结束了,老师希望小德能统计学生的最终成绩,并提交给教务。根据小德的观察,一位老师累加分数的过程可以被下述过程描述:

  1. 假设这一门课程有 $n$ 个项目,每个项目的得分都是一个保留到小数点后一位的实数。小德记项目得分的可重集合为 $S$。
  2. 重复若干次操作,每一次操作老师会从下面 A,B 两个方案中选择一个执行,直到 $S$ 只剩下一个项目得分:
    • A. 老师在 $S$ 中取出一个项目的得分 $x$,将 $x$ 四舍五入到整数后作为新的项目得分放回 $S$。
    • B. 老师在 $S$ 中取出两个不同的项目的得分 $x,y$,将 $x+y$ 作为新的项目得分放回 $S$。
  3. 老师取出 $S$ 中唯一的项目得分 $x$,将 $x$ 四舍五入到整数后提交给教务。

小德是一名善良的学生,作为过来人,他希望给学生尽可能高的成绩。小德想知道,按照上述加分规则,他提交给教务的成绩最高可能是多少,你能帮帮他吗?

输入格式

本题的测试点包含有多组测试数据。

第一行一个正整数 $T$ 表示测试数据组数。

下面每组测试数据第一行一个正整数 $n$,表示课程的项目数。

接下来一行 $n$ 个实数 $a_i$,每个数小数点后都恰有一个数字。

输出格式

对于每组数据,一行一个整数表示答案。

样例数据

输入格式

2
2
4.4 5.4
6
0.4 0.3 7.3 2.3 4.3 3.3

输出格式

10
19

子任务

对于所有数据:$1 \leq T \leq 10^4, 1 \leq \sum n \leq 10^6$, $0 \leq a_i \lt 10$。

子任务编号 数据范围 特殊性质 分值
1 $n \leq 5$ $20$
2 $T \leq 100, n \leq 12 $ $15$
3 $n \leq 80$ $17$
4 $a_i$ 都是 $0.2$ 的倍数 $21$
5 $27$