PAT – 第39页 – 柳婼の blog

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;

}

1042. Shuffling Machine (20)-PAT甲级真题

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.

The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:

S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2

where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:
2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47
Sample Output:
S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

分析：简单模拟。使用start和end数组保存每一次变换的开始顺序和结束顺序（以1~54的编号存储），最后根据编号与扑克牌字母数字的对应关系输出end数组

#include <cstdio>
using namespace std;
int main() {
    int cnt;
    scanf("%d", &cnt);
    int start[55], end[55], scan[55];
    for(int i = 1; i < 55; i++) {
        scanf("%d", &scan[i]);
        end[i] = i;
    }
    for(int i = 0; i < cnt; i++) {
        for(int j = 1; j < 55; j++)
            start[j] = end[j];
        for(int k = 1; k < 55; k++)
            end[scan[k]] = start[k];
    }
    char c[6] = {"SHCDJ"};
    for(int i = 1; i < 55; i++) {
        end[i] = end[i] - 1;
        printf("%c%d", c[end[i]/13], end[i]%13+1);
        if(i != 54) printf(" ");
    }
    return 0;
}

#include <cstdio>

using namespace std;

int main() {

int cnt;

scanf("%d", &cnt);

int start[55], end[55], scan[55];

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

scanf("%d", &scan[i]);

end[i] = i;

}

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

for(int j = 1; j < 55; j++)

start[j] = end[j];

for(int k = 1; k < 55; k++)

end[scan[k]] = start[k];

}

char c[6] = {"SHCDJ"};

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

end[i] = end[i] - 1;

printf("%c%d", c[end[i]/13], end[i]%13+1);

if(i != 54) printf(" ");

}

return 0;

}

1006. Sign In and Sign Out (25)-PAT甲级真题

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

ID_number Sign_in_time Sign_out_time

where times are given in the format HH:MM:SS, and ID number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.

Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

CS301111 15:30:28 17:00:10

SC3021234 08:00:00 11:25:25

CS301133 21:45:00 21:58:40

Sample Output:

SC3021234 CS301133

题目大意：给出n个人的id、sign in时间、sign out时间，求最早进来的人和最早出去的人的ID～

分析：将时间都转换为总秒数，最早和最迟的时间保存在变量minn和maxn中，并同时保存当前最早和最迟的人的ID，最后输出～

#include <iostream>
#include <climits>
using namespace std;
int main() {
    int n, minn = INT_MAX, maxn = INT_MIN;
    scanf("%d", &n);
    string unlocked, locked;
    for(int i = 0; i < n; i++) {
        string t;
        cin >> t;
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int tempIn = h1 * 3600 + m1 * 60 + s1;
        int tempOut = h2 * 3600 + m2 * 60 + s2;
        if (tempIn < minn) {
            minn = tempIn;
            unlocked = t;
        }
        if (tempOut > maxn) {
            maxn = tempOut;
            locked = t;
        }
    }
    cout << unlocked << " " << locked;
    return 0;
}

#include <iostream>

#include <climits>

using namespace std;

int main() {

int n, minn = INT_MAX, maxn = INT_MIN;

scanf("%d", &n);

string unlocked, locked;

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

string t;

cin >> t;

int h1, m1, s1, h2, m2, s2;

scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);

int tempIn = h1 * 3600 + m1 * 60 + s1;

int tempOut = h2 * 3600 + m2 * 60 + s2;

if (tempIn < minn) {

minn = tempIn;

unlocked = t;

}

if (tempOut > maxn) {

maxn = tempOut;

locked = t;

}

cout << unlocked << " " << locked;

return 0;

}

