I solved it while thinking that I remember that the C problem was difficult because I had solved it before. The C problem has loose restrictions, so if you notice that you can turn the triple loop, you can afford it.
There are not many patterns that distinguish cases by the value of the first input, so be careful.
answerA.py
x=int(input())
if x==1:
print("Hello World")
else:
a,b=int(input()),int(input())
print(a+b)
Find the cost of the first cost route within time T. However, if there is no route within time T, TLE must be output, so it is necessary to specify a value of 1001 or more as inf.
answerB.py
n,t=map(int,input().split())
ct=[list(map(int,input().split())) for i in range(n)]
c=10000000000000000
for i in range(n):
if ct[i][1]<=t:
c=min(c,ct[i][0])
print(c if c!=10000000000000000 else "TLE")
First of all, even if I think about all the center coordinates, there is only $ 101 \ times 101
answerC.py
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
xyh.sort(key=lambda x:x[2],reverse=True)
for X in range(0,101):
for Y in range(0,101):
f=True
H=xyh[0][2]+abs(xyh[0][0]-X)+abs(xyh[0][1]-Y)
for i in range(1,n):
x,y,h=xyh[i]
if h==0:
if H-abs(x-X)-abs(y-Y)>0:
f=False
break
else:
if H-abs(x-X)-abs(y-Y)!=h:
f=False
break
if f:
print(X,Y,H)
break
answerC_better.py
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
xyh.sort(key=lambda x:x[2],reverse=True)
for X in range(0,101):
for Y in range(0,101):
H=xyh[0][2]+abs(xyh[0][0]-X)+abs(xyh[0][1]-Y)
for i in range(1,n):
x,y,h=xyh[i]
if h!=max(H-abs(x-X)-abs(y-Y),0):
break
else:
print(X,Y,H)
break
After a little experiment and observing the sample, $ a_1, a_2,…, a_N $ are all multiples of X when the greatest common divisor is set to X. Therefore, we can see that M is a multiple of X. Therefore, X is a divisor of M. Furthermore, since $ a_1, a_2,…, a_N $ are all multiples of X and their sum is M, it must be $ N \ leqq M / X $. Therefore, consider the divisors of M in order, and when you divide M by the divisors, the quotient is N or more, and the largest one should be found as the answer. Also, on the contrary, I thought about the divisors that would be n or more and asked for the largest of the divisors divided by N (also divisors) as the answer. Implementing this looks like this: Also, make_divisors is a function that enumerates divisors of n.
answerD.py
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
divisors.sort()
return divisors
n,m=map(int,input().split())
ans=1
for i in make_divisors(m):
if i>=n:
ans=max(ans,m//i)
print(ans)
Recommended Posts