Improving the GPA

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 65    Accepted Submission(s): 43

Xueba: Using the 4-Point Scale, my GPA is 4.0.

In fact, the AVERAGE SCORE of Xueba is calculated by the following formula:
AVERAGE SCORE = ∑(Wi * SCOREi) / ∑(Wi) 1<=i<=N
where SCOREi represents the scores of the ith course and Wi represents the credit of the corresponding course.

To simplify the problem, we assume that the credit of each course is 1. In this way, the AVERAGE SCORE is ∑(SCOREi) / N. In addition, SCOREi are all integers between 60 and 100, and we guarantee that ∑(SCOREi) can be divided by N.

In SYSU, the university usually uses the AVERAGE SCORE as the standard to represent the students’ level. However, when the students want to study further in foreign countries, other universities will use the 4-Point Scale to represent the students’ level. There are 2 ways of transforming each score to 4-Point Scale. Here is one of them.


The student’s average GPA in the 4-Point Scale is calculated as follows:GPA = ∑(GPAi) / N
So given one student’s AVERAGE SCORE and the number of the courses, there are many different possible values in the 4-Point Scale. Please calculate the minimum and maximum value of the GPA in the 4-Point Scale.

475 175 275 375 10

3.0000 3.00002.7500 3.00002.6667 3.16672.4000 3.2000
Hint
In the third case, there are many possible ways to calculate the minimum value of the GPA in the 4-Point Scale.For example, Scores 78 74 73 GPA = (3.0 + 2.5 + 2.5) / 3 = 2.6667Scores 79 78 68 GPA = (3.0 + 3.0 + 2.0) / 3 = 2.6667Scores 84 74 67 GPA = (3.5 + 2.5 + 2.0) / 3 = 2.6667Scores 100 64 61 GPA = (4.0 + 2.0 + 2.0) / 3 = 2.6667
 

给出n科的平均成绩，问最低和最高的平均学分会是多少？

一开始看很麻烦的一个题，因为分数不一定，将成绩分成了五个分数段，每段都可以有ki科，每个分数段的科目加起来是n个，这样遍历出所有的可能，如果每一段都去最高分，得到一个最高可能的平均分，每一段都取最低分，得到最低的平均分，如果给出的平均分在这一段内那么这一种的成绩就可能存在，统计该情况的平均学分，最后得出所有情况的平均学分的最小值和最大值。

时间：n最大是10，所以最多需要确定4个段就可以得到最后一个段的科目数，时间也就是 10^4.

#include <cstring>#include <cstdio>#include <math.h>#include <algorithm>using namespace std;int main(){    int t, n, a, i, tot, j, k, h, i1, j1, k1, h1, i2, j2, k2, h2;    double max1, tmp, min1;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&a,&n);        max1=-1;        min1=1e9;        a*=n;        for(i=0; i<=n; i++)        {            i1=i*100;            i2=i*85;            for(j=0; j<=n-i; j++)            {                j1=j*84;                j2=j*80;                for(k=0; k<=n-i-j; k++)                {                    k1=k*79;                    k2=k*75;                    for(h=0; h<=n-i-j-k; h++)                    {                        h1 = h * 74 ;                        h2 = h * 70 ;                        int z=n-i-j-k-h;                        ////printf("zz --- %d %d %d %d %d\n" , i, j, k, h, z);                        int maxans=i1+j1+k1+h1+z*69;                        int minans=i2+j2+k2+h2+z*60;                        if(a>=minans&&a<=maxans)                        {                             //printf("kkkk --- %d %d %d %d %d\n" , i, j, k, h, z);                            tmp=i*4+j*3.5+k*3.0+h*2.5+z*2;                            if(max1<tmp)                            {                                max1=tmp;                                //printf("max --- %d %d %d %d %d\n" , i, j, k, h, z);                            }                            if(min1>tmp)                            {                                min1=tmp;                                //printf("min --- %d %d %d %d %d\n" , i, j, k, h, z);                            }                        }                    }                }            }        }        printf("%.4lf %.4lf\n",min1/n,max1/n);    }    return 0;}