PAT – 第16页

1062. 最简分数(20)-PAT乙级真题

一个分数一般写成两个整数相除的形式：N/M，其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为K的最简分数。

输入格式：

输入在一行中按N/M的格式给出两个正分数，随后是一个正整数分母K，其间以空格分隔。题目保证给出的所有整数都不超过1000。

输出格式：

在一行中按N/M的格式列出两个给定分数之间分母为K的所有最简分数，按从小到大的顺序，其间以1个空格分隔。行首尾不得有多余空格。题目保证至少有1个输出。

输入样例：
7/18 13/20 12
输出样例：
5/12 7/12

分析：使用辗转相除法gcd计算a和b的最大公约数，因为要列出n1/m1和n2/m2之间的最简分数，但是n1/m1不一定小于n2/m2，所以如果n1 * m2 > n2 * m1，说明n1/m1比n2/m2大，则调换n1和n2、m1和m2的位置～假设所求的分数分母为k、分子num，先令num=1，当n1 * k >= m1 * num时，num不断++，直到num符合n1/m1 < num/k为止～然后在n1/m1和n2/m2之间找符合条件的num的值，用gcd(num, k)是否等于1判断num和k是否有最大公约数，如果等于1表示没有最大公约数，就输出num/k，然后num不断++直到退出循环～

#include <iostream>
using namespace std;
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    int n1, m1, n2, m2, k;
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    if(n1 * m2 > n2 * m1) {
        swap(n1, n2);
        swap(m1, m2);
    }
    int num = 1;
    bool flag = false;
    while(n1 * k >= m1 * num) num++;
    while(n1 * k < m1 * num && m2 * num < n2 * k) {
        if(gcd(num, k) == 1) {
            printf("%s%d/%d", flag == true ? " " : "", num, k);
            flag = true;
        }
        num++;
    }
    return 0;
}

#include <iostream>

using namespace std;

int gcd(int a, int b){

return b == 0 ? a : gcd(b, a % b);

}

int main() {

int n1, m1, n2, m2, k;

scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);

if(n1 * m2 > n2 * m1) {

swap(n1, n2);

swap(m1, m2);

}

int num = 1;

bool flag = false;

while(n1 * k >= m1 * num) num++;

while(n1 * k < m1 * num && m2 * num < n2 * k) {

if(gcd(num, k) == 1) {

printf("%s%d/%d", flag == true ? " " : "", num, k);

flag = true;

}

num++;

}

return 0;

}

1061. 判断题(15)-PAT乙级真题

判断题的评判很简单，本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

输入格式：

输入在第一行给出两个不超过100的正整数N和M，分别是学生人数和判断题数量。第二行给出M个不超过5的正整数，是每道题的满分值。第三行给出每道题对应的正确答案，0代表“非”，1代表“是”。随后N行，每行给出一个学生的解答。数字间均以空格分隔。

输出格式：

按照输入的顺序输出每个学生的得分，每个分数占一行。

输入样例：
3 6
2 1 3 3 4 5
0 0 1 0 1 1
0 1 1 0 0 1
1 0 1 0 1 0
1 1 0 0 1 1
输出样例：
13
11
12

分析：score数组表示每道题的分值，ans数组表示每道题的答案，对于每一个学生，如果他给出的答案temp等于正确答案ans[j]，则将这道题的分数score[j]累加到total中，最后输出total的值～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, temp;
    scanf("%d%d", &n, &m);
    vector<int> score(m), ans(m);
    for(int i = 0; i < m; i++)
        scanf("%d", &score[i]);
    for(int i = 0; i < m; i++)
        scanf("%d", &ans[i]);
    for(int i = 0; i < n; i++) {
        int total = 0;
        for(int j = 0; j < m; j++) {
            scanf("%d", &temp);
            if(temp == ans[j])
                total += score[j];
        }
        printf("%d\n", total);
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, temp;

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

vector<int> score(m), ans(m);

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

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

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

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

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

int total = 0;

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

scanf("%d", &temp);

if(temp == ans[j])

total += score[j];

}

printf("%d\n", total);

}

return 0;

}

1065. 单身狗(25)-PAT乙级真题

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：

输入第一行给出一个正整数N（<=50000），是已知夫妻/伴侣的对数；随后N行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个ID号，为5位数字（从00000到99999），ID间以空格分隔；之后给出一个正整数M（<=10000），为参加派对的总人数；随后一行给出这M位客人的ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式：

首先第一行输出落单客人的总人数；随后第二行按ID递增顺序列出落单的客人。ID间用1个空格分隔，行的首尾不得有多余空格。

输入样例：

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例：

5
10000 23333 44444 55555 88888

