[PYTHON] AtCoder Beginner Contest 112 Review of past questions

Time required

Impressions

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.

Problem A

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)

B problem

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

C problem

First of all, even if I think about all the center coordinates, there is only $ 101 \ times 101 . Therefore, I thought that it would be better to fix the parameters of the center coordinates and make only the parameters of the height **.) here,**The center coordinates and height of the pyramid can be specified in exactly one**So fixed center coordinates(X,Y)If is the correct answer, the information is**All accurate information**And if the fixed center coordinates are not the correct answer**Some information is incorrect**ことになります。here,情報がAll accurate informationとなるということは、高度が1でないような情報から高さHを定めてそれ以外の情報について**h_i=max(H-|x_i-X|-|y_i-Y|,0)$Just try to see if**is. Also, since the height H is determined from the information whose altitude is not 1, the descending sort is performed first in order to set the altitude of the first element to 1.

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

D problem

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)