L2-014. 列车调度-PAT团体程序设计天梯赛GPLT

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？
输入格式：
输入第一行给出一个整数N (2 <= N <= 105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例：
9
8 4 2 5 3 9 1 6 7
输出样例：
4

分析：必须要车号大的先出，小的后出。所以列车排队的每一队必须是从大到小排列（从右往左看），才能保证开出去的车也是从大到小的。对于每一个想要进入并列铁轨的车，如果车号大于每一队的队尾的车号，说明不能进入已经有的队伍，必须进入新的铁轨，否则，选择一个最接近它车号的尾部车号的队伍进入。其实无需保存每一个并行队列的所有值，只需要保存当前队伍的车尾（就是每一列最左边即每一列的最小值）即可，因为每一次都是需要排序比较大小的，所以用set自动排序，首先把set里面放入一个0值。每一次set的最后一个值s.rbegin()都是当前所有队列队尾的最大值。如果当前想要进入排队队伍的t值比集合里面最大值小，就移除第一个比他大的值，然后把t插入集合中。表示的是将t值插入了最接近它车号的队伍的队尾，否则就直接插入进去t值。作为新的队伍。s.upper_bound(t)返回的是第一个大于t的迭代器的位置，在前面加星号表示取这个位置的值，所以s.erase(*(s.upper_bound(t)));表示删除当前这个刚好大于t的位置处的值。因为一开始插入了一个没有的0，所以最后输出是s.size()-1;

#include <iostream>
#include <set>
using namespace std;
int main() {
    int n, t;
    cin >> n;
    set<int> s;
    s.insert(0);
    for(int i = 0; i < n; i++) {
        cin >> t;
        if(t < *s.rbegin()) {
            s.erase(*(s.upper_bound(t)));
        }
        s.insert(t);
    }
    cout << s.size() - 1;
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int main() {

int n, t;

cin >> n;

set<int> s;

s.insert(0);

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

cin >> t;

if(t < *s.rbegin()) {

s.erase(*(s.upper_bound(t)));

}

s.insert(t);

}

cout << s.size() - 1;

return 0;

}

L2-015. 互评成绩-PAT团体程序设计天梯赛GPLT

学生互评作业的简单规则是这样定的：每个人的作业会被k个同学评审，得到k个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。
输入格式：
输入第一行给出3个正整数N（3< N <= 104，学生总数）、k（3<= k <= 10，每份作业的评审数）、M（<= 20，需要输出的学生数）。随后N行，每行给出一份作业得到的k个评审成绩（在区间[0, 100]内），其间以空格分隔。
输出格式：
按非递减顺序输出最后得分最高的M个成绩，保留小数点后3位。分数间有1个空格，行首尾不得有多余空格。
输入样例：
6 5 3
88 90 85 99 60
67 60 80 76 70
90 93 96 99 99
78 65 77 70 72
88 88 88 88 88
55 55 55 55 55
输出样例：
87.667 88.000 96.000

分析：total数组保存各个同学的平均分，v数组保存每次接收得到的分数，排序后取前m名，按递增输出

kuuo同学说不用排序，标记最大和最小值，用总和减去最大最小值即可，于是我偷偷的改了代码。。。。嘘｡◕‿◕｡～～

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int cmp1(double a, double b) {return a > b;}
int main() {
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);
    vector<double> total;
    for(int i = 0; i < n; i++) {
        vector<double> v(k);
        double maxn = -1, minn = 101, average = 0.0;
        for(int j = 0; j < k; j++) {
            scanf("%lf", &v[j]);
            maxn = max(maxn, v[j]);
            minn = min(minn, v[j]);
            average += v[j];
        }
        average = (average - maxn - minn) / (k - 2);
        total.push_back(average);
    }
    sort(total.begin(), total.end(), cmp1);
    if(m != 0)
        printf("%.3f", total[m - 1]);
    for(int i = m - 2; i >= 0; i--)
        printf(" %.3f", total[i]);
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int cmp1(double a, double b) {return a > b;}

int main() {

int n, k, m;

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

vector<double> total;

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

vector<double> v(k);

double maxn = -1, minn = 101, average = 0.0;

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

scanf("%lf", &v[j]);

maxn = max(maxn, v[j]);

minn = min(minn, v[j]);

average += v[j];

}

average = (average - maxn - minn) / (k - 2);

total.push_back(average);

}

sort(total.begin(), total.end(), cmp1);

if(m != 0)

printf("%.3f", total[m - 1]);

for(int i = m - 2; i >= 0; i--)

printf(" %.3f", total[i]);

return 0;

}