【2020-02-28】pat甲级(1001-1021)
2020-03-14 本文已影响0人
BigBigFlower
1001 A+B Format (20分)
Calculate a+b and output the sum in standard format -- that is, the digits must be separated into groups of three by commas (unless there are less than four digits).
Input Specification:
Each input file contains one test case. Each case contains a pair of integers a and b where −10^6 ≤a,b≤10^6 . The numbers are separated by a space.
Output Specification:
For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.
Sample Input:
-1000000 9
Sample Output:
-999,991
nums=input()
a,b=int(nums.split(" ")[0]),int(nums.split(" ")[1])
num=a+b
print('{:,}'.format(num))
1002 A+B for Polynomials (25分)
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:
image.png
Output Specification:
For each test case you should output the sum 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 to 1 decimal place.
Sample Input:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output:
3 2 1.5 1 2.9 0 3.2
# 合并两个多项式
firstline={}
secondline={}
line1=input().split(" ") #读入第一行
for ele in range(int(line1[0])): # 非零项
firstline[int(line1[1+ele*2])]=float(line1[2+ele*2])# 构建指数和幂和对应字典
line2=input().split(" ") #读入第二行
for ele in range(int(line2[0])):
secondline[int(line2[1+ele*2])]=float(line2[2+ele*2])
a=sorted(list(firstline.keys()),key=lambda x: -x) #提取指数
b=sorted(list(secondline.keys()),key=lambda x: -x)
c=sorted(list(set(a+b)),key=lambda x: -x)
out={}
for x in c:
if x in a and x in b:
out[x]=firstline[x]+secondline[x] #指数一致时系数相加
else:
if x in a:
out[x]=firstline[x]
else:
out[x]=secondline[x]
res=" "
num=0
for t in c:
if out[t]!=0:
num=num+1
res=res+str(t)+" "+'{:.1f}'.format(out[t])+" "
print(str(num)+res[:-1])
1003 Emergency (25分)
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input Specification:
input
Output Specification:
output
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4
# 第一行：城市数、道路输、目前所在城市、需急救城市、
# 第二行：每个城市的急救队数量
# C1、C2、L 两个城市之间的路长
# 寻找最短路径
#点的属性<城市编号、救急队数量>
# 边的属性<<city1,city2>,L>
# 最短路径
# dijkstra
a=input().split(" ")
cities,rodes,currenty,savecity=int(a[0]),int(a[1]),int(a[2]),int(a[3])
b=input().split(" ")
point=[int(x) for x in b] #点权重
route=[[0 for x in range(cities)] for i in range(cities)] #点到点的距离，初始化为0
for x in range(rodes):
m=input().split(" ")
p,q,k=int(m[0]),int(m[1]),int(m[2])
route[p][q]=k
route[q][p]=k
visited=[0 for x in range(cities)]# 标识走过的点
weight=[float('inf') for x in range(cities)]#边权重，点到点的最短路径，初始化为无穷大
power=[0 for x in range(cities)] # 累积的点权重
weight[currenty]=0
power[currenty]=point[currenty]
visited[currenty]=1
x=currenty
num=[0 for x in range(cities)]
num[currenty]=1
while visited[savecity]==0:
for i in range(cities):
if route[x][i]!=0 and visited[i]!=1:# x->i 有路径，且未访问
if weight[i]>=weight[x]+route[x][i]:
if weight[i]==weight[x]+route[x][i]:
num[i]=num[i]+num[x]
if power[i]<power[x]+point[i]:
power[i]=power[x]+point[i]
else:
if weight[i]>weight[x]+route[x][i]:
power[i]=power[x]+point[i]
num[i]=num[x]
weight[i]=weight[x]+route[x][i]
small=sorted([weight[x] for x in range(cities) if visited[x]!=1])[0]
index=[x for x in range(cities) if weight[x]==small and visited[x]!=1][0]
visited[index]=1
x=index
print(num[savecity],power[savecity])
1004 Counting Leaves (30分)
题目
# 没通过
# 给定一棵树，求每一层的叶子节点数
# 第一行n（节点个数）,m（无叶子节点的节点个数）
# 第二行 id无叶子节点，k叶子节点个数，id[1].....id[k]
tmap={} # 记录非叶子节点
record=[0 for i in range(101)] #记录数的深度
def dfs(id,level):
if not id in tmap:
record[level]+=1
return
for cid in tmap[id]:
dfs(cid,level+1)
n,m=map(int,input().split())# n 节点个数，m无叶子节点的节点个数
for i in range(m):
line=input().split() #读取数据
rid=int(line[0]) #
k=int(line(1)) # 叶子节点个数
tmap[rid]=[]
for cid in line[2:]:
cid=int(cid)
tmap[rid].append(cid)
dfs(1,0)
cnt=record[0]
cle=n-m
result=str(record[0])
for i in range(1,101):
if cnt>=cle:
break
result+=" "+str(record[i])
cnt+=record[i]
print(result)
1005 Spell It Right (20分)
题
dict={1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',0:'zero'}
a=input()
b=[int(x) for x in str(a)]
c=sum(b)
for x in str(c):
result=result+dict[int(x)]+" "
print(result[:-1])
1006 Sign In and Sign Out (25分)
题目
import time
num = int(input())
record = []
for x in range(num):
line = input().split(" ")
unit = [line[0]]
for i in line[1:]:
timeStruct = time.strptime('2020-01-01 '+i, "%Y-%m-%d %H:%M:%S")
timeStamp = int(time.mktime(timeStruct))
unit.append(timeStamp)
record.append(unit)
early = min([ x[1] for x in record])
late = max([x[2] for x in record])
first = [x for x in range(num) if record[x][1] == early][0]
last = [x for x in range(num) if record[x][2] == late][0]
print(record[first][0], record[last][0])
1007 Maximum Subsequence Sum (25分)
题目
a=int(input())
number=input().split()
seq=[int(x) for x in number]
flag=True
if len([x for x in seq if x>=0])==0:
flag=False
print(0,seq[0],seq[-1])
res= -1
tmp,tmpleft,index,right,left=0,0,0,0,0
if flag==True:
while(index!=len(seq)):
tmp=tmp+seq[index]
index+=1
if tmp<0:
tmp=0
tmpleft=index
elif tmp>res:
res=tmp
left=tmpleft
right=index-1
print(res,seq[left],seq[right])
1008、Elevator (20分)
题目
# 升一层需6s 降一层需4s 每一层停留5s
a=input()
a=a.split()
floor=[0]
for i in range(1,len(a)):
floor.append(int(a[i]))
res=0
for i in range(1,len(floor)):
if floor[i-1]-floor[i]<0:
res=res+5+abs(floor[i-1]-floor[i])*6
else:
res=res+5+abs(floor[i-1]-floor[i])*4
print(res)
1009、Product of Polynomials (25分)
题目
line1=input().split()
line2=input().split()
dic1={}
dic2={}
for i in range(int(line1[0])):
dic1[int(line1[1+i*2])]=float(line1[2+i*2])
for i in range(int(line2[0])):
dic2[int(line2[1+i*2])]=float(line2[2+i*2])
dic1 = {key:value for key,value in dic1.items() if value!=0}
dic2 = {key:value for key,value in dic2.items() if value!=0}
result = [[x,0] for x in range(2001)]
for x in dic1 :
for y in dic2:
result[x+y][1]+=dic1[x]*dic2[y]
output=str(len([x for x in result if x[1]!=0]))+" "
for x in result[::-1]:
if x[1]!=0:
output = output + str(x[0])+" "+ "{:.1f}" .format(x[1])+" "
print(output[:-1])
1010、Radix (25分)
题目
题目
# N1 N2 tag(标记第几位的进制) radix（标记第几位的进制）
def convert(s,radix):
t=0
point=0
for x in range(len(s)):
t+=int(s[-x-1],36)*(radix**point)
point+=1
return t
def find(target,n):
low=max([int(x,36) for x in n])+1
high=max([low,target])
while(low<=high):
rad=round((low+high)/2)
t=convert(n,rad)
if t==target:
return rad
else:
if t>target:
high=rad-1
else:
low=rad+1
return 'Impossible'
a=input().split()
n1=a[0]
n2=a[1]
tag=int(a[2])
radix=int(a[3])
if tag==1:
t=convert(n1,radix)
print(find(t,n2))
else:
t=convert(n2,radix)
print(find(t,n1))
1011、World Cup Betting (20分)
题目
题目
profit = 1
wtl = ['W','T','L']
out =[]
for i in range(3):
l = list(map(float,input().split()))
out.extend(wtl[l.index(max(l))])
profit *= max(l)
profit = (profit*0.65-1)*2
print(' '.join(out),round(profit,2))
1012、The Best Rank (25分)
题目
题目
# C M E A
class student:
def __init__(self, C, M, E, ID):
self.grade = [round((C+M+E)/3),C,M,E]
self.id = ID
self.rank = [-1, -1, -1, -1]
def main():
line = input().split(" ")
n = int(line[0])
m = int(line[1])
students = {}
for x in range(n):
line = input().split(" ")
ID = line[0]
C = int(line[1])
M = int(line[2])
E = int(line[3])
s = student(C, M, E, ID)
students[ID]=s
for x in range(4):
p = sorted(students.values(), key=lambda i : -i.grade[x])
p[0].rank[x] = 1
for i in range(1, n):
p[i].rank[x] = i + 1
if p[i].grade[x] == p[i-1].grade[x] :
p[i].rank[x] = p[i-1].rank[x]
for x in range(m):
line = input()
try:
unit = students[line]
temp = zip(unit.rank, ['0A','1C','2M','3E'])
temp = sorted(temp)
print(str(min(unit.rank)), temp[0][1][-1])
except:
print('N/A')
if __name__ == "__main__":
main()
1013 Battle Over Cities (25分)
题目
class city:
def __init__(self, name):
self.name = name
self.conn = []
def main():
line = input().split(" ")
n = int(line[0])
m = int(line[1])
k = int(line[2])
cities = {}
for x in range(n):
c = city(x+1)
cities[x+1] = c
for x in range(m):
line = input().split(" ")
come = int(line[0])
to = int(line[1])
cities[come].conn.append(to)
cities[to].conn.append(come)
line = input().split(" ")
conc = [int(x) for x in line]
for x in conc:
a = [0 for x in range(n)]
a[x-1] = 1
repair = -1
while(sum(a) <n):
start = a.index(0)
step = [start+1]
new = [start+1]
temp = []
while(len(new) > 0):
for i in new:
for j in cities[i].conn:
if j not in step and j !=x:
temp.append(j)
step += temp
new = temp
temp = []
repair += 1
for i in step:
a[i-1] = 1
print(repair)
if __name__ == "__main__":
main()
1014 Waiting in Line (30分)
题目
题目
n,m,k,q=[int(x) for x in input().split()]
# n个窗口，每个窗口可容纳m个顾客，一共k个顾客，q个顾客在排
people_time_list=[int(x) for x in input().split()]
line_time_list=[0 for x in range(n)]
dict1={}
list_wait=[]
for j in range(m):
list_kaishi=[]
for i in range(n):
if j*n+i>=k:
pass
else:
line_time_list[i]=line_time_list[i]+people_time_list[j*n+i]
dict1[j*n+i+1]=line_time_list[i]
list_kaishi.append(line_time_list[i])
list_wait.append(list_kaishi)
for i in range(n*m,k):
index=list_wait[0].index(min(list_wait[0]))
for l in range(m-1):
list_wait[l][index]=list_wait[l+1][index]
line_time_list[index] = line_time_list[index] + people_time_list[i]
list_wait[m-1][index]=line_time_list[index]
dict1[i+1] = line_time_list[index]
list1=[int(x) for x in input().split()]
for i in list1:
hour=dict1[i]//60+8
minute=dict1[i]%60
time_now=dict1[i]-people_time_list[i-1]
if time_now>=540:
print("Sorry")
elif dict1[i]>=600:
print("Sorry")
elif hour<10 and minute<10:
print("0"+str(hour)+":"+"0"+str(minute))
elif hour<10:
print("0" + str(hour) + ":" + str(minute))
elif minute<10:
print(str(hour) + ":" + "0" + str(minute))
else:
print(str(hour) + ":"+ str(minute))
1015 Reversible Primes (20分)
题目
"""
输入整数和进制
如果整数是素数，转换为指定的进制后反转，再转为10进制后是否是素数
"""
import math
def is_prime(num):
if num<=1:
return 0
flag=1
for x in range(2,round(math.sqrt(num))+1):
if num%x==0:
flag=0
return flag
return flag
def reverse(num,radix):
result=''
while (num!=0):
temp=num%radix
result=str(temp)+result
num=num//radix
return result
while (True):
line=input().split()
if len(line)<2:
break
num=int(line[0])
radix=int(line[1])
if is_prime(num)==1:
rever=reverse(num,radix)
rever=rever[::-1]
rever=int(rever,radix)
if is_prime(rever)==1:
print("Yes")
else:
print("No")
else:
print("No")
1016 Phone Bills (25分)
题目
题目
# 假设开始时间为A 结束时间为B
# 从00:00:00 到A 的话费T1，从00:00:00 到B 的话费T2
# 话费 T2-T1
line = input().split(" ")
rate = [int(x) for x in line]
oneday = sum([x for x in rate])*60
num = int(input())
record = {}
for x in range(num):
line = input().split(" ")
if line[0] in record:
record[line[0]] .append(line[1:])
else:
record[line[0]] = [line[1:]]
name = sorted(record.keys())
for x in name:
unit = sorted(record[x])
bill = []
stack = []
for i in unit:
if len(stack) == 0:
if i[1] =='on-line':
stack.append(i)
else:
if i[1] == stack[0][1]:
stack[0] = i
else:
bill.append([stack[0],i])
stack = []
if len(bill) >0 :
count = 0
result = '{} {}\n'.format(x, bill[0][0][0][:2])
for i in bill:
start = i[0][0]
end = i[1][0]
result = result + start[3:] + ' '+ end[3:] + ' '
m1, m2=0, 0
day1, day2= int(start[3:5]), int(end[3:5])
hour1, hour2 = int(start[6:8]), int(end[6:8])
minute1, minute2 = int(start[9:11]), int(end[9:11])
m1 = oneday * day1 + sum(rate[:hour1])*60 + rate[hour1]*int(minute1)
m2 = oneday * day2 + sum(rate[:hour2])*60 + rate[hour2]*int(minute2)
time = (day2 - day1)*24*60 + (hour2-hour1)*60 + minute2 - minute1
result = result + str(time)+' '
m = m2 - m1
result = result+'$'+'{:.2f}'.format(m/100)+'\n'
count += m
result = result+'Total amount: ${:.2f}'.format(count/100)
print(result)
1017 Queueing at Bank (25分)
题目
# 优先队列
N,K=[int(i) for i in input().split()]
cus = {} #用来存放顾客的到达时间，和需要处理的时间
window = [3600 * 8] * K #将所有窗口的开放时间都设为8点
for _ in range(N):
A=input().split()
hh,mm,ss=[int(i) for i in A[0].split(":")]
wait=int(A[1])
if hh*3600+mm*60+ss<17*3600+1: #过滤掉晚上5点以后的顾客
cus[hh*3600+mm*60+ss]=wait*60
cus=dict(sorted(cus.items(),key=lambda x:x[0])) #按照到达时间把顾客排好队
total=0
for j in cus:
window=sorted(window) #不断的更新窗口的等待时间，将短的等待时间放在前面
if window[0]>j: #判断窗口是否空闲
total+=window[0]-j #将顾客等待时间存放入
window[0]+=cus[j] #更新窗口下次开放的时间
else:
window[0]=cus[j]+j
count=len(cus)
if count>0:
print("{:.1f}".format(total/60/count))
else:
print("0.0")
1018 Public Bike Management (30分)
题目
题目
cmax,n,sp,m = [int(x) for x in input().split() ]
C = [0] + [ int(x) for x in input().split() ]
Neib = [ {} for i in range(n+1) ]
for i in range(m):
si,sj,t = [ int(x) for x in input().split() ]
Neib[si][sj] = t
Neib[sj][si] = t
minpath = []
minrequire = cmax+1
minextra = cmax+1
mindis = -1
vis = [0] * (n+1)
def dfs (Neib,path,dis,require,extra,st):
global minrequire
global minextra
global mindis
global minpath
#print(path,dis,require,extra,st)
vis[st] = 1
if st == sp:
if mindis == -1 or dis < mindis \
or (dis == mindis and (require < minrequire or \
require == minrequire and extra < minextra )):
minextra = extra
minrequire = require
mindis = dis
minpath = path
vis[st] = 0
return
for i,t in Neib[st].items():
if not vis[i]:
#deal with need and take
need,take = require,extra
# get i's Current state
diff = C[i] - cmax // 2
# if i's state less than perfection
if diff < 0 :
# if take can feed i's need , decrease take
if take >= (-diff) :
take += diff
# if can't , let take be 0, increase need
else:
need += (-diff) - take
take = 0
# if i's state more than perfection , just increase take
# need can't be feed by i's state
# the bike needed is used in adjusting the state before approching i's state
# so we can just take more, can't need less
# 2 test cases here.
elif diff > 0:
take += diff
#dfs i
dfs(Neib,path+[i],dis + t,need,take,i)
vis[st] = 0
dfs(Neib,[0],0,0,0,0)
#print(minpath,minrequire,minextra,mindis)
strpath = '->'.join([str(x) for x in minpath])
print(minrequire,strpath,minextra)
1019 General Palindromic Number (20分)
题目
题目
def transform(a,b):
# a 整数 b 进制
if a==0:
return '0'
result = []
while(a != 0):
result.insert(0, str(a % b))
a = a//b
return result
a,b=map(int, input().split())
num = transform(a,b)
result = ''
if len(num) == 1:
result = "Yes" +"\n" + num[0]
else:
for x in range(len(num)//2):
if num[x] != num[len(num) - 1-x]:
result = "No"+"\n"+" ".join(num)
break
if result == '':
result = "Yes" + "\n" +" ".join(num)
print(result)
1020 Tree Traversals (25分)
题目
def trav(poster, inorder):
global result, temp
root = poster[-1]
result.append(root)
index = inorder.index(root)
inleft,inright = inorder[:index], inorder[index+1:]
posleft, posright = poster[:len(inleft)], poster[len(inleft):len(inleft)+len(inright)]
if len(inleft) >0:
temp.append([posleft,inleft])
if len(inright) >0:
temp.append([posright,inright])
if __name__ =="__main__":
num = int(input())
line = input().split(" ")
poster = [int(x) for x in line]
line = input().split(" ")
inorder = [int(x) for x in line]
result = []
temp = []
part = [[poster,inorder]]
while(True):
for x in part:
trav(x[0], x[1])
if len(temp)==0:
break
else:
part = temp
temp = []
result = [str(x) for x in result]
print(' '.join(result))
1021 Deepest Root (25分)
题目
题目
def bfs(graph,start):
global n
count = 0
visted = [0 for x in range(n)]
for x in range(n):
if x+1 not in graph:
visted[x] = 1
count += 1
step = [start]
while(count == 0):
temp = []
for x in step:
visted[x-1] = 1
for j in graph[x]:
if visted[j-1] == 0:
temp.append(j)
if len(temp) == 0:
if 0 not in visted:
return True, step
else:
break
step = temp
while(0 in visted):
count += 1
start = [x for x in graph if visted[x-1] ==0][0]
step = [start]
while(len(step)>0):
temp = []
for x in step:
visted[x-1] = 1
for j in graph[x]:
if visted[j-1] == 0:
temp.append(j)
if len(temp)==0:
if 0 not in visted:
return False, count
step = temp
if __name__ == "__main__":
n = int(input())
if n==1:
print(1)
else:
graph = {}
for x in range(n-1):
line = input().split(" ")
start, to = int(line[0]), int(line[1])
try:
graph[start].append(to)
except:
graph[start] = [to]
try:
graph[to].append(start)
except:
graph[to] = [start]
back = bfs(graph, start)
if back[0]:
another = bfs(graph, back[1][0])
result = sorted(set(back[1] + another[1]))
for x in result:
print(x)
else:
print('Error: {} components'.format(back[1]))
