[PYTHON] AtCoder Beginner Contest 112 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Ich löste es, während ich dachte, dass ich mich daran erinnere, dass das C-Problem schwierig war, weil ich es zuvor gelöst hatte. Das C-Problem hat lose Einschränkungen. Wenn Sie also feststellen, dass Sie die Dreifachschleife drehen können, können Sie es sich leisten.

Problem A

Es gibt nicht viele Muster, die Fälle anhand des Werts der ersten Eingabe unterscheiden. Seien Sie also vorsichtig.

answerA.py

x=int(input())

if x==1:
    print("Hello World")
else:
    a,b=int(input()),int(input())
    print(a+b)

B-Problem

Finden Sie die Kosten der ersten Kostenroute innerhalb der Zeit T. Wenn jedoch innerhalb der Zeit T keine Route vorhanden ist, muss TLE ausgegeben werden, sodass ein Wert von 1001 oder mehr als inf angegeben werden muss.

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

Selbst wenn ich an alle Mittelkoordinaten denke, gibt es zunächst nur $ 101 \ mal 101 . Deshalb habe ich beschlossen, die Mittelkoordinaten einmal zu bestimmen (hier gibt es insgesamt drei Parameter für die Mittelkoordinaten und die Höhe). Daher dachte ich, dass es besser wäre, die Parameter der Mittelkoordinaten festzulegen und nur die Parameter der Höhe zu machen **.). Hier,**Die Mittelkoordinaten und die Höhe der Pyramide können in genau einer angegeben werden**Also feste Mittelkoordinaten(X,Y)Wenn die richtige Antwort ist, sind die Informationen**Alle genauen Informationen**Und wenn die festen Mittelkoordinaten nicht die richtige Antwort sind**Einige Informationen sind falsch**ことになります。Hier,情報がAlle genauen Informationenとなるということは、高度が1でないような情報から高さHを定めてそれ以外の情報について**h_i=max(H-|x_i-X|-|y_i-Y|,0)$Versuchen Sie einfach zu sehen, ob**ist. Da die Höhe H aus den Informationen bestimmt wird, deren Höhe nicht 1 ist, wird die absteigende Reihenfolge zuerst sortiert, um die Höhe des ersten Elements auf 1 zu setzen.

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

Nach einem kleinen Experiment und Beobachtung der Stichprobe sind $ a_1, a_2,…, a_N $ alle Vielfache von X, wenn die maximale Verpflichtung auf X gesetzt ist. Daher können wir sehen, dass M ein Vielfaches von X ist. Daher ist X ein Bruchteil von M. Da außerdem $ a_1, a_2,…, a_N $ alle Vielfache von X sind und ihre Summe M ist, muss es $ N \ leqq M / X $ sein. Wenn Sie also die Brüche von M in der richtigen Reihenfolge betrachten und M durch diesen Bruch dividieren, können Sie den größten finden, dessen Quotient N oder mehr als Antwort ist. Im Gegenteil, ich dachte über die Anzahl der Reziprozitäten nach, die n oder mehr sein würden, und dividierte durch N durch diese Zahl (auch über die Reziprozität), und fragte nach dem größten als Antwort. Die Implementierung sieht folgendermaßen aus: Außerdem ist make_divisors eine Funktion, die die Brüche von n auflistet.

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)