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])# 構建指數(shù)和冪和對應字典
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) #提取指數(shù)
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] #指數(shù)一致時系數(shù)相加
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
# 第一行：城市數(shù)、道路輸、目前所在城市、需急救城市、
# 第二行：每個城市的急救隊數(shù)量
# C1、C2、L 兩個城市之間的路長
# 尋找最短路徑
#點的屬性<城市編號、救急隊數(shù)量>
# 邊的屬性<<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分)
題目
# 沒通過
# 給定一棵樹，求每一層的葉子節(jié)點數(shù)
# 第一行n（節(jié)點個數(shù)）,m（無葉子節(jié)點的節(jié)點個數(shù)）
# 第二行 id無葉子節(jié)點，k葉子節(jié)點個數(shù)，id[1].....id[k]
tmap={} # 記錄非葉子節(jié)點
record=[0 for i in range(101)] #記錄數(shù)的深度
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 節(jié)點個數(shù)，m無葉子節(jié)點的節(jié)點個數(shù)
for i in range(m):
line=input().split() #讀取數(shù)據(jù)
rid=int(line[0]) #
k=int(line(1)) # 葉子節(jié)點個數(shù)
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分)
題目
"""
輸入整數(shù)和進制
如果整數(shù)是素數(shù)，轉換為指定的進制后反轉，再轉為10進制后是否是素數(shù)
"""
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分)
題目
# 優(yōu)先隊列
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 整數(shù) 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]))
