AtCoder Beginner Contest 112 Review of past questions

Time required

スクリーンショット 2020-04-18 13.48.33.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions