Problem 2382. -- 打怪物

2382: 打怪物

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

有N只怪物,第i只怪物的能量是blood[i]。你有一种攻击武器,称为"三连冲击波",每使用一次这个攻击武器,
你都可以选择三只怪物被杀伤,它的杀伤力是这样的:
一、首先被冲击的那只怪物的能量会减少9。
二、其次被冲击的那只怪物的能量会减少3。(N>=2时有效)
三、最后被冲击的那只怪物的能量会减少1。(N>=3时有效)
当某只怪物的能量为0或者低于0时,该怪物就会灭亡。
你可以按照你的意愿来确定每一次使用攻击武器时,怪物受到冲击的次序。
你的任务是计算,至少要使用多少次攻击武器,才能消灭N只怪物?
注意:
1、当怪物的能力小于等于0时,你依然可以对它进行攻击。
2、在一轮攻击中,同一只怪物不能被攻击多次。

Input

多组测试数据。
第一行,一个整数R,表示有R组测试数据。 1 <= R <= 5。
每组测试数据格式如下:
第一行,一个整数N。 1 <= N <= 20。
第二行,有N个正整数: 第i个正整数是blood[i],1 <= blood[i] <= 60。

Output

共R行,每行一个整数

Sample Input

5
20
60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60
20
18 42 44 33 23 7 42 44 8 23 26 48 11 58 43 15 4 29 24 52
3
9 2 2
3
45 17 3
3
3 5 18

Sample Output

93
46
2
6
3

HINT

Source

[Submit][Status]