专栏首页算法修养ZOJ 3705 Applications

ZOJ 3705 Applications

Recently, the ACM/ICPC team of Marjar University decided to choose some new members from freshmen to take part in the ACM/ICPC competitions of the next season. As a traditional elite university in ACM/ICPC, there is no doubt that application forms will fill up the mailbox. To constitute some powerful teams, coaches of the ACM/ICPC team decided to use a system to score all applicants, the rules are described as below. Please note that the score of an applicant is measured by pts, which is short for "points".

1. Of course, the number of solved ACM/ICPC problems of a applicant is important. Proudly, Marjar University have a best online judge system calledMarjar Online Judge System V2.0, and in short, MOJ. All solved problems in MOJ of a applicant will be scored under these rules:

  • (1) The problems in a set, called MaoMao Selection, will be counted as 2.5 pts for a problem.
  • (2) The problems from Old Surgeon Contest, will be counted as 1.5 pts for a problem.There is no problem in MaoMao Selection from Old Surgeon Contest.
  • (3) Besides the problem from MaoMao Selection and Old Surgeon Contest, if the problem's id is a prime, then it will be counted as 1 pts.
  • (4) If a solved problem doesn't meet above three condition, then it will be counted as 0.3 pts.

2. Competitions also show the strength of an applicant. Marjar University holds the ACM/ICPC competition of whole school once a year. To get some pts from the competition, an applicant should fulfill rules as below:

  • The member of a team will be counted as 36 pts if the team won first prize in the competition.
  • The member of a team will be counted as 27 pts if the team won second prize in the competition.
  • The member of a team will be counted as 18 pts if the team won third prize in the competition.
  • Otherwise, 0 pts will be counted.

3. We all know that some websites held problem solving contest regularly, such as JapanJamZacaiForces and so on. The registered member ofJapanJam will have a rating after each contest held by it. Coaches thinks that the third highest rating in JapanJam of an applicant is good to show his/her ability, so the scoring formula is:

Pts = max(0, (r - 1200) / 100) * 1.5

Here r is the third highest rating in JapanJam of an applicant.

4. And most importantly - if the applicant is a girl, then the score will be added by 33 pts.

The system is so complicated that it becomes a huge problem for coaches when calculating the score of all applicants. Please help coaches to choose the best M applicants!

Input

There are multiple test cases.

The first line of input is an integer T (1 ≤ T ≤ 10), indicating the number of test cases.

For each test case, first line contains two integers N (1 ≤ N ≤ 500) - the number of applicants and M (1 ≤ M ≤ N) - the number of members coaches want to choose.

The following line contains an integer R followed by R (0 ≤ R ≤ 500) numbers, indicating the id of R problems in MaoMao Selection.

And then the following line contains an integer S (0 ≤ S ≤ 500) followed by S numbers, indicating the id of S problems from Old Surgeon Contest.

The following line contains an integer Q (0 ≤ Q ≤ 500) - There are Q teams took part in Marjar University's competition.

Following Q lines, each line contains a string - team name and one integer - prize the team get. More specifically, 1 means first prize, 2 means second prize, 3 means third prize, and 0 means no prize.

In the end of each test case, there are N parts. In each part, first line contains two strings - the applicant's name and his/her team name in Marjar University's competition, a char sex - M for male, F for female and two integers P (0 ≤ P ≤ 1000) - the number of problem the applicant solved, C (0 ≤C ≤ 1000) - the number of competitions the applicant have taken part in JapanJam.

The following line contains P integers, indicating the id of the solved problems of this applicant.

And, the following line contains C integers, means the rating for C competitions the applicant have taken part in.

We promise:

  • The problems' id in MaoMao SelectionOld Surgeon Contest and applicant's solving list are distinct, and all of them have 4 digits (such as 1010).
  • All names don't contain spaces, and length of each name is less than 30.
  • All ratings are non-negative integers and less than 3500.

Output

