首页 > 代码库 > HDU 3296 & POJ 3138 Acm Team Section（数学）

HDU 3296 & POJ 3138 Acm Team Section（数学）

2024-07-24 06:37:29   218人阅读

题目链接：

HDU: http://acm.hdu.edu.cn/showproblem.php?pid=3296

POJ:  http://poj.org/problem?id=3138

Acm Team Section

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 159    Accepted Submission(s): 47


Problem Description
The ACM-ICPC brings together the top student programmers from all over the world, and provides them with opportunities to develop critical skills which will give them a competitive edge when they launch careers in information technology areas. More than 5,600 teams from 84 countries had competed in regional contests last year. An ever larger number of teams - more than 7,000 teams from different countries worldwide - have registered in this year‘s regional contests. However, due to the limited capacity of each site, only a small amount of the registered teams can be allowed to participate in the on-site contest. It is really hard for the contest organizers to determine which teams should be allowed to participate. One of the possible solutions is to hold a preliminary internet contest before the on-site competition. The following part describes a simplified version of rules for team selection:

Up to three teams from each school can participate in the on-site contest, depending on how many following conditions the school in question meets:

a)
A team from this school has solved at least M problems in the preliminary contest; 
b)
Some of the teams from this school ranked top 20 in previous World Finals; 
c)
This school has hosted a provincial contest this year. 

Your task is to write a program to help the contest holders to calculate how many teams are allowed to participate in the on-site final contest.
 

Input
There are multiple test cases in the input file. Each test case starts with three integers S , T and M (1<=S<=100, 1<=T<=2000, 0<=M<=10) , representing the number of schools, the number of teams participating in the preliminary contest, and the minimum number of problems which is required to be solved in order to enter the on-site competition, respectively.

Each of the following S lines consists of three integers Id , P and Q , (1<=Id<=S, 0<=P, Q<=1) , representing the Id of the school, whether this school satisfies condition b), and whether this school satisfies condition c).

The last part of each test case consists of T lines. There are two integers on each of the T lines, Sid and Tot (1<=Sid<=S, 0<=Tot<=10) , meaning that a team from school Sid had solved Tot problems in the preliminary contest.

Two consecutive test cases are separated by a blank line. S = 0, T = 0, M = 0 indicates the end of input and should not be processed by your program.
 

Output
For each test case, print the total number of teams which are allowed to participate in the on-site competition on a separate line in the format as indicated in the sample output.
 

Sample Input
5 8 6 
5 0 1 
4 0 0 
1 0 0 
3 1 1 
2 1 1
2 6 
3 3 
2 9 
5 7 
4 8 
3 6 
2 8 
1 6 

5 8 6 
3 0 1 
5 1 1 
2 0 1 
1 1 1 
4 1 0
5 7 
2 5 
4 5 
5 5 
3 3 
5 6 
2 0 
4 7 

0 0 0
 

Sample Output
Case 1: 10
Case 2: 9
 

Source
2006 Asia Regional Shanghai


题意：

ACM比赛由于比赛场地有限制不能容纳太多的队伍，所以现场赛之前会有网络赛，每个学校最多有三个队伍的名额能参加现场赛，且须满足三个条件！（在不超过三支队伍的情况下能满足几个条件就能有几支队伍参加），条件a：某学校的某支队伍解出了M道及其以上的题目；条件b：在WF排名前20的学校；条件c：今年学校举办过省赛；

思路：

很简单，先检查每所学校满足的条件b、c，满足几个条件就有几支队伍，然后再检查每所学校解题最多的队伍的题数是否大于等于M;


代码如下：

//#pragma warning (disable:4786)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-9;
//const double pi = atan(1.0)*4;
const double pi = 3.1415926535897932384626;
#define INF 1e18
//typedef long long LL;
//typedef __int64 LL;
const int maxn = 2017;
int main()
{
    int s[maxn], t[maxn];
    int S, T, M;
    int ID, P, Q;
    int cas = 0;
    while(scanf("%d%d%d",&S,&T,&M))
    {
        if(S==0 && T==0 && M==0)
            break;
        /*if(cas)
            printf("\n");*/
        memset(s,0,sizeof(s));
        memset(t,0,sizeof(t));
        int sum = 0;
        for(int i = 1; i <= S; i++)
        {
            scanf("%d%d%d",&ID,&P,&Q);
            sum+=P+Q;
        }
        int Sid, Tot;
        for(int i = 1; i <= T; i++)
        {
            scanf("%d%d",&Sid,&Tot);
            if(Tot >= M && t[Sid] == 0)
            {
                sum++;
                t[Sid] = 1;
            }
        }
        printf("Case %d: %d\n",++cas,sum);
    }
    return 0;
}


HDU 3296 & POJ 3138 Acm Team Section（数学）


联系
我们