1022 Digital Library (30分)

题目

题目

题目

def find(line, pos, booktitle, author, publisher, key):
    print(line)
    result = []
    query = line[3:]
    if pos == 1:
        try:
            result = booktitle[query]
            result = sorted(result)
            for x in result:
                print(x)
        except:
            print('Not Found')
    elif pos == 2:
        try:
            result = author[query]
            result = sorted(result)
            for x in result:
                print(x)
        except:
            print('Not Found')
    elif pos == 4:
        try:
            result = publisher[query]
            result = sorted(result)
            for x in result:
                print(x)
        except:
            print('Not Found')
    elif pos == 5:
        try:
            result = puby[query]
            result = sorted(result)
            for x in result:
                print(x)
        except:
            print('Not Found')
    else:
        try:
            result = key[query]
            result = sorted(result)
            for x in result:
                print(x)
        except:
            print('Not Found')
def check(line, booktitle, author, publisher, puby):
    query = line[3:]
    if query in booktitle:
        return 1
    elif query in author:
        return 2
    elif query in publisher:
        return 4
    elif query.isnumeric():
        return 5
    else:
        return 3
if __name__ == "__main__":
    n = int(input())
    puby = {}
    booktitle = {}
    author = {}
    publisher = {}
    key = {}
    for x in range(n):
        ID = input()
        for i in range(5):
            line = input()
            if i==0:
                try:
                    booktitle[line].append(ID)
                except:
                    booktitle[line]=[ID]
            elif i==1:
                try:
                    author[line].append(ID)
                except:
                    author[line] = [ID]
            elif i==2:
                for j in line.split(" "):
                    try:
                        key[j].append(ID)
                    except:
                        key[j] = [ID]
            elif i==3:
                try:
                    publisher[line].append(ID)
                except:
                    publisher[line] = [ID]
            elif i==4:
                try:
                    puby[line].append(ID)
                except:
                    puby[line] = [ID]
    m = int(input())
    for x in range(m):
        line = input()
        pos = check(line, booktitle, author, publisher, puby)
        find(line, pos, booktitle, author, publisher, key)

1023 Have Fun with Numbers (20分)

题目

from collections import Counter
num=input()
x=str(int(num)*2)
a=Counter(num)
b=Counter(x)
if a==b:
    print( 'Yes')
else:
    print('No')
print(x)

1024 Palindromic Number (25分)

题目

题目

def main():
    line = input().split(" ")
    n, k = line[0], int(line[1])
    for x in range(k):
        if  n == n[::-1] :
            print(n)
            print(x)
            return
        else:
            n = str(int(n) + int(n[::-1]))
    print(n)
    print(k)
if __name__ == "__main__":
    main()

1025 PAT Ranking (25分)

题目

题目

def main():
    n = int(input())
    tests = []
    count = 0
    for x in range(n):
        k = int(input())
        count += k
        temp = []
        for i in range(k):
            line = input().split(" ")
            unit = [line[0], -1, str(x+1), -1, int(line[1])]#number,-1,分组,-1，得分
            temp.append(unit)
        temp = sorted(temp, key = lambda i : (-i[4], i[0]))
        temp[0][3] = '1'
        for i in range(1, k):
            if temp[i][4] != temp[i-1][4]:
                temp[i][3] = str(i+1)
            else:
                temp[i][3] = temp[i-1][3]
        tests += temp
    tests = sorted(tests, key = lambda x:(-x[4], x[0]))
    tests[0][1] = '1'
    print(count)
    print(' '.join(tests[0][:-1]))
    for i in range(1, count):
        if tests[i][4] != tests[i-1][4]:
            tests[i][1] = str(i+1)
        else:
            tests[i][1] = tests[i-1][1]
        print(' '.join(tests[i][:-1]))
if __name__ == "__main__":
    main()

1026 Table Tennis (30分)

题目

题目

1027 Colors in Mars (20分)

题目

def change(num):
    l = '0123456789ABC'
    a = int(num)
    first, second = a // 13, a % 13
    return l[first] + l[second]
if __name__ == "__main__":
    line = input().split(" ")
    result = ''
    for x in line:
        result += change(x)
    print('#'+result)

1028 List Sorting (25分)

题目

题目

def main():
    line = input().split(" ")
    n = int(line[0])
    c =line[1]
    records = []
    for x in range(n):
        line = input()
        records.append(line)
    if c == '1':
        records = sorted(records)
    elif c == '2':
        records = sorted(records, key = lambda x : (x[7:-3], x[:6]))
    elif c== '3':
        records = sorted(records, key = lambda x : (x[-2:], x[:6]))
    for x in records:
        print(x)
if __name__ == "__main__":
    main()

1029 Median (25分)

题目

1030 Travel Plan (30分)

题目

def main():
    line = input().split(" ")
    n,m,s,d = [int(x) for x in line]
    route = [ [[-1,-1] for x in range(n)] for x in range(n)]
    for x in range(m):
        line = input().split(" ")
        a, b, dis, cost = [int(x) for x in line]
        route[a][b], route[b][a] = [dis,cost], [dis,cost]
    path = [[] for x in range(n)]
    weight = [float("inf") for x in range(n)]
    point = [float("inf") for x in range(n)]
    visted = [0 for x in range(n)]
    path[s] = [s]
    visted[s] = 1
    point[s], weight[s] = 0, 0
    node = s
    while(node != -1):
        nodes = [x for x in range(n) if route[node][x] != [-1,-1] and visted[x] == 0]
        for x in nodes:
            if weight[node] + route[node][x][0] < weight[x]:
                weight[x] = weight[node] + route[node][x][0]
                point[x] = point[node] + route[node][x][1]
                path[x] = path[node] + [x]
            elif weight[node] + route[node][x][0] == weight[x]:
                if point[node] + route[node][x][1] < point[x]:
                    path[x] = path[node] + [x]
                    point[x] = point[node] + route[node][x][1]
        avai = [x for x in range(n) if weight[x] != float("inf") and visted[x]==0]
        if len(avai) == 0:
            node = -1
        else:
            node = sorted(avai,key = lambda x : weight[x])[0]
            visted[node] = 1
    print(*path[d], weight[d], point[d])
if __name__ == "__main__":
    main()

1031 Hello World for U (20分)

题目

def main():
    line = list(input())
    num = len(line)
    ava = [float('inf'),0]
    for x in range(3, num):
        if (num+2-x) % 2 == 0:
            if x >= (num+2-x) / 2:
                if x - ((num+2-x) / 2) < ava[0]-ava[1]:
                    ava = [x,(num+2-x) / 2]
    result = ''
    for x in range(int(ava[1]-1)):
        result = result + line.pop(0)+' '*(ava[0]-2) + line.pop(-1)+'\n'
    result+= ''.join(line)
    print(result)
if __name__ =="__main__":
    main()

1032 Sharing (25分)

题目

题目

def main():
    line = input().split(" ")
    first, second = line[0], line[1]
    n = int(line[2])
    if first == second:
        print(first)
        return
    else:
        dic = {}
        for x in range(n):
            line = input().split(" ")
            dic[line[0]] = [line[-1],False]
    while(first != '-1'):
        dic[first][1] = True
        first = dic[first][0] #读入下一个节点
    while(second != '-1'):
        if dic[second][1]:
            print(second)
            return
        second = dic[second][0]
    print(-1)
if __name__ == "__main__":
    main()

1033 To Fill or Not to Fill (25分)

题目

题目

# 贪心算法
def main():    
    line = input().split(" ")
    capacity, dis, per, n = (int(x) for x in line)
    station = {}
    for x in range(n):
        line = input().split(" ")
        price, length = float(line[0]), int(line[1])
        station[length] = price
    station[dis] = 0
    contain, now, price = 0, 0, 0
    if 0 not in station:
        print('The maximum travel distance = 0.00')
    while(0 in station):
        if now == dis:
            print('{:.2f}'.format(price))
            break
        longest = int(now + capacity * per) # 当前可行驶的最长距离
        temp = sorted([x for x in station if x > now and x <= longest])#能到达的加油站
        if len(temp) > 0:
            arri = sorted([[x, station[x]] for x in temp], key = lambda x : x[1])
            b = sorted([x for x in arri if x[1] <= station[now]])
            if len(b) == 0:
                target = arri[0][0]
                price = price +  (capacity - contain) * station[now]
                contain = capacity - (target - now) / per
                now = target
            else: #寻找价格更低的加油站
                target = b[0][0]
                need = (target - now) / per
                price += (need-contain) * station[now]
                contain = 0
                now = target
        else:
            result='The maximum travel distance = {:.2f}'.format(longest)
            print(result)
            break
if __name__ =="__main__":
    main()

1034 Head of a Gang (30分)

题目

题目

# 图遍历
class person:
    def __init__(self, name, total):
        self.link = []
        self.name = n
        self.total = total
def bfs(persons):
    global result
    while(len(persons) > 0):
        temp, t = [], []
        start = [ list(persons.keys()) [0]]
        temp += start
        while(len(start) >0):
            for x in start:
                for i in persons[x].link:
                    if i not in temp and i not in t:
                        t.append(i)
            start, t = t, []
            temp += start
        a = max([ [persons[x].total,x] for x in temp])
        sums = 0
        for x in temp:
            sums += persons[x].total
        result.append([a[1], len(temp), sums/2])
        for x in temp:
            persons.pop(x)
if __name__ == "__main__":
    result = []
    line = input().split(" ")
    n, limit = int(line[0]), int(line[1])
    persons = {}
    for x in range(n):
        line = input().split(" ")
        first, second = line[0], line[1]
        m = int(line[2])
        try:
            persons[first].total += m
            if second not in persons[first].link:
                persons[first].link.append(second)
        except:
            p = person(first, m)
            persons[first] = p
            persons[first].link.append(second)
        try:
            persons[second].total += m
            if first not in persons[second].link:
                persons[second].link.append(first)
        except:
            p = person(second, m)
            persons[second] = p
            persons[second].link.append(first)
    bfs(persons)
    result = sorted([x for x in result if x[1] > 2 and x[2] > limit])
    print(len(result))
    for x in result:
        print(x[0],x[1])

1035 Password (20分)

题目

题目

def main():
    n = int(input())
    count = n
    a = {'1':'@','0':'%','l':'L','O':'o'}
    result = []
    for x in range(n):
        line = input().split(" ")
        flag = False
        for i in a:
            if i in line[1]:
                flag = True
                line[1] = line[1].replace(i,a[i])
        if flag:
            result.append([line[0], line[1]])
            count -= 1
    if len(result) !=0:
        print(len(result))
        for x in result:
            print(x[0],x[1])
    elif count > 0 :
        if count == 1:
            print('There is 1 account and no account is modified')
        else:
            print('There are {} accounts and no account is modified'.format(count))
if __name__ == "__main__":
    main()

1036 Boys vs Girls (25分)

题目

题目

def main():
    n = int(input())
    male, femal = [], []
    for x in range(n):
        line = input().split(" ")
        name, sex = line[0], line[1]
        ID, grade = line[2], int(line[3])
        if sex == "M":
            male.append([name, ID, grade])
        else:
            femal.append([name, ID, grade])
    if len(femal) == 0:
        print("Absent")
    else:
        stu = max(femal, key = lambda x : x[2])
        print(stu[0], stu[1])
        temp = stu[2]
    if len(male) == 0:
        print("Absent")
    else:
        stu = min(male, key = lambda x : x[2])
        print(stu[0], stu[1])
    if len(male) > 0 and len(femal) >0:
        print(abs(stu[2] - temp))
    else:
        print("NA")
if __name__ == "__main__":
    main()

1037 Magic Coupon (25分)

题目

def main():
    n1 = int(input())
    line = input().split(" ")
    list1_xiao = sorted([int(x) for x in line if int(x) <0])
    list1_da = sorted([int(x) for x in line if int(x) >0])
    n2 = int(input())
    line = input().split(" ")
    list2_xiao = sorted([int(x) for x in line if int(x) <0])
    list2_da = sorted([int(x) for x in line if int(x) >0])
    result = 0
    for x in range(min([len(list1_xiao),len(list2_xiao)])):
        result += list1_xiao[x] * list2_xiao[x]
    for x in range(min([len(list1_da),len(list2_da)])):
        result += list1_da[len(list1_da)-1-x] * list2_da[len(list2_da)-1-x]
    print(result)
if __name__ == "__main__":
    main()

1038 Recover the Smallest Number (30分)

题目

def main():
    get = input().split(" ")
    a=get[1:]
    num=int(get[0])
    for x in range(num):
        for i in range(num-1):
            temp = a.copy()
            temp[i],temp[i+1] = temp[i+1],temp[i]
            if(''.join(temp)<''.join(a)):
                a = temp
                break
    result = ''.join(a)
    print(int(result))
if __name__ == "__main__":
    main()

1039 Course List for Student (25分)

题目

题目

def main():
    line = input().split(" ")
    n, k = int(line[0]), int(line[1])
    stu = {}
    for x in range(k):
        line = input().split(" ")
        index, num = int(line[0]), int(line[1])
        if num >0:
            line = input().split(" ")
            for x in line:
                try:
                    stu[x].append(index)
                except:
                    stu[x] = [index]
    query = input().split(" ")
    for i in range(n):
        x = query[i]
        result=[x]
        if x in stu.keys():
            temp = sorted(stu[x])
            result.append(len(temp))
            result += temp
        else:
            result.append(0)
        print(*result)
if __name__ =="__main__":
    main()

1040 Longest Symmetric String (25分)

题目

# 最长回文子序列
def main():
    line = input()
    n = len(line)
    flag = [ [1 for x in range(n)] for x in range(n)]
    maxs = 0
    for x in range(1,n+1):
        for i in range(n-x):
            if line[i] == line[i+x] and flag[i+1][i+x-1] == 1:
                if x > maxs:
                    maxs = x
            else:
                flag[i][i+x] = 0
    print(maxs+1)
if __name__ == "__main__":
    main()

1041 Be Unique (20分)

题目

# 寻找第一个独立出现的数字
import collections
a=input().split()
n=int(a[0])
num=a[1:]
flag=False
obj = collections.Counter(num)
for x in obj:
    if obj[x]==1:
        print(x)
        flag=True
        break
if not flag:
    print('None')

1042 Shuffling Machine (20分)

题目

题目

def main():
    pai = ["S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13",
        "H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13",
        "C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13",
        "D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13",
        "J1","J2"]
    n = int(input())
    line = input().split(" ")
    order = [int(x)-1 for x in line]
    for x in range(n):
        temp = pai.copy()
        for i in range(54):
            temp[order[i]]= pai[i]
        pai = temp
    print(*pai)
if __name__ == "__main__":
    main()

1043 Is It a Binary Search Tree (25分)

题目

题目

# 左节点小于根节点
# 右节点大于等于根节点
# 左右都是二叉搜索树
# 左右交换，镜像二叉搜索树
# 判断是否是前序遍历的二叉搜索或镜像二叉搜索 前序（根左右）

def dfs(get, types):
    global pos
    left,right = [],[]
    if types == 0: #二叉搜索判断
        x = 1
        try:
            for x in range(1, len(get)):
                if get[x] < get[0]:
                    left.append(get[x])
                else:
                    break
        except:
            pass
        right = [x for x in get[x:] if x>= get[0]]
    elif types ==  1: # 镜像判断
        x = 1
        try:
            for x in range(1,  len(get)):
                if get[x] >= get[0]:
                    left.append(get[x])
                else:
                    break
        except:
            pass
        right = [x for x in get[x:] if x < get[0]]
    if len(left) > 0:
        dfs(left, types)
    if len(right) >0 :
        dfs(right, types)
    pos.append(get[0])
if __name__ == "__main__":
    n = int(input())
    line = input().split(" ")
    get = [int(x) for x in line]
    pos = []
    dfs(get, 0)
    if len(pos) == n:
        print("YES")
        print(*pos)
    else:
        pos = []
        dfs(get, 1)
        if len(pos) == n:
            print("YES")
            print(*pos)
        else:
            print("NO")

1044 Shopping in Mars (25分)

题目

题目

1045 Favorite Color Stripe (30分)

题目

"""
遍历chain中的每一个元素，判断它前面的序列中是否有比它小的元素，即在喜欢的序列中出现在它前面的元素。
如果没有，则说明该元素只能作为一个子列的起始，在num字典中，以该元素为键值存储，值为1.
如果存在出现在它之前的元素，则取出在num字典中的最大值a，更新该元素在num字典中的值为a+1，并判断是否大于result，如果大于则更新result。
"""

def main():
    n = int(input())
    line = input().split(" ")
    like = [int(x) for x in line[1:]]
    dic = {like[x]:x for x in range(len(like))}
    line = input().split(" ")
    chain = [dic[int(x)] for x in line[1:] if int(x) in like]
    num = {x:0  for x in range(n)}
    result = 1
    for x in range(len(chain)):
        now = chain[x]
        temp = sorted([ [i, num[i]] for i in num if i <= now], key = lambda j : -j[1])
        if len(temp) == 0:
            num[now] = 1
        else:
            num[now] = temp[0][1] + 1
            if num[now] > result:
                result = num[now]
    print(result)
if __name__ == "__main__":
    main()

1046 Shortest Distance (20分)

题目

# N个距离，D1...DN
def main():
    line = input().split(" ")
    num = int(line[0])
    dis = [int(x) for x in line[1:]]
    n = int(input())
    total = sum(dis)
    dic = {1:0}
    count = 0
    for x in range(num-1):
        dic[x+2] = count + dis[x]
        count += dis[x]
    for x in range(n):
        line = input().split(" ")
        left = abs(dic[int(line[0])] - dic[int(line[1])])
        right = total - left
        print(min([left, right]))
if __name__ == "__main__":
    main()

1047 Student List for Course (25分)

题目

题目

def main():
    line = input().split(" ")
    n, k = int(line[0]), int(line[1])
    dic = {key+1 : [] for key in range(k)}
    for x in range(n):
        line = input().split(" ")
        name = line[0]
        course = line[2:]
        for i in course:
            dic[int(i)].append(name)
    for x in dic:
        dic[x] = sorted(dic[x])
    for x in dic:
        print(x, len(dic[x]))
        for i in dic[x]:
            print(i)
if __name__ == "__main__":
    main()

1048 Find Coins (25分)

题目

题目

def main():
    line = input().split(" ")
    n, m = int(line[0]), int(line[1])
    line = input().split(" ")
    num = [int(x) for x in line]
    dic = [0 for x in range(1000)]
    for x in num:
        dic[x] += 1
    for x in range(1000):
        if dic[x] > 0:
            temp = m - x
            if temp != x:
                if dic[temp] > 0:
                    print(x,temp)
                    return
            else:
                if dic[temp] > 1:
                    print(x,temp)
                    return
    print("No Solution")
if __name__ == "__main__":
    main()

1049 Counting Ones (30分)

题目

def main():
    n = input()
    result, a = 0,  1
    for x in range(1, len(n) + 1):
        index = len(n) - x
        if n[index] == '0':
            left = n[:index] if n[:index] !='' else 0
            result += int(n[:index]) * a
        elif n[index] == '1':
            left = n[:index] if n[:index] !='' else 0
            right = n[index+1:] if n[index+1:] != '' else 0
            result += int(left)*a + int(right) +1
        else:
            left = n[:index] if n[:index] !='' else 0
            result += (int(left)+1)*a
        a *= 10
    print(result)
if __name__ == "__main__":
    main()

1050 String Subtraction (20分)

题目

a=input()
b=input()
for x in b:
    a=a.replace(x,'')
print(a)

1051 Pop Sequence (25分)

题目

# 判断有可能的出栈顺序
def main():
    line1 = input().split(" ")
    m,n,k = int(line1[0]),int(line1[1]),int(line1[2])
    for x in range(k):
        line = input().split(" ")
        pop = [int(x) for x in line]
        stack = []
        start = 1
        flag = True
        while(start <= n):
            if(start == pop[0]):
                start += 1
                pop.pop(0)
            elif(len(stack)==0):
                stack.append(start)
                start += 1
            elif(stack[-1] == pop[0]):
                stack.pop(-1)
                pop.pop(0)
            elif(len(stack) < m-1):
                stack.append(start)
                start += 1
            else:
                flag = False
                break
        stack = stack[::-1]
        if stack != pop:
            flag = False
        if(flag):
            print("YES")
        else:
            print("NO")
if __name__ == "__main__":
    main()

1052 Linked List Sorting (25分)

题目

题目

def main():
    line = input().split(" ")
    n = int(line[0])
    start = line[1]
    nodes = {}
    for x in range(n):
        line = input().split(" ")
        nodes[line[0]] = [line[0], int(line[1]), line[2]]
    data = []
    while(start != '-1'):
        item = nodes[start]
        data.append(item)
        start = item[-1]
    data = sorted(data, key = lambda x : x[1])
    num = len(data)
    for x in range(num):
        if x != num - 1:
            data[x][-1] = data[x+1][0]
        else:
            data[x][-1] = '-1'
    if num == 0:
        print(0, -1)
    else:
        print(num, data[0][0])
        for x in data:
            print(x[0], x[1], x[2])
if __name__ == "__main__":
    main()