## 1161 Merging Linked Lists – PAT甲级真题

Given two singly linked lists L1​=a1​→a2​→⋯→an−1​→an​ and L2​=b1​→b2​→⋯→bm−1​→bm​. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1​→a2​→bm​→a3​→a4​→bm−1​⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

### Input Specification:

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1​ and L2​, plus a positive N (≤105) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by `-1`.

Then N lines follow, each describes a node in the format:

where `Address` is the position of the node, `Data` is a positive integer no more than 105, and `Next` is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

### Output Specification:

For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

## 1160 Forever – PAT甲级真题

“Forever number” is a positive integer A with K digits, satisfying the following constrains:

• the sum of all the digits of A is m;
• the sum of all the digits of A+1 is n; and
• the greatest common divisor of m and n is a prime number which is greater than 2.

Now you are supposed to find these forever numbers.

### Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description.

### Output Specification:

For each pair of K and m, first print in a line `Case X`, where `X` is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output `No Solution`.

2
6 45
7 80

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

## 1159 Structure of a Binary Tree – PAT甲级真题

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

• A is the root
• A and B are siblings
• A is the parent of B
• A is the left child of B
• A is the right child of B
• A and B are on the same level
• It is a full tree

Note:

• Two nodes are on the same level, means that they have the same depth.
• full binary tree is a tree in which every node other than the leaves has two children.

### Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 103 and are separated by a space.

Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both `A` and `B` in the statements are in the tree.

### Output Specification:

For each statement, print in a line `Yes` if it is correct, or `No` if not.

### Sample Input:

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Yes
No
Yes
No
Yes
Yes
Yes

## 1158 Telefraud Detection – PAT甲级真题

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than K short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a short phone call to B means that the total duration of the calls from A to B is no more than 5 minutes.

### Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers K (≤500, the threshold（阈值） of the amount of short phone calls), N (≤103, the number of different phone numbers), and M (≤105, the number of phone call records). Then M lines of one day’s records are given, each in the format:

where `caller` and `receiver` are numbered from 1 to N, and `duration` is no more than 1440 minutes in a day.

### Output Specification:

Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

If no one is detected, output `None` instead.

5 15 31
1 4 2
1 5 2
1 5 4
1 7 5
1 8 3
1 9 1
1 6 5
1 15 2
1 15 5
3 2 2
3 5 15
3 13 1
3 12 1
3 14 1
3 10 2
3 11 5
5 2 1
5 3 10
5 1 1
5 7 2
5 6 1
5 13 4
5 15 1
11 10 5
12 14 1
6 1 1
6 9 2
6 10 5
6 11 2
6 12 1
6 13 1

### Sample Output 1:

3 5
6

Note: In sample 1, although `1` had 9 records, but there were 7 distinct receivers, among which `5` and `15` both had conversations lasted more than 5 minutes in total. Hence `1` had made 5 short phone calls and didn’t exceed the threshold 5, and therefore is not a suspect.

5 7 8
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 1 1
3 1 1

None

## 1157 Anniversary – PAT甲级真题

Zhejiang University is about to celebrate her 122th anniversary in 2019. To prepare for the celebration, the alumni association （校友会） has gathered the ID’s of all her alumni. Now your job is to write a program to count the number of alumni among all the people who come to the celebration.

### Input Specification:

Each input file contains one test case. For each case, the first part is about the information of all the alumni. Given in the first line is a positive integer N (≤105). Then N lines follow, each contains an ID number of an alumnus. An ID number is a string of 18 digits or the letter `X`. It is guaranteed that all the ID’s are distinct.

The next part gives the information of all the people who come to the celebration. Again given in the first line is a positive integer M (≤105). Then M lines follow, each contains an ID number of a guest. It is guaranteed that all the ID’s are distinct.

### Output Specification:

First print in a line the number of alumni among all the people who come to the celebration. Then in the second line, print the ID of the oldest alumnus — notice that the 7th – 14th digits of the ID gives one’s birth date. If no alumnus comes, output the ID of the oldest guest instead. It is guaranteed that such an alumnus or guest is unique.

### Sample Input:

5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042

### Sample Output:

3
150702193604190912

## 1156 Sexy Primes – PAT甲级真题

Sexy primes are pairs of primes of the form (pp+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)

Now given an integer, you are supposed to tell if it is a sexy prime.

### Input Specification:

Each input file contains one test case. Each case gives a positive integer N (≤108).

### Output Specification:

For each case, print in a line `Yes` if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print `No` instead, then print in the next line the smallest sexy prime which is larger than N.

47

Yes
41

21

No
23