P6363 software engineering practice

Title Description

The compulsory course of software engineering in a university is divided into theory and practice. The theoretical part is taught by the professor of the University; The practice part is dominated by a third-party company. Students need to self-study HTML, css, JavaScript, vue, Python, django and other technologies within five weeks, and form a team to complete a real Internet business application.

There are \ (n(0\le n \le 1000) \) students participating in this course, which are divided into no more than \ (26 \) teams. Each team is represented by \ (A \) to \ (Z \). Each team will complete A project and score all teams (including their own teams) in teams, ranging from \ (0 \) to \ (100 \).

In order to calm the students' dissatisfaction with many problems arising from this course (such as too much workload, too tight time, unfair assessment methods, etc.), the teacher decided to use a "seemingly" fair way to determine the project score of each team:

For a team, first calculate the average value of the scores given to the team by all teams (including yourself), then eliminate the scores that are more than \ (15 \) different from the average value (ensure that all scores will not be eliminated), and finally calculate the average value of the remaining scores, which will be rounded as the project score of the team.

For each student, we have learned their team code and theoretical score (also an integer from \ (0 \) to \ (100 \). The student's final score is the theoretical score of \ (60 \% \) plus the project score of his team of \ (40 \% \), and then rounded to the nearest whole.

Now the teacher wants to know the score ranking of all the students. Please output each student's score and his team in the order of the last score from high to low.

Input format

In the first line, two integers \ (n \) and \ (k \) represent the number of students and teams respectively.

The following \ (n \) lines, each with an integer \ (s_i \) and an uppercase letter \ (c_i \), represent the theoretical score and team number of the (I \) th player. Ensure that the team number range is one of consecutive \ (k \) letters starting from \ (A \).

Next \ (k \) lines, each line \ (k \) integers. The integer $a in line \ (i \) and column \ (j \)_ {i, j} indicates the score given by team \ (i \) to team \ (j \). When \ (i=j \), it is self-evaluation.

Output format

The output \ (n \) line indicates the answer. The students with high scores will be output first, and the students with the same team number will be output first. For each line, first output the student's grade, and then output the capital English letters representing his team number.

input

6 3
70 A
80 A
65 B
95 B
85 C
90 C
70 90 100
95 88 85
30 47 100

output

93 B
92 C
89 C
76 A
75 B
70 A

Description / tips

\The scores received by group (A \) are \ (70,95,30 \), and the average score is \ (65 \), then \ (95,30 \) is excluded as invalid score, so the item score of group \ (A \) is \ (70 \).
\The scores received by group (b) are \ (90,88,47 \) respectively, and the average score is \ (75 \), then \ (47 \) is eliminated as invalid score, so the item score of group \ (B \) is \ (89 \).
\The scores received by the (C \) group are \ (100,85100 \) respectively, with an average score of \ (95 \), and no score is eliminated. Therefore, the item score of the \ (C \) group is \ (95 \).

Problem solving ideas

simulation

Simulation questions, pay attention to rounding~

• Time complexity: \ (O(nlogn+k^2) \)

code

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n,k,score[30][30],final_score[30],sum[30];
pair<int,int> res[1005],can[1005];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        int s;
        char c;
        scanf("%d %c",&s,&c);
        can[i]={s,c-'A'+1};
    }
    for(int j=1;j<=k;j++)
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&score[i][j]);
            sum[i]+=score[i][j];
            final_score[i]=sum[i];
        }
    for(int i=1;i<=k;i++)
    {
        int cnt=k;
        for(int j=1;j<=k;j++)
            if(abs(sum[i]-k*score[i][j])>k*15)final_score[i]-=score[i][j],cnt--;
        final_score[i]=int(1.*final_score[i]/cnt+0.5);
    }
    for(int i=1;i<=n;i++)
        res[i]={int(0.6*can[i].fi+0.4*final_score[can[i].se]+0.5),can[i].se};
    sort(res+1,res+1+n,[](auto &a,auto &b){if(a.fi!=b.fi)return a.fi>b.fi;return a.se<b.se;});
    for(int i=1;i<=n;i++)
        printf("%d %c\n",res[i].fi,res[i].se-1+'A');
    return 0;
}