Lösen Sie mit Python [100 ausgewählte Fragen aus der Vergangenheit, die Anfänger und Fortgeschrittene lösen sollten] (005 --- 009 Alle Suche: Alle Aufzählungen, um die Anzahl der Straßen durch Entwickeln zu reduzieren)

1. Zweck

Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.

Dieser Artikel ist "005 - 009 Alle Suche: Alle Aufzählung, um die Anzahl der Straßen durch Einfallsreichtum zu reduzieren".

2. Zusammenfassung

[006. Sumitomo Mitsui Trust Bank Programmierwettbewerb 2019 D - GlückspIN] war ein wenig schwierig. 007 und 009 können schwierig sein, wenn Sie keinen Vektor haben.

3. Hauptgeschichte

005 --009 Alle suchen: Alle Aufzählungen, um die Anzahl der Straßen durch Ausarbeiten zu reduzieren

5. AtCoder Beginner Contest 095 C - Half and Half

Antworten

A, B, C, X, Y = map(int, input().split())

answer_1 = A * X + B * Y #Beim Kauf alles bei A und B.
answer_2 = C * 2 * max(X, Y) #Wenn Sie alles in C kaufen

# answer_3:Eine Premiere,Beim Kauf von B und dann Ergänzung des Restes mit C.
# answer_4:Kaufen Sie zuerst C und dann den Rest A.,Bei der Ergänzung mit B.
if X > Y:
    answer_3 = A * Y + B * Y + C * (X - Y) * 2
    answer_4 = A * (X - Y) + C * Y * 2
else:
    answer_3 = A * X + B * X + C * (Y - X) * 2
    answer_4 = B * (Y - X) + C * X * 2

answer = min(answer_1, answer_2, answer_3, answer_4)
print(answer)

Um zum günstigsten Preis zu kaufen, reicht es aus, die folgenden 4 Möglichkeiten auszuprobieren.

1. Beim Kauf alles bei A und B.
2. Wenn Sie alles in C kaufen
3. Wenn Sie zuerst bis zu einer kleinen Menge A und B kaufen und dann den Rest mit C ergänzen
4. Wenn Sie zuerst eine kleine Menge mit C kaufen und dann den Rest mit A und B ergänzen

Die Antwort besteht darin, den Mindestwert nach Berechnung dieser vier Beträge zu ermitteln.

006. Programmierwettbewerb der Sumitomo Mitsui Trust Bank 2019 D - GlückspIN

Antworten

import itertools

def find_index(l, x): #Wenn der integrierte Funktionsindex nicht gefunden wird, tritt ein Fehler auf.-Behoben, 1 zurückzugeben
    if x in l:
        return l.index(x)
    else:
        return -1


if __name__ == "__main__":
        
    N = int(input())
    S = [int(c) for c in input()]
    table = list(range(10))

    count = 0
    for p in itertools.product(table, repeat=3): #Duplizierung zulassen 1~Ordnen Sie drei Zahlen von 9
        target = list(p)

        s1_index = find_index(S, target[0])
        if s1_index == -1:
            continue
        s1 = S[s1_index+1:]

        s2_index = find_index(s1, target[1])
        if s2_index == -1:
            continue
        s2 = s1[s2_index+1:]
        
        s3_index = find_index(s2, target[2])
        if s3_index == -1:
            continue
        
        count += 1

    print(count)

Diese Antwort ist nicht gut.

Wenn Sie hauptsächlich nach der Zeichenfolge S suchen, beträgt die maximale Länge von S 30.000, und wenn Sie alle Methoden ausprobieren, um drei von hier auszuwählen, beträgt die Reihenfolge etwa 10 ** 12, sodass ich mir eine andere Methode überlegen werde.

Wenn Sie darüber nachdenken, wie Sie doppelte Zahlen von 0 bis 9 zulassen und drei anstelle der Zeichenfolge S als Hauptteil auswählen können, liegt diese in der Größenordnung von 10 ** 3, und ich denke, wenn Sie dies als Hauptteil betrachten, können Sie gehen.

Die Politik ist

1. Zählen Sie dreistellige Zahlen mit 0-9 in `` `itertools.product``` auf
2. Finden Sie die Indexnummer heraus, bei der die Nummer in der linken Ziffer zuerst in der Zeichenfolge S erscheint
3. Überprüfen Sie die Indexnummer, bei der die mittlere Ziffer zum ersten Mal in der Zeichenfolge S nach der oben angegebenen Indexnummer erscheint.
4. Überprüfen Sie die Indexnummer, bei der die Nummer in der rechten Ziffer zum ersten Mal in der Zeichenfolge S nach der oben angegebenen Indexnummer erscheint.
5. Wenn die Indexnummer nicht gefunden wird, weil sie 2 bis 3 ist, wird `` `break``` jeweils

ist.

007. JOI 2007 Final Selection 3 - Die ältesten Ruinen

