The 3rd Collegiate Programming Contest of Central South University
Problem D. OSU! Scoring System
Description
OSU! is a rhythm game based on the gameplay of a variety of popular commercial rhythm games. The gameplay consists of only three elements: hit circles on the screen, dragging a ball across a fixed path and rotating a spinner very fast. To simplify the calculation, we assume that there are only hit circles in this game.
Here?s the scoring system of this game: Hit circle judgment
You get a 300, 100 or 50 from a normal hit circle depending on how accurately you click on it. If you do not click on the hit circle at all or click on it way too early you will receive a miss.
Combo
The initial of your combo is 0, and each successful hitting (300,100 or 50) add 1 point to your combo. A miss will reset your combo to 0.
Score
The score given by each hit circle is calculated with the following formula:
Score = HitValue + HitValue * (Combo multiplier * Difficulty multiplier * Mod multiplier) / 25
Hit value = The hit circle judgment (50, 100 or 300).
Combo multiplier = The max value between (Combo before this hit - 1) and 0. Difficulty multiplier = The difficulty setting for the beatmap. Mod multiplier = The multiplier of the selected mods. The total score is the sum of score given by each hit circle.
Accuracy
Accuracy = Total points of hits / (Total number of hits * 300) *100%
Total number of hits = (Number of misses + Number of 50's + Number of 100's + Number of 300's)
Total points of hits = (Number of 50s * 50 + Number of 100s * 100 + Number of 300s * 300)
In other words, each miss counts as 0 points, each 50 counts as 50 points, each 100 as 100 points and each 300 as 300 points. Add them all together and divide the sum with the number of hits multiplied by 300. If you score only 300s you will get a result of 1.00 which means 100% accuracy. If you score only 100s you will get a result of
5
The 3rd Collegiate Programming Contest of Central South University
0.3333 which means 33.33% accuracy.
Grades
After each play, you will get your grade according to your performance. SS = 100% accuracy
S = Over 90% 300s, less than 1% 50s and no misses. A = Over 80% 300s and no misses OR over 90% 300s. B = Over 70% 300s and no misses OR over 80% 300s. C = Over 60% 300s. D = Anything else.
Input
The first line contains a non-negative integer N, the number of test cases, at most 100. The first line of each test case contains three numbers, D, M and L (1 ≤ D ≤ 5, 1 ≤ M ≤ 1.5, 1 ≤ L ≤ 1000). D means Difficulty multiplier, M means Mod multiplier and L means the number of hit circles.
The second line of each test case contains L integers (0, 50, 100 or 300), which denote your performance of each hit circle. 0 means a miss.
Output
For each case, out put the total score, accuracy and grade on a line. (Accurate to two digits after decimal point.).
Sample Input
2
1 1.1 5
300 300 300 300 300 2 1.0 6
300 0 100 300 300 300
Sample Output
1579.20 100.00% SS 1372.00 72.22% C
6
The 3rd Collegiate Programming Contest of Central South University
Problem E. 五一步行街购物
Description
五一劳动节到了,焦同学要陪女朋友去步行街购物,但是五一去步行街购物的人相当多,大街上、商店里到处都是人,相当拥挤。焦同学想节省购物时间,不愿陪女朋友在街上来回走动,所以他计划一直从街头走向街尾,沿途所经过的商店里如果有他女朋友所需的商品,他就可以考虑购买。现在焦同学手上有份购物清单,并且也有份关于步行街旁各商店所出售的商品的名称及价格的详单。因为要买的东西太多,为避免买漏了东西,现在他计划按照购物清单上的顺序,依次购买各个物品,并且还要使总的费用最小。请问如何设计才能帮助焦同学实现他的计划。
为方便起见,用数字来代替商品的名称。关于详单上的记录,是按照各商店在步行街上的位置的先后关系依次给出各商店所出售的某种商品的名称及价格(对于每个商店仅给出一种所出售的物品的名称及价格,可以认为该商店只有这一种商品可以出售)。举个例子,下面的图一表示购物清单的内容,图二表示详单的内容(S1表示街头处的商店,Sn表示街尾处的商店)。
图一
商店 S1 S2 3 80 S3 2 40 S4 5 60 图二
S5 2 42 S6 5 65 S7 4 100 S8 1 30 商品 2 价格 50
7
The 3rd Collegiate Programming Contest of Central South University
Input
有多组测试数据。对于每一组测试数据,第一行有两个数字M和N,M (1 ≤ M ≤ 100)表示购物清单上需要购买的商品的数量,N(1 ≤ N ≤ 100000)表示详单上商店的数量,接下来一行为M个整数,依次表示购物清单上的物品名称,再接下来有N行,每行有两个整数,其中第i行第一个数字表示商店Si所出售物品的名称,第二个数字表示商店Si所出售物品的价格。当M=N=0时表示输入结束。
Output
对于每组测试数据,如果能帮完成购物计划,则输出完成购物计划最少需要的费用,若不能完成购物计划,则输出“Impossible”。
Sample Input
4 8 2 2 5 1 2 50 3 80 2 40 5 60 2 42 5 65 4 100 1 30 2 3 3 2 1 200 2 300 3 100 0 0
Sample Output
177
Impossible
8
相关推荐: