标签归档:PTA

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.

Sample Input:

73 10
23 2
23 10
-2

      
    

Sample Output:

Yes
Yes
No

编译器:Python(python3)

写了三个函数分别是:素数判断,十进制转任意进制的逆序和任意进制转十进制

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

def reverse_Radix(origin_num,base_num):
    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]) < 0:
        break

    origin_num = int(Input_Str[0])
    base_num = int(Input_Str[1])

    reverse_num = reverse_Radix(origin_num,base_num)

    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

编译器:Python(python3)

判断溢出

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.

Sample Input 1:

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

      
    

Sample Output 1:

000001 Zoe 60
000007 James 85
000010 Amy 90

      
    

Sample Input 2:

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

      
    

Sample Input 3:

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

编译器:Python(python3)

这题用list的sort方法,其中可以按key关键字排序,但是python的缺点就是最后一个测试点超时,但是不想用C++再写了。

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[0]))
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

编译器:Python(python3)

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

编译器:Python(python3)





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.

Sample Input:

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

编译器:Python(python3)

这题的思路就是用list的append和pop来模拟堆栈,思路比较清晰,大概调试了2个小时(笑哭

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 = [0]
    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。

思路相同, 先读取有效的数据,排除不在链表上的节点 ,然后用有序列表的部分反转操作达到反转。Python效率不如C++,C++用4ms算完的,Python要22ms,最大长度C++花了200多ms,而这题限制400ms。也想不出优化的地方了。

编译器:Python(python3)

d={}

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

for i in range(L):
    addr1, data, next_addr = input().split(' ')
    d[addr1] = [data,next_addr]

addr_list = []
count = 0
temp_addr = start_addr 
for i in range(L):
    if temp_addr == '-1':
        break
    else:
        count += 1
        addr_list.append(temp_addr)
        temp_addr = d[temp_addr][1]

res_index = 0
while(res_index + K <= count):
    sub_list = addr_list[res_index:res_index+K]
    addr_list[res_index:res_index+K] = sub_list[::-1]
    res_index += K

for i in range(len(addr_list) - 1):
    print(addr_list[i],d[ addr_list[i] ][0],addr_list[i+1])
print(addr_list[-1],d[ addr_list[-1] ][0],'-1') 

编译器:C++(g++)

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

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

int List[MAXSIZE];

int main()
{
    int head_addr, n, k;
    cin >> head_addr >> n >> k;

    int addr, data, next;
    for(int i = 0; i < n; i++)
    {
        cin >> addr;
        cin >> data;
        cin >> next;
        node[addr].data = data;
        node[addr].next = next;
    }

    int count = 0;
    int p_next = head_addr;

    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)

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

输出格式:

输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0

输入样例:

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

编译器:Python(python3)

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))