Antworten

import itertools

n = int(input())
dots = [tuple(map(int, input().split())) for _ in range(n) ]
dots_set = set(dots)

#Denken Sie an ein ABCD-Quadrat
max_area = 0
for A, B in itertools.combinations(dots, 2):
    Ax, Ay = A
    Bx, By = B

    Cx, Cy = Bx - (By - Ay), By + (Bx - Ax) 
    Dx, Dy = Ax - (By - Ay), Ay + (Bx - Ax)
    
    if (Cx, Cy) in dots_set and (Dx, Dy) in dots_set:
        area = (Ax - Bx) ** 2 + (Ay - By) ** 2
        max_area = max(max_area, area)

print(max_area)

Wenn 2 Punkte aus den angegebenen Koordinaten bestätigt werden, werden 4 Punkte und die Fläche zum Erstellen des Quadrats bestimmt. Daher werden wir als Richtlinie alle Methoden zur Auswahl von zwei Punkten aus den Koordinaten ausprobieren und beurteilen, ob ein Quadrat erstellt werden kann oder nicht.

1. Listen Sie auf, wie Sie mit `` `itertools``` 2 Punkte aus Koordinaten auswählen (nennen wir es A, B).
2. Suchen Sie die verbleibenden zwei Punkte C und D, wenn Sie aus zwei Punkten ein Quadrat erstellen
3. Bestimmen Sie, ob C, D angegeben und im Koordinatensatz enthalten sind
4. Suchen Sie den Bereich und notieren Sie den Maximalwert, falls vorhanden

ist. Wenn bei der Bestimmung, ob die Punkte C und D in einem gegebenen Satz von Koordinaten enthalten sind, die Liste "in Punkten" zur Bestimmung verwendet wird, lautet sie "TLE", also " Muss dots_set = set (dots) `sein.

8. Square869120Contest #6 B - AtCoder Markets

Antworten

N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

min_time = float('inf')
for a in A:
    for b in B:
        total_time = 0
        for i in range(N):
            total_time += abs(a - A[i]) + abs(A[i] - B[i]) + abs(b - B[i])
        
        min_time = min(min_time, total_time)

print(min_time)

Es scheint am besten, den Ein- und Ausgang entweder im angegebenen Ai oder Bi zu platzieren (wahrscheinlich gibt es andere beste Orte ...). Versuchen Sie also alle A und B, um die zu finden, die Ihnen am wenigsten Zeit lässt.

009. JOI 2008 Qualifying 4-Search for Constellation

Antworten

m = int(input()) #m ist die Anzahl der Sterne in der Konstellation, nach der Sie suchen
target = [tuple(map(int, input().split())) for _ in range(m)] #Koordinaten der Konstellation, die Sie finden möchten
n = int(input()) #n ist die Anzahl der Sterne im Bild
stars = [tuple(map(int, input().split())) for _ in range(n)] #Koordinaten der Sterne auf dem Foto
set_stars = set(stars)

target_vector = [] #Halten Sie die relative Position als Vektor
for i in range(m-1):
    y1, x1 = target[i]
    y2, x2 = target[i+1]
    vector_y, vector_x = y2 - y1, x2 - x1
    target_vector.append((vector_y, vector_x))

#Fügen Sie Vektoren für alle Sterne hinzu.
target_y, target_x = 0, 0 
for star in stars:
    y, x = star
    new_y, new_x = y, x
    count = 0
    for vector in target_vector:
        y_vector, x_vector = vector

        new_y += y_vector
        new_x += x_vector

        if (new_y, new_x) not in set_stars:
            break

        count += 1
        if count == m - 1: #Wenn nach allen Vektoradditionen Sterne vorhanden sind, sind die Startkoordinaten die Quelle der Antwort
            target_y, target_x = y, x 
            break
#Die Antwort sind die relativen Koordinaten zu den ersten Koordinaten des Ziels
answer_y = target_y - target[0][0]
answer_x = target_x - target[0][1]

print(answer_y, answer_x)

Ich habe die Indizes y und x in umgekehrter Reihenfolge der Problemeinstellung erstellt, aber es gibt eine Antwort.

Die Politik ist

1. Halten Sie die gewünschte Konstellationsform als Vektor `` `target_vector``` (gegen den Uhrzeigersinn)
2. Verschieben Sie alle Sterne auf dem Foto entsprechend dem Vektor und prüfen Sie, ob die verschobenen Koordinaten Sterne enthalten
3. Wenn es keinen Stern gibt, `` break```, falls vorhanden, zählen Sie, wie oft der Vektor verwendet wurde, und wenn er `m-1```-mal verwendet werden kann, ist die Reproduktion der Konstellation abgeschlossen.
4. Wenn Sie die Konstellation reproduzieren können, nehmen Sie die Differenz zwischen der Startkoordinate und der ersten Koordinate der Zielkonstellation, und das ist die Antwort.

ist.