# 1015 Reversible Primes (PTA)

reversible prime in any number system is a prime whose “reverse” in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (<10​5​​) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.

### Input Specification:

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

### Output Specification:

For each test case, print in one line `Yes` if N is a reversible prime with radix D, or `No` if not.

```73 10
23 2
23 10
-2

```

### Sample Output:

```Yes
Yes
No```

```import math
def IsPrime(num):
if num == 0 | num == 1:
return False
for i in range(2,int(math.sqrt(num))+1):
if num % i == 0:
return False
return True

result_num_lsit = []
if origin_num < base_num:
return origin_num
else:
while True:
div, mod = divmod(origin_num,base_num)
# result_num_lsit.insert(0,str(mod))
result_num_lsit.append(str(mod))
origin_num = div
if origin_num < base_num:
# result_num_lsit.insert(0,str(origin_num))
result_num_lsit.append(str(origin_num))
result_num = int(''.join(result_num_lsit))
return result_num

def ToDecimal(origin_num,base_num):
result_num = 0
index = 0
while True:
div, mod = divmod(origin_num,10)
result_num = result_num + mod*base_num**index
index+=1
origin_num = div
if div == 0:
return result_num

while True:
Input_Str = input().split(' ')
if int(Input_Str) < 0:
break

origin_num = int(Input_Str)
base_num = int(Input_Str)

result_num = ToDecimal(reverse_num,base_num)

if IsPrime(origin_num) & IsPrime(result_num):
print('Yes')
else:
print('No')```

# 1065 A+B and C (64bit) (PTA)

Given three integers AB and C in [−2​63​​,2​63​​], 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 AB 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```

```N = int(input())

index = 1
while(index<=N):
flag = 0
a, b, c = map(int,input().split(' '))
if a>0 & b>0 & a+b<0:
flag = 1
elif a<0 & b<0 & a+b>=0:
flag = 0
elif a+b>c:
flag = 1
print('Case #{}:'.format(index),"true" if flag else "false")
index +=1```

# 1028 List Sorting (PTA)

Excel can sort records according to any column. Now you are supposed to imitate this function.

### Input Specification:

Each input file contains one test case. For each case, the first line contains two integers N (≤10​5​​) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).

### Output Specification:

For each test case, output the sorting result in N lines. That is, if C = 1 then the records must be sorted in increasing order according to ID’s; if C = 2 then the records must be sorted in non-decreasing order according to names; and if C = 3 then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.

```3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

```

### Sample Output 1:

```000001 Zoe 60
000007 James 85
000010 Amy 90

```

```4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98

```

### Sample Output 2:

```000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60

```

```4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90

```

### Sample Output 3:

```000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90```

```N, ref = map(int, input().split())

records = []

for i in range(N):
s_id, name, score = input().split()
records.append([s_id, name, score])

records.sort(key=lambda x: (x[ref - 1],x))
for i in records:
print(" ".join(i))```

# 1031 Hello World for U (PTA)

Given any string of N (≥5) characters, you are asked to form the characters into the shape of `U`. For example, `helloworld` can be printed as:

```h  d
e  l
l  r
lowo

```

That is, the characters must be printed in the original order, starting top-down from the left vertical line with n​1​​ characters, then left to right along the bottom line with n​2​​ characters, and finally bottom-up along the vertical line with n​3​​ characters. And more, we would like `U` to be as squared as possible — that is, it must be satisfied that n​1​​=n​3​​=max { k | kn​2​​ for all 3≤n​2​​≤N } with n​1​​+n​2​​+n​3​​−2=N.

### Input Specification:

Each input file contains one test case. Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.

### Output Specification:

For each test case, print the input string in the shape of U as specified in the description.

### Sample Input:

```helloworld!

```

### Sample Output:

```h   !
e   d
l   l
lowor```

```string = input()
N = len(string)
height = (N+2)//3
width = N-2*height-2
for i in range(height - 1):
print(string[i] + ' '*(width+2) + string[-i-1])
print(string[height-1:N-height+1])```

# 1009 Product of Polynomials (PTA)

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 N​1​​ aN​1​​​​ N​2​​ aN​2​​​​ … 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​​<⋯<N​2​​<N​1​​≤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`

