PAT – 第43页 – 柳婼の blog

1089. Insert or Merge (25)-PAT甲级真题

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

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

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

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

Sample Output 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6

题目大意：现给定原始序列和由某排序算法产生的中间序列，请你判断该算法是插入算法还是归并算法。首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列

分析：先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标，再将j指向从i+1开始，第一个不满足a[j] == b[j]的下标，如果j顺利到达了下标n，说明是插入排序，再下一次的序列是sort(a, a+i+2);否则说明是归并排序。归并排序就别考虑中间序列了，直接对原来的序列进行模拟归并时候的归并过程，i从0到n/k，每次一段段得sort(a + i * k, a + (i + 1) * k);最后别忘记还有最后剩余部分的sort(a + n / k * k, a + n);这样是一次归并的过程。直到有一次发现a的顺序和b的顺序相同，则再归并一次，然后退出循环～

注意：一开始第三个测试点一直不过，天真的我以为可以模拟一遍归并的过程然后在过程中判断下一步是什么。。然而真正的归并算法它是一个递归过程。。也就是先排左边一半，把左边的完全排列成正确的顺序之后，再排右边一半的。。而不是左右两边一起排列的。。后来改了自己的归并部分判断的代码就过了。。。｡◕‿◕｡

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, a[100], b[100], i, j;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);
    for (j = i + 1; a[j] == b[j] && j < n; j++);
    if (j == n) {
        cout << "Insertion Sort" << endl;
        sort(a, a + i + 2);
    } else {
        cout << "Merge Sort" << endl;
        int k = 1, flag = 1;
        while(flag) {
            flag = 0;
            for (i = 0; i < n; i++) {
                if (a[i] != b[i])
                    flag = 1;
            }
            k = k * 2;
            for (i = 0; i < n / k; i++)
                sort(a + i * k, a + (i + 1) * k);
            sort(a + n / k * k, a + n);
        }
    }
    for (j = 0; j < n; j++) {
        if (j != 0) printf(" ");
        printf("%d", a[j]);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, a[100], b[100], i, j;

cin >> n;

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

cin >> a[i];

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

cin >> b[i];

for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);

for (j = i + 1; a[j] == b[j] && j < n; j++);

if (j == n) {

cout << "Insertion Sort" << endl;

sort(a, a + i + 2);

} else {

cout << "Merge Sort" << endl;

int k = 1, flag = 1;

while(flag) {

flag = 0;

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

if (a[i] != b[i])

flag = 1;

}

k = k * 2;

for (i = 0; i < n / k; i++)

sort(a + i * k, a + (i + 1) * k);

sort(a + n / k * k, a + n);

}

for (j = 0; j < n; j++) {

if (j != 0) printf(" ");

printf("%d", a[j]);

}

return 0;

}

1092. To Buy or Not to Buy (20)-PAT甲级真题

Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence Eva must check whether a string in the shop contains all the beads she needs. She now comes to you for help: if the answer is “Yes”, please tell her the number of extra beads she has to buy; or if the answer is “No”, please tell her the number of beads missing from the string.

For the sake of simplicity, let us use the characters in the ranges [0-9], [a-z], and [A-Z] to represent the colors. For example, the 3rd string in Figure 1 is the one that Eva would like to make. Then the 1st string is okay since it contains all the necessary beads with 8 extra ones; yet the 2nd one is not since there is no black bead and one less red bead.
Input Specification:
Each input file contains one test case. Each case gives in two lines the strings of no more than 1000 beads which belong to the shop owner and Eva, respectively.

Output Specification:
For each test case, print your answer in one line. If the answer is “Yes”, then also output the number of extra beads Eva has to buy; or if the answer is “No”, then also output the number of beads missing from the string. There must be exactly 1 space between the answer and the number.

Sample Input 1:
ppRYYGrrYBR2258
YrR8RrY
Sample Output 1:
Yes 8
Sample Input 2:
ppRYYGrrYB225
YrR8RrY
Sample Output 1:
No 2

题目大意：小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串，但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下，某串珠子里是否包含了全部自己想要的珠子？如果是，那么告诉她有多少多余的珠子；如果不是，那么告诉她缺了多少珠子～

分析：字符串a和b分别存储摊主的珠串和小红想做的珠串，遍历字符串a，将每一个字符出现的次数保存在book数组中，表示摊主的每个珠子的个数，遍历字符串b，如果book[b[i]]>0，表示小红要的珠子摊主有，则book[b[i]]-1，将这个珠子给小红～否则说明小红要的珠子摊主没有，则将统计缺了多少珠子的result++，如果result不等于0，说明缺珠子，则不可以买，输出No以及缺了的珠子个数result，否则说明不缺珠子，可以买，输出Yes以及摊主珠子多余的个数a.length() – b.length()～