分析：设立数组couple[i] = j表示i的对象是j～一开始先设置为都是-1，设立数组isExist表示某人的对象是否来到了派对上～接收数据的时候，对于每一对a和b，将couple的a设置为b，b设置为a，表示他俩是一对～对于每一个需要判断的人，将其存储在guest数组里面，如果它不是单身的（也就是如果它的couple[guest[i]] != -1）那么就将它对象的isExist设置为1，表示他对象的对象（也就是他自己）来到了派对～这样所有isExist不为1的人，对象是没有来到派对的～把所有的人遍历后插入一个集合set里面，set的size就是所求的人数，set里面的所有数就是所求的人的递增排列～

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
    int n, a, b, m;
    scanf("%d", &n);
    vector<int> couple(100000, -1);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a, &b);
        couple[a] = b;
        couple[b] = a;
    }
    scanf("%d", &m);
    vector<int> guest(m), isExist(100000);
    for (int i = 0; i < m; i++) {
        scanf("%d", &guest[i]);
        if (couple[guest[i]] != -1)
            isExist[couple[guest[i]]] = 1;
    }
    set<int> s;
    for (int i = 0; i < m; i++) {
        if (!isExist[guest[i]])
            s.insert(guest[i]);
    }
    printf("%d\n", s.size());
    for (auto it = s.begin(); it != s.end(); it++) {
        if (it != s.begin()) printf(" ");
        printf("%05d", *it);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

int main() {

int n, a, b, m;

scanf("%d", &n);

vector<int> couple(100000, -1);

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

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

couple[a] = b;

couple[b] = a;

}

scanf("%d", &m);

vector<int> guest(m), isExist(100000);

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

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

if (couple[guest[i]] != -1)

isExist[couple[guest[i]]] = 1;

}

set<int> s;

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

if (!isExist[guest[i]])

s.insert(guest[i]);

}

printf("%d\n", s.size());

for (auto it = s.begin(); it != s.end(); it++) {

if (it != s.begin()) printf(" ");

printf("%05d", *it);

}

return 0;

}

1064. 朋友数(20)

如果两个整数各位数字的和是一样的，则被称为是“朋友数”，而那个公共的和就是它们的“朋友证号”。例如123和51就是朋友数，因为1+2+3 = 5+1 = 6，而6就是它们的朋友证号。给定一些整数，要求你统计一下它们中有多少个不同的朋友证号。注意：我们默认一个整数自己是自己的朋友。

输入格式：

输入第一行给出正整数N。随后一行给出N个正整数，数字间以空格分隔。题目保证所有数字小于10⁴。

输出格式：

首先第一行输出给定数字中不同的朋友证号的个数；随后一行按递增顺序输出这些朋友证号，数字间隔一个空格，且行末不得有多余空格。

输入样例：

8
123 899 51 998 27 33 36 12

1 2	8 123 899 51 998 27 33 36 12

输出样例：

4
3 6 9 26

1 2	4 3 6 9 26

分析：在接收输入数据的时候就把该数字的每一位相加，并把结果插入一个set集合中。因为set是有序的、不重复的，所以set的size值就是输出的个数，set中的每一个数字即所有答案的数字序列

此为Java版，C/C++版本请戳：http://www.liuchuo.net/archives/2889

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int numOfInteger = scanner.nextInt();
		Set<Integer> set = new TreeSet<Integer>();
		for (int i = 0; i < numOfInteger; i++) {
			int temp = scanner.nextInt();
			set.add(getFriendId(temp));
		}
		scanner.close();
		System.out.println(set.size());
		boolean isFirst = true;
		for (int id : set) {
			if (!isFirst) {
				System.out.print(" ");
			}
			System.out.print(id);
			isFirst = false;
		}
	}
	
	private static int getFriendId(int num) {
		int sum = 0;
		while(num != 0) {
			sum += num % 10;
			num /= 10;
		}
		return sum;
	}
}

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int numOfInteger = scanner.nextInt();

Set<Integer> set = new TreeSet<Integer>();

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

int temp = scanner.nextInt();

set.add(getFriendId(temp));

}

scanner.close();

System.out.println(set.size());

boolean isFirst = true;

for (int id : set) {

if (!isFirst) {

System.out.print(" ");

}

System.out.print(id);

isFirst = false;

}

private static int getFriendId(int num) {

int sum = 0;

while(num != 0) {

sum += num % 10;

num /= 10;

}

return sum;

}

PAT 1120. Friend Numbers (20) Java

Two integers are called “friend numbers” if they share the same sum of their digits, and the sum is their “friend ID”. For example, 123 and 51 are friend numbers since 1+2+3 = 5+1 = 6, and 6 is their friend ID. Given some numbers, you are supposed to count the number of different friend ID’s among them. Note: a number is considered a friend of itself.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then N positive integers are given in the next line, separated by spaces. All the numbers are less than 10⁴.