For each test case, output M lines, means that M applicants and their scores. Please output these informations by sorting scores in descending order. If two applicants have the same rating, then sort their names in alphabet order. The score should be rounded to 3 decimal points.

Sample Input

1
5 3
3 1001 1002 1003
4 1004 1005 1006 1007
3
MagicGirl!!! 3
Sister's_noise 2
NexusHD+NexusHD 1
Edward EKaDiYaKanWen M 5 3
1001 1003 1005 1007 1009
1800 1800 1800
FScarlet MagicGirl!!! F 3 5
1004 1005 1007
1300 1400 1500 1600 1700
A NexusHD+NexusHD M 0 0


B None F 0 0


IamMM Sister's_noise M 15 1
1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015
3000

Sample Output

FScarlet 60.000
IamMM 44.300
A 36.000
小模拟#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>

using namespace std;
int n,m;
struct Node
{
    string team;
    string name;
    double score;
}res[505];
int cmp(Node a,Node b)
{
    if(a.score==b.score)
        return a.name<b.name;
    return a.score>b.score;
}

int c[1005];
int p[1005];
int cmp2(int x,int y)
{
    return x>y;
}
int judge(int x)
{
    for(int i=2;i*i<=x;i++) {if(x%i==0) return 0;}
           return 1;
}
int r,s;
int r1,s1;
map<string,int> m4;
int m1[3010];
int m2[3010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        m4.clear();
        memset(m1,0,sizeof(m1));
        memset(m2,0,sizeof(m2));

        int m3[1005];
        m3[3]=18;m3[2]=27;m3[1]=36;
        scanf("%d%d",&n,&m);
        scanf("%d",&r);
        int oo;
        for(int i=1;i<=r;i++)
        {
            scanf("%d",&oo);
            m1[oo]=1;
        }
        scanf("%d",&s);
        for(int i=1;i<=s;i++)
        {
            scanf("%d",&oo);
            m2[oo]=1;
        }
        int num;
        string ss;
        scanf("%d",&num);
        for(int i=1;i<=num;i++)
        {
            cin>>ss>>oo;
            m4[ss]=max(m4[ss],m3[oo]);
        }
        string cc;string dd;int ee;int ff;
        for(int i=1;i<=n;i++)
        {
            cin>>cc>>ss>>dd>>oo>>ee;
            res[i].name=cc;
            res[i].score=0;
            res[i].score+=1.0*m4[ss];
            if(dd=="F")
                res[i].score+=33.0;
            for(int j=1;j<=oo;j++)
            {
                scanf("%d",&ff);
                if(m1[ff])
                    res[i].score+=2.5;
                else if(m2[ff])
                    res[i].score+=1.5;
                else if(judge(ff))
                    res[i].score+=1.0;
                else
                    res[i].score+=0.3;
            }
            for(int j=1;j<=ee;j++)
            {
                scanf("%d",&c[j]);
            }
            if(ee<3)
                continue;
            sort(c+1,c+ee+1,cmp2);
            res[i].score+=max(0.0,(1.0*(c[3]-1200)/100)*1.5);
        }
        sort(res+1,res+1+n,cmp);
        for(int i=1;i<=m;i++)
        {
            cout<<res[i].name<<" ";
            printf("%.3f\n",res[i].score);
        }

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 不只是软件,在线也可以免费下载百度文库了。

    不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

    课代表
  • 考研英语-1-导学

    英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

    用户1335799
  • 【系统设置】CentOS 修改机器名

    ken.io
  • 复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

    从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

    haifeiWu
  • 中国互联网协会发布:《2018中国互联网发展报告》

    在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

    钱塘数据
  • 理工男图解零维到十维空间,烧脑已过度,受不了啦!

    让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

    钱塘数据
  • SQL中GROUP BY用法示例

    GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

    Awesome_Tang
  • 知识体系解决迷茫的你

    最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

    桃翁
  • 【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

    腾讯高校合作
  • ISUX Xcube智能一键生成H5

    腾讯ISUX

扫码关注云+社区

领取腾讯云代金券