#include <iostream>
using namespace std;
int book[256];
int main() {
    string a, b;
    cin >> a >> b;
    for (int i = 0; i < a.length(); i++)
        book[a[i]]++;
    int result = 0;
    for (int i = 0; i < b.length(); i++) {
        if (book[b[i]] > 0)
            book[b[i]]--;
        else
            result++;
    }
    if(result != 0)
        printf("No %d", result);
    else
        printf("Yes %d", a.length() - b.length());
    return 0;
}

#include <iostream>

using namespace std;

int book[256];

int main() {

string a, b;

cin >> a >> b;

for (int i = 0; i < a.length(); i++)

book[a[i]]++;

int result = 0;

for (int i = 0; i < b.length(); i++) {

if (book[b[i]] > 0)

book[b[i]]--;

else

result++;

}

if(result != 0)

printf("No %d", result);

else

printf("Yes %d", a.length() - b.length());

return 0;

}

1093. Count PAT’s (25)-PAT甲级真题

The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT’s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT’s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:
APPAPT
Sample Output:
2

分析：要想知道构成多少个PAT，那么遍历字符串后对于每一A，它前面的P的个数和它后面的T的个数的乘积就是能构成的PAT的个数。然后把对于每一个A的结果相加即可～辣么就简单啦，只需要先遍历字符串数一数有多少个T～然后每遇到一个T呢～countt–;每遇到一个P呢，countp++;然后一遇到字母A呢就countt * countp～～把这个结果累加到result中～～最后输出结果就好啦～对了别忘记要对10000000007取余哦～～

【PS：假设神奇的你对每次都遇到的神奇的为什么要对1000000007取模感兴趣，戳那个加下划线的链接即可~~~^_^】

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.length(), result = 0, countp = 0, countt = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'T')
            countt++;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] == 'P') countp++;
        if (s[i] == 'T') countt--;
        if (s[i] == 'A') result = (result + (countp * countt) % 1000000007) % 1000000007;
    }
    cout << result;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

int len = s.length(), result = 0, countp = 0, countt = 0;

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

if (s[i] == 'T')

countt++;

}

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

if (s[i] == 'P') countp++;

if (s[i] == 'T') countt--;

if (s[i] == 'A') result = (result + (countp * countt) % 1000000007) % 1000000007;

}

cout << result;

return 0;

}

1100. Mars Numbers (20)-PAT甲级真题

People on Mars count their numbers with base 13:

Zero on Earth is called “tret” on Mars.
The numbers 1 to 12 on Earch is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.
For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.
For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (< 100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

Output Specification:
For each number, print in a line the corresponding number in the other language.

Sample Input:
4
29
5
elo nov
tam

Sample Output:
hel mar
may
115
13

题目大意：火星人是以13进制计数的：地球人的0被火星人称为tret。地球人数字1到12的火星文分别为：jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。火星人将进位以后的12个高位数字分别称为：tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。例如地球人的数字“29”翻译成火星文就是“hel mar”；而火星文“elo nov”对应地球数字“115”。为了方便交流，请你编写程序实现地球和火星数字之间的互译～

分析：因为给出的可能是数字（地球文）也有可能是字母（火星文），所以用字符串s保存每一次的输入，因为如果是火星文则会出现空格，所以用getline接收一行的输入～计算string s的长度len，判断s[0]是否是数字，如果是数字，表示是地球文，则需要转为火星文，执行func1()；如果不是数字，则说明是火星文，需要转为地球文，执行func2()；

func1(int t)中，传入的值是string转int后的结果stoi(s)，因为数字最大不超过168，所以最多只会输出两位火星文，如果t / 13不等于0，说明有高位，所以输出b[t/13]；如果输出了高位（t/13不等于0）并且t % 13不等于0，说明有高位且有低位，所以此时输出空格；如果t % 13不等于0，说明有低位，此时输出a[t % 13]；注意，还有个数字0没有考虑，因为数字0取余13等于0，但是要特别输出tret，所以在func1的最后一句判断中加一句t == 0，并将a[0]位赋值成tret即可解决0的问题～

func2()中，t1和t2一开始都赋值0，s1和s2用来分离火星文单词，因为火星文字符串只可能一个单词或者两个单词，而且一个单词不会超过4，所以先将一个单词的赋值给s1，即s1 = s.substr(0, 3)；如果len > 4，就将剩下的一个单词赋值给s2，即s2 = s.substr(4, 3)；然后下标j从1到12遍历a和b两个数组，如果a数组中有和s1或者s2相等的，说明低位等于j，则将j赋值给t2；如果b数组中有和s1相等的（b数组不会和s2相等，因为如果有两个单词，s2只可能是低位），说明高位有值，将j赋值给t1，最后输出t1 * 13 + t2即可～

#include <iostream>
#include <string>
using namespace std;
string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string b[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
string s;
int len;
void func1(int t) {
    if (t / 13) cout << b[t / 13];
    if ((t / 13) && (t % 13)) cout << " ";
    if (t % 13 || t == 0) cout << a[t % 13];
}
void func2() {
    int t1 = 0, t2 = 0;
    string s1 = s.substr(0, 3), s2;
    if (len > 4) s2 = s.substr(4, 3);
    for (int j = 1; j <= 12; j++) {
        if (s1 == a[j] || s2 == a[j]) t2 = j;
        if (s1 == b[j]) t1 = j;
    }
    cout << t1 * 13 + t2;
}
int main() {
    int n;
    cin >> n;
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        len = s.length();
        if (s[0] >= '0' && s[0] <= '9')
            func1(stoi(s));
        else
            func2();
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};

string b[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};

string s;

int len;

void func1(int t) {

if (t / 13) cout << b[t / 13];

if ((t / 13) && (t % 13)) cout << " ";

if (t % 13 || t == 0) cout << a[t % 13];

}

void func2() {

int t1 = 0, t2 = 0;

string s1 = s.substr(0, 3), s2;

if (len > 4) s2 = s.substr(4, 3);

for (int j = 1; j <= 12; j++) {

if (s1 == a[j] || s2 == a[j]) t2 = j;

if (s1 == b[j]) t1 = j;

}

cout << t1 * 13 + t2;

}

int main() {

int n;

cin >> n;

getchar();

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

getline(cin, s);

len = s.length();

if (s[0] >= '0' && s[0] <= '9')

func1(stoi(s));

else

func2();

cout << endl;

}

return 0;

}

1002. A+B for Polynomials (25)-PAT甲级真题

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

Input

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

For each test case you should output the sum 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 to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 2 1.5 1 2.9 0 3.2

题目大意：计算多项式A+B的和～

分析：设立c数组，长度为指数的最大值，c[i] = j表示指数i的系数为j，接收a和b输入的同时将对应指数的系数加入到c中，累计c中所有非零系数的个数，然后从后往前输出所有系数不为0的指数和系数～

#include <iostream>
using namespace std;
int main() {
    float c[1001] = {0};
    int m, n, t;
    float num;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%f", &t, &num);
        c[t] += num;
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%f", &t, &num);
        c[t] += num;
    }
    int cnt = 0;
    for (int i = 0; i < 1001; i++) {
        if (c[i] != 0) cnt++;
    }
    printf("%d", cnt);
    for (int i = 1000; i >= 0; i--) {
        if (c[i] != 0.0)
            printf(" %d %.1f", i, c[i]);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

float c[1001] = {0};

int m, n, t;

float num;

scanf("%d", &m);

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

scanf("%d%f", &t, &num);

c[t] += num;

}

scanf("%d", &n);

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

scanf("%d%f", &t, &num);

c[t] += num;

}

int cnt = 0;

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

if (c[i] != 0) cnt++;

}

printf("%d", cnt);

for (int i = 1000; i >= 0; i--) {

if (c[i] != 0.0)

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

}

return 0;

}

1005. Spell It Right (20)-PAT甲级真题

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

Input Specification:

Each input file contains one test case. Each case occupies one line which contains an N (<= 10100).

Output Specification:

For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

Sample Input:

12345

Sample Output:

one five

题目大意：给一个非负正数N，计算N的每一位相加的和，然后输出和的每一位的英文读音～

分析：1、求出每一位相加的和sum 2、将sum转换为string s 3、将string s的每一位输出对应的英文读音～

#include <iostream>
using namespace std;
int main() {
    string a;
    cin >> a;
    int sum = 0;
    for (int i = 0; i < a.length(); i++)
        sum += (a[i] - '0');
    string s = to_string(sum);
    string arr[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    cout << arr[s[0] - '0'];
    for (int i = 1; i < s.length(); i++)
        cout << " " << arr[s[i] - '0'];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string a;

cin >> a;

int sum = 0;

for (int i = 0; i < a.length(); i++)

sum += (a[i] - '0');

string s = to_string(sum);

string arr[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};

cout << arr[s[0] - '0'];

for (int i = 1; i < s.length(); i++)

cout << " " << arr[s[i] - '0'];

return 0;

}