Output Specification:

For each case, print in the first line the number of different friend ID’s among the given integers. Then in the second line, output the friend ID’s in increasing order. The numbers must be separated by exactly one space and there must be no extra space at the end of the line.

Sample Input:

8
123 899 51 998 27 33 36 12

1 2	8 123 899 51 998 27 33 36 12

Sample Output:

4
3 6 9 26

1 2	4 3 6 9 26

此为Java版，C/C++版本请戳：http://www.liuchuo.net/archives/2901

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int numOfInteger = scanner.nextInt();
		Set<Integer> set = new TreeSet<Integer>();
		for (int i = 0; i < numOfInteger; i++) {
			int temp = scanner.nextInt();
			set.add(getFriendId(temp));
		}
		scanner.close();
		System.out.println(set.size());
		boolean isFirst = true;
		for (int id : set) {
			if (!isFirst) {
				System.out.print(" ");
			}
			System.out.print(id);
			isFirst = false;
		}
	}
	
	private static int getFriendId(int num) {
		int sum = 0;
		while(num != 0) {
			sum += num % 10;
			num /= 10;
		}
		return sum;
	}
}

import java.util.Scanner;

import java.util.Set;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int numOfInteger = scanner.nextInt();

Set<Integer> set = new TreeSet<Integer>();

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

int temp = scanner.nextInt();

set.add(getFriendId(temp));

}

scanner.close();

System.out.println(set.size());

boolean isFirst = true;

for (int id : set) {

if (!isFirst) {

System.out.print(" ");

}

System.out.print(id);

isFirst = false;

}

private static int getFriendId(int num) {

int sum = 0;

while(num != 0) {

sum += num % 10;

num /= 10;

}

return sum;

}

1121. Damn Single (25)-PAT甲级真题

“Damn Single (单身狗)” is the Chinese nickname for someone who is being single. You are supposed to find those who are alone in a big party, so they can be taken care of.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=50000), the total number of couples. Then N lines of the couples follow, each gives a couple of ID’s which are 5-digit numbers (i.e. from 00000 to 99999). After the list of couples, there is a positive integer M (<=10000) followed by M ID’s of the party guests. The numbers are separated by spaces. It is guaranteed that nobody is having bigamous marriage (重婚) or dangling with more than one companion.

Output Specification:

First print in a line the total number of lonely guests. Then in the next line, print their ID’s in increasing order. The numbers must be separated by exactly 1 space, and there must be no extra space at the end of the line.

Sample Input:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

Sample Output:

5
10000 23333 44444 55555 88888

分析：设立数组couple[i] = j表示i的对象是j。一开始先设置为都是-1。设立数组isExist表示某人的对象是否来到了派对上。接收数据的时候，对于每一对a和b，将couple的a设置为b，b设置为a，表示他俩是一对。对于每一个需要判断的人，将其存储在guest数组里面，如果它不是单身的（也就是如果它的couple[guest[i]] != -1）那么就将它对象的isExist设置为1，表示他对象的对象（也就是他自己）来到了派对。这样所有isExist不为1的人，对象是没有来到派对的。把所有的人遍历后插入一个集合set里面，set的size就是所求的人数，set里面的所有数就是所求的人的递增排列～～～

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
    int n, a, b, m;
    scanf("%d", &n);
    vector<int> couple(100000);
    for (int i = 0; i < 100000; i++)
        couple[i] = -1;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a, &b);
        couple[a] = b;
        couple[b] = a;
    }
    scanf("%d", &m);
    vector<int> guest(m), isExist(100000);
    for (int i = 0; i < m; i++) {
        scanf("%d", &guest[i]);
        if (couple[guest[i]] != -1)
            isExist[couple[guest[i]]] = 1;
    }
    set<int> s;
    for (int i = 0; i < m; i++)
        if (!isExist[guest[i]]) s.insert(guest[i]);
    printf("%d\n", s.size());
    for (auto it = s.begin(); it != s.end(); it++) {
        if (it != s.begin()) printf(" ");
        printf("%05d", *it);
    }
    return 0;
}

#include <iostream>

#include <set>

#include <vector>

using namespace std;

int main() {

int n, a, b, m;

scanf("%d", &n);

vector<int> couple(100000);

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

couple[i] = -1;

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

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

couple[a] = b;

couple[b] = a;

}

scanf("%d", &m);

vector<int> guest(m), isExist(100000);

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

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

if (couple[guest[i]] != -1)

isExist[couple[guest[i]]] = 1;

}

set<int> s;

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

if (!isExist[guest[i]]) s.insert(guest[i]);

printf("%d\n", s.size());

for (auto it = s.begin(); it != s.end(); it++) {

if (it != s.begin()) printf(" ");

printf("%05d", *it);

}

return 0;

}