The PAT admission ticket number consists of 4 parts:
- The first digit is the level, that is, T represents the top level; A represents the A level; B represents the B level;
- The 2nd to 4th digits are the examination room number, ranging from 101 to 999;
- The 5th to 10th digits are the test date, in the format of year, month, and day, each occupying 2 digits;
- The last 11-13 digits are the candidate number, ranging from 000 to 999.
Given a series of candidates' admission ticket numbers and their scores, please output various statistical information as required.
Input format:
The input first gives two positive integers N (≤104) and M (≤100) in one line, which are the number of candidates and the number of statistical requirements, respectively.
Next N lines, each giving a candidate's admission ticket number and its score (integer in the interval [0,100]), separated by spaces.
After the candidate information, give M lines, each line gives a statistical requirement, the format is: type instruction, where
- Type 1 indicates that the scores of candidates of a specified level are required to be output in non-ascending order of scores, and the corresponding instruction gives the letters representing the specified level;
- Type 2 means that the number of candidates and the total score of a designated examination room are required to be output, and the corresponding instruction is to give the number of the designated examination room;
- Type 3 means that the number of candidates on a specified date is required to be output by the examination room, and the corresponding instruction gives the specified date in the same format as the date on the admission ticket.
Output format:
For each statistical requirement, first output the Case #: requirement on one line, where # is the requirement number, starting with 1; the requirement is to copy the requirement given by the input. Then output the corresponding statistical results:
- For an instruction of type 1, the output format is the same as the input test taker information format, that is, the result of the admission ticket number. For candidates with tied scores, they will be output according to the lexicographical order of their admission ticket numbers (the questions are guaranteed to have no duplicate admission ticket numbers);
- Commands of type 2 are output in the format of the total score of the number of people;
- For commands of type 3, the output is in non-increasing order of the number of people, and the format is the total number of people in the examination room number. If the number of people is tied, it will be output in the ascending order of the examination room number.
If the query result is empty, NA is output.
Input sample:
8 4 B123180908127 99 B102180908003 86 A112180318002 98 T107150310127 62 A107180908108 100 T123180908010 78 B112160918035 88 A107180908021 98 1 A 2 107 3 180908 2 999
Sample output:
Case 1: 1 A A107180908108 100 A107180908021 98 A112180318002 98 Case 2: 2 107 3 260 Case 3: 3 180908 107 2 123 2 102 1 Case 4: 2 999 NA
Problem solving ideas:
It's a very complicated question. You need to read the data first, and then extract all kinds of information. Then deal with the situation according to the requirements. My approach is to sort according to the requirements of type 1. The other two cases can be sorted without sorting, and the overall control of the program within O(N^2) should be able to pass smoothly. Note that in each case, when there is no query result, NA should be output, and the character width should be preserved when outputting the data of the number class.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 14
#define MAXROOMS 1000
typedef struct _node *PtrN;
typedef struct _node {
char str[MAXN];
char lv;
int exam_no, exam_date, can_id, score;
} Candidate;
typedef struct _node2 *PtrP;
typedef struct _node2 {
int exam_no, candidates;
} Pair;
int compare1(const void *a, const void *b) {
PtrN pa = (PtrN)a, pb = (PtrN)b;
if ( pa->lv != pb->lv )
return (int)(pa->lv - pb->lv);
else if ( pa->score != pb->score )
return pb->score - pa->score;
else
return strcmp(pa->str, pb->str);
}
int compare2(const void *a, const void *b) {
PtrP pa = (PtrP)a, pb = (PtrP)b;
return pb->candidates - pa->candidates;
}
int main(int argc, const char *argv[]) {
int N, M, i, j, type;
char temp[MAXN], strcode[MAXN];
if ( scanf("%d %d", &N, &M)==EOF ) printf("error\n");
Candidate students[N];
for ( i=0; i<N; ++i ) {
if ( scanf("%s %d", students[i].str, &students[i].score)==EOF ) printf("error\n");
students[i].lv = students[i].str[0];
memcpy(temp, &students[i].str[1], 3);
temp[3] = '\0';
students[i].exam_no = atoi(temp);
memcpy(temp, &students[i].str[10], 3);
temp[3] = '\0';
students[i].can_id = atoi(temp);
memcpy(temp, &students[i].str[4], 6);
temp[6] = '\0';
students[i].exam_date = atoi(temp);
}
qsort(students, N, sizeof(Candidate), compare1);
for ( i=1; i<=M; ++i ) {
if ( scanf("%d %s", &type, strcode)==EOF ) printf("error\n");
printf("Case %d: %d %s\n", i, type, strcode);
int flag = 1, count = 0, sum = 0, code = atoi(strcode);
char level = strcode[0];
Pair stu_in_room[MAXROOMS] = {{0,0},};
switch ( type ) {
case 1:
for ( j=0; j<N; ++j ) {
if ( students[j].lv == level ) {
printf("%s %d\n", students[j].str, students[j].score);
flag = 0;
}
}
if ( flag ) printf("NA\n");
break;
case 2:
for ( j=0; j<N; ++j ) {
if ( students[j].exam_no == code ) {
sum += students[j].score;
++count;
flag = 0;
}
}
if ( flag )
printf("NA\n");
else
printf("%d %d\n", count, sum);
break;
case 3:
for ( j=0; j<N; ++j ) {
if ( students[j].exam_date == code ) {
stu_in_room[students[j].exam_no].exam_no = students[j].exam_no;
++stu_in_room[students[j].exam_no].candidates;
flag = 0;
}
}
if ( flag ) {
printf("NA\n");
} else {
qsort(stu_in_room, MAXROOMS, sizeof(Pair), compare2);
for ( j=0; j<MAXROOMS; ++j ) {
if ( stu_in_room[j].candidates == 0 ) break;
printf("%03d %d\n", stu_in_room[j].exam_no, stu_in_room[j].candidates);
}
}
break;
default:
printf("NA\n");
}
}
return EXIT_SUCCESS;
}