liuchuo – 第213页

1036. Boys vs Girls (25)-PAT甲级真题

This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N lines of student information. Each line contains a student’s name, gender, ID and grade, separated by a space, where name and ID are strings of no more than 10 characters with no space, gender is either F (female) or M (male), and grade is an integer between 0 and 100. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case, output in 3 lines. The first line gives the name and ID of the female student with the highest grade, and the second line gives that of the male student with the lowest grade. The third line gives the difference gradeF-gradeM. If one such kind of student is missing, output “Absent” in the corresponding line, and output “NA” in the third line instead.

Sample Input 1:
3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95
Sample Output 1:
Mary EE990830
Joe Math990112
6
Sample Input 2:
1
Jean M AA980920 60
Sample Output 2:
Absent
Jean AA980920
NA

题目大意：给出N个同学的信息，输出女生中的最高分获得者的信息与男生中最低分获得者的信息，并输出他们的分数差。如果不存在女生或者男生，则对应获得者信息处输出Absent，而且差值处输出NA～

分析：用string类型的female和male保存要求的学生的信息，femalescore和malescore处保存男生的最低分和女生的最高分～

一开始设femalescore为最低值-1，malescore为最高值101，最后根据分值是否为-1或者101来判断是否有相应的女生或者男生～

#include <iostream>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    string female, male;
    int femalescore = -1, malescore = 101;
    for(int i = 0; i < n; i++) {
        string name, sex, num;
        int score;
        cin >> name >> sex >> num;
        scanf("%d", &score);
        if(sex == "F") {
            if(femalescore < score) {
                femalescore = score;
                female = name + " " + num;
            }
        } else if(malescore > score) {
                malescore = score;
                male = name + " " + num;
            }
    }
    if(femalescore != -1)
        cout << female << endl;
    else
        printf("Absent\n");
    if(malescore != 101)
        cout << male << endl;
    else
        printf("Absent\n");
    if(femalescore != -1 && malescore != 101)
        printf("%d", femalescore - malescore);
    else
        printf("NA");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

scanf("%d", &n);

string female, male;

int femalescore = -1, malescore = 101;

for(int i = 0; i < n; i++) {

string name, sex, num;

int score;

cin >> name >> sex >> num;

scanf("%d", &score);

if(sex == "F") {

if(femalescore < score) {

femalescore = score;

female = name + " " + num;

}

} else if(malescore > score) {

malescore = score;

male = name + " " + num;

}

if(femalescore != -1)

cout << female << endl;

else

printf("Absent\n");

if(malescore != 101)

cout << male << endl;

else

printf("Absent\n");

if(femalescore != -1 && malescore != 101)

printf("%d", femalescore - malescore);

else

printf("NA");

return 0;

}

1054. The Dominant Color (20)-PAT甲级真题

Behind the scenes in the computer’s memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800×600), you are supposed to point out the strictly dominant color.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (<=800) and N (<=600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0, 224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print the dominant color in a line.

Sample Input:
5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24
Sample Output:
24

题目大意：选取主色调，就是M列N行的矩阵里面出现次数多余一半的那个数字～

分析：STL中map的应用～使用arr[i] = j表示i元素在矩阵中出现了j次，在输入的同时比较arr当前的值是否已经超过半数，如果超过，就直接输出该数字并退出程序～

#include <iostream>
#include <map>
using namespace std;
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    map<int, int> arr;
    int half = m * n / 2;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int temp;
            scanf("%d", &temp);
            arr[temp]++;
            if(arr[temp] > half) {
                printf("%d", temp);
                return 0;
            }
        }
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int m, n;

scanf("%d %d", &m, &n);

map<int, int> arr;

int half = m * n / 2;

for(int i = 0; i < n; i++) {

for(int j = 0; j < m; j++) {

int temp;

scanf("%d", &temp);

arr[temp]++;

if(arr[temp] > half) {

printf("%d", temp);

return 0;

}

return 0;

}

1011. World Cup Betting (20)-PAT甲级真题

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.

Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results — namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.

For example, 3 games’ odds are given as the following:

W T L
1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1
To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.1*3.0*2.5*65%-1)*2 = 37.98 yuans (accurate up to 2 decimal places).

Input

Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.

Output

For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.

Sample Input
1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1
Sample Output
T T W 37.98

题目大意：给出三场比赛以及每场比赛的W、T、L的赔率，选取每一场比赛中赔率最大的三个数a b c，先输出三行各自选择的是W、T、L中的哪一个，然后根据计算公式 (a * b * c * 0.65 – 1) * 2 得出最大收益～

分析：以三个数一组的形式读取，读取完一组后输出最大值代表的字母，然后同时ans累乘该最大值，最后根据公式输出结果～

#include <cstdio>
using namespace std;
int main() {
    char c[4] = {"WTL"};
    double ans = 1.0;
    for(int i = 0; i < 3; i++) {
        double maxvalue = 0.0;
        int maxchar = 0;
        for(int j = 0; j < 3; j++) {
            double temp;
            scanf("%lf", &temp);
            if(maxvalue <= temp) {
                maxvalue = temp;
                maxchar = j;
            }
        }
        ans *= maxvalue;
        printf("%c ", c[maxchar]);
    }
    printf("%.2f", (ans * 0.65 - 1) * 2);
    return 0;
}

#include <cstdio>

using namespace std;

int main() {

char c[4] = {"WTL"};

double ans = 1.0;

for(int i = 0; i < 3; i++) {

double maxvalue = 0.0;

int maxchar = 0;

for(int j = 0; j < 3; j++) {

double temp;

scanf("%lf", &temp);

if(maxvalue <= temp) {

maxvalue = temp;

maxchar = j;

}

ans *= maxvalue;

printf("%c ", c[maxchar]);

}

printf("%.2f", (ans * 0.65 - 1) * 2);

return 0;

}

1009. Product of Polynomials (25)-PAT甲级真题

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 3 3.6 2 6.0 1 1.6

题目大意：给出两个多项式A和B，求A*B的结果～

分析：简单模拟～double类型的arr数组保存第一组数据，ans数组保存结果。当输入第二组数据的时候，一边进行运算一边保存结果。最后按照指数递减的顺序输出所有不为0的项～
注意：因为相乘后指数可能最大为2000，所以ans数组最大要开到2001

#include <iostream>
using namespace std;
int main() {
    int n1, n2, a, cnt = 0;
    scanf("%d", &n1);
    double b, arr[1001] = {0.0}, ans[2001] = {0.0};
    for(int i = 0; i < n1; i++) {
        scanf("%d %lf", &a, &b);
        arr[a] = b;
    }
    scanf("%d", &n2);
    for(int i = 0; i < n2; i++) {
        scanf("%d %lf", &a, &b);
        for(int j = 0; j < 1001; j++)
                ans[j + a] += arr[j] * b;
    }
    for(int i = 2000; i >= 0; i--)
        if(ans[i] != 0.0) cnt++;
    printf("%d", cnt);
    for(int i = 2000; i >= 0; i--)
        if(ans[i] != 0.0)
            printf(" %d %.1f", i, ans[i]);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n1, n2, a, cnt = 0;

scanf("%d", &n1);

double b, arr[1001] = {0.0}, ans[2001] = {0.0};

for(int i = 0; i < n1; i++) {

scanf("%d %lf", &a, &b);

arr[a] = b;

}

scanf("%d", &n2);

for(int i = 0; i < n2; i++) {

scanf("%d %lf", &a, &b);

for(int j = 0; j < 1001; j++)

ans[j + a] += arr[j] * b;

}

for(int i = 2000; i >= 0; i--)

if(ans[i] != 0.0) cnt++;

printf("%d", cnt);

for(int i = 2000; i >= 0; i--)

if(ans[i] != 0.0)

printf(" %d %.1f", i, ans[i]);

return 0;

}

1065. A+B and C (64bit) (20)-PAT甲级真题

Given three integers A, B and C in [-263, 263], you are supposed to tell whether A+B > C.

Input Specification:

The first line of the input gives the positive number of test cases, T (<=10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line “Case #X: true” if A+B>C, or “Case #X: false” otherwise, where X is the case number (starting from 1).”
Sample Input:
3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0
Sample Output:
Case #1: false
Case #2: true
Case #3: false
分析：
因为A、B的大小为[-2^63, 2^63]，用long long 存储A和B的值，以及他们相加的值sum：
如果A > 0, B < 0 或者 A < 0, B > 0，sum是不可能溢出的
如果A > 0, B > 0，sum可能会溢出，sum范围理应为(0, 2^64 – 2]，溢出得到的结果应该是[-2^63, -2]是个负数，所以sum < 0时候说明溢出了
如果A < 0, B < 0，sum可能会溢出，同理，sum溢出后结果是大于0的，所以sum > 0 说明溢出了

#include <cstdio>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        long long sum = a + b;
        if(a > 0 && b > 0 && sum < 0) {
            printf("Case #%d: true\n", i + 1);
        } else if(a < 0 && b < 0 && sum >= 0){
            printf("Case #%d: false\n", i + 1);
        } else if(sum > c) {
            printf("Case #%d: true\n", i + 1);
        } else {
            printf("Case #%d: false\n", i + 1);
        }
    }
    return 0;
}

#include <cstdio>

using namespace std;

int main() {

int n;

scanf("%d", &n);

for(int i = 0; i < n; i++) {

long long a, b, c;

scanf("%lld %lld %lld", &a, &b, &c);

long long sum = a + b;

if(a > 0 && b > 0 && sum < 0) {

printf("Case #%d: true\n", i + 1);

} else if(a < 0 && b < 0 && sum >= 0){

printf("Case #%d: false\n", i + 1);

} else if(sum > c) {

printf("Case #%d: true\n", i + 1);

} else {

printf("Case #%d: false\n", i + 1);

}

return 0;

}

1046. Shortest Distance (20)-PAT甲级真题

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output:
3
10
7

分析：简单模拟。所有结点连起来会形成一个环形，dis[i]存储第1个结点到第i个结点的下一个结点的距离，sum保存整个路径一圈的总和值。求得结果就是dis[right – 1] – dis[left – 1]和 sum – dis[right – 1] – dis[left – 1]中较小的那一个～～
注意：可能left和right的顺序颠倒了，这时候要把left和right的值交换～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> dis(n + 1);
    int sum = 0, left, right, cnt;
    for(int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        sum += temp;
        dis[i] = sum;
    }
    scanf("%d", &cnt);
    for(int i = 0; i < cnt; i++) {
        scanf("%d %d", &left, &right);
        if(left > right)
            swap(left, right);
        int temp = dis[right - 1] - dis[left - 1];
        printf("%d\n", min(temp, sum - temp));
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

scanf("%d", &n);

vector<int> dis(n + 1);

int sum = 0, left, right, cnt;

for(int i = 1; i <= n; i++) {

int temp;

scanf("%d", &temp);

sum += temp;

dis[i] = sum;

}

scanf("%d", &cnt);

for(int i = 0; i < cnt; i++) {

scanf("%d %d", &left, &right);

if(left > right)

swap(left, right);

int temp = dis[right - 1] - dis[left - 1];

printf("%d\n", min(temp, sum - temp));

}

return 0;

}