```p1 = list(input().split())
p2 = list(input().split())

d1 = {}
d2 = {}
d3 = {}

list1 = []

for i in range(1,len(p1),2):
if float(p1[i+1]) !=0:
d1[int(p1[i])] = float(p1[i+1])
for i in range(1,len(p2),2):
if float(p2[i+1]) !=0:
d2[int(p2[i])] = float(p2[i+1])

for k1 in d1:
for k2 in d2:
temp = d3.get(k1+k2,0) + d1.get(k1)*d2.get(k2)
if temp !=0:
d3[k1+k2] = round(temp,1)
else:
del d3[k1+k2]
list1 = [str(len(d3))]
if len(d3) != 0:
for i in sorted(d3.keys(),reverse = True):
list1.append(str(i))
list1.append(str(d3[i]))
else:
list1.append(str(0))
list1.append(str(0))

print(' '.join(list1))```

# 02-线性结构4 Pop Sequence (PTA)

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

### Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

### Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

```5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

```

### Sample Output:

```YES
NO
NO
YES
NO```

```M, N, K = map(int,input().split(' '))

std_list = [x for x in range(N+1)]

while K:
K -=1
input_list = [int(x) for x in input().split(' ')]
stack = 
i = 1
j = 0
while(len(stack)<=M+1):
if stack[-1] == input_list[j]:
stack.pop()
j+=1
if j == N:
print('YES')
break
else:
if i <= N:
stack.append(std_list[i])
i+=1
else:
break
if j != N:
print('NO')
```

# 02-线性结构3 Reversing Linked List (PTA)

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

### Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. 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:

`Address Data Next`

where `Address` is the position of the node, `Data` is an integer, and `Next` is the position of the next node.

### Output Specification:

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

### Sample Input:

```00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
```

### Sample Output:

```00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1```

Python 的代码在第五个测试点“ 最大N,最后剩K-1不反转 ”，运行超时。C++代码可以AC。

```d={}

start_addr, L, K = input().split(' ')
L = int(L)
K = int(K)

for i in range(L):

count = 0
for i in range(L):
break
else:
count += 1

res_index = 0
while(res_index + K <= count):
res_index += K

for i in range(len(addr_list) - 1):

```#include <iostream>
#include <algorithm>
#define MAXSIZE 100000
using namespace std;

struct LNode
{
int data;
int next;
}node[MAXSIZE];

int List[MAXSIZE];

int main()
{

for(int i = 0; i < n; i++)
{
cin >> data;
cin >> next;
}

int count = 0;

while(p_next!=-1)
{
List[count] = p_next;
p_next = node[p_next].next;
count = count + 1;
}

int first = 0;
while (first + k <= count)
{
reverse(&List[first], &List[first + k]);
first += k;
}

for(first = 0; first < count-1; first++)
printf("%05d %d %05d\n", List[first], node[List[first]].data, List[first + 1]);
printf("%05d %d -1\n", List[first], node[List[first]].data);
return 0;
} ```

# 02-线性结构2 一元多项式的乘法与加法运算 (PTA)

### 输入样例:

```4 3 4 -5 2  6 1 -2 0
3 5 20  -7 4  3 1
```

### 输出样例:

```15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0```

```p1 = list(input().split())
p2 = list(input().split())

d1 = {}
d1c = {}
d2 = {}
d2c = {}

d3 = {}
d4 = {}

list1 = []
list2 = []

for i in range(1,len(p1),2):
if int(p1[i]) !=0:
d1[int(p1[i+1])] = int(p1[i])
for i in range(1,len(p2),2):
if int(p2[i]) !=0:
d2[int(p2[i+1])] = int(p2[i])

#polu multi
d1c = d1.copy()
d2c = d2.copy()
for k1 in d1c:
for k2 in d2c:
temp = d4.get(k1+k2,0) + d1c.get(k1)*d2c.get(k2)
if temp !=0:
d4[k1+k2] = temp
else:
del d4[k1+k2]

if len(d4) != 0:
for i in sorted(d4.keys(),reverse = True):
list1.append(str(d4[i]))
list1.append(str(i))
else:
list1.append(str(0))
list1.append(str(0))

#poly plus
d3 = d2.copy()
for k1 in d1:
temp = d3.get(k1,0) + d1.get(k1)
if (temp!=0):
d3[k1] = temp
else:
del d3[k1]

if len(d3) != 0:
for i in sorted(d3.keys(),reverse = True):
list2.append(str(d3[i]))
list2.append(str(i))
else:
list2.append(str(0))
list2.append(str(0))

print(' '.join(list1))
print(' '.join(list2))  ```