Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (005 --- 009 Toutes les recherches: Toutes les énumérations pour réduire le nombre de rues en concevant)

1. Objet

Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.

Cet article s'intitule "005 --009 All Search: All Enumeration to Reduce the Number of Streets by Ingenuity".

2. Résumé

[006. Sumitomo Mitsui Trust Bank Programming Contest 2019 D - Lucky PIN] a été un peu difficile. 007 et 009 peuvent être difficiles si vous n'avez pas de vecteur.

3. Histoire principale

005 --009 Toutes les recherches: toutes les dénombrements pour réduire le nombre de rues

5. AtCoder Beginner Contest 095 C - Half and Half

Répondre

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

answer_1 = A * X + B * Y #Lors de tout achat en A et B
answer_2 = C * 2 * max(X, Y) #Si vous achetez tout en C

# answer_3:Une première,Lors de l'achat de B, puis en complétant le reste avec C
# answer_4:Achetez d'abord C, puis le reste A,En complétant avec 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)

Pour acheter au prix le moins cher, il suffit d'essayer les 4 façons suivantes.

1. Lors de tout achat en A et B
2. Si vous achetez tout en C
3. Lors de l'achat d'une petite quantité de A et B d'abord, puis en complétant le reste avec C
4. Lors de l'achat d'une petite quantité avec C d'abord, puis en complétant le reste avec A et B

La réponse est de trouver la valeur minimale après avoir calculé ces quatre montants.

006. Concours de programmation Sumitomo Mitsui Trust Bank 2019 D - PIN chanceux

Répondre

import itertools

def find_index(l, x): #Dans l'index de fonction intégré, s'il n'est pas trouvé, une erreur se produira.-Fixé pour retourner 1
    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): #Autoriser la duplication 1~Disposer trois nombres de 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)

Cette réponse n'est pas bonne.

Si vous recherchez principalement la chaîne de caractères S, la longueur maximale de S est de 30000, et si vous essayez toutes les méthodes pour en sélectionner trois à partir d'ici, l'ordre sera d'environ 10 ** 12, donc je vais penser à une méthode différente.

Si vous réfléchissez à la façon d'autoriser les nombres en double de 0 à 9 et de sélectionner 3 au lieu de la chaîne de caractères S comme corps principal, ce sera de l'ordre de 10 ** 3, donc je pense que je peux y aller si je pense à cela comme au corps principal.

La politique est

1. Énumérer les nombres à 3 chiffres en utilisant 0-9 dans itertools.product
2. Trouvez le numéro d'index où le numéro du chiffre de gauche apparaît en premier dans la chaîne S
3. Vérifiez le numéro d'index où le numéro du milieu apparaît pour la première fois dans la chaîne de caractères S après le numéro d'index trouvé ci-dessus.
4. Vérifiez le numéro d'index où le numéro du chiffre de droite apparaît pour la première fois dans la chaîne de caractères S après le numéro d'index trouvé ci-dessus.
5. Si le numéro d'index est introuvable car il est compris entre 2 et 3, `` `break```

est.

007. Sélection finale JOI 2007 3-The Oldest Ruins

Répondre

import itertools

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

#Pensez à un carré ABCD
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)

Si 2 points sont confirmés à partir des coordonnées données, 4 points et la zone de création du carré seront déterminés. Par conséquent, en tant que politique, nous allons essayer toutes les méthodes de sélection de deux points à partir des coordonnées et juger si un carré peut être créé ou non.

1. Indiquez comment sélectionner 2 points à partir des coordonnées avec itertools (appelons-les A et B)
2. Trouvez les deux points C et D restants lors de la création d'un carré à partir de deux points
3. Déterminez si C, D sont donnés et inclus dans l'ensemble de coordonnées
4. Si inclus, recherchez la zone et notez la valeur maximale

est. Pour déterminer si les points C et D sont inclus dans un ensemble donné de coordonnées, la liste en points aboutit généralement à TLE```, donc ` Doit être `` dots_set = set (dots) ''.

8. Square869120Contest #6 B - AtCoder Markets

Répondre

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)

Il semble préférable de placer l'entrée et la sortie soit dans l'Ai soit dans le Bi (il y a probablement d'autres meilleurs endroits ...). Essayez donc tous les A et B pour trouver celui qui vous donnera le moins de temps.

009. JOI 2008 Qualifying 4-Search for Constellation

Répondre

m = int(input()) #m est le nombre d'étoiles dans la constellation que vous recherchez
target = [tuple(map(int, input().split())) for _ in range(m)] #Coordonnées de la constellation que vous souhaitez trouver
n = int(input()) #n est le nombre d'étoiles dans l'image
stars = [tuple(map(int, input().split())) for _ in range(n)] #Coordonnées des étoiles sur la photo
set_stars = set(stars)

target_vector = [] #Maintenir la position relative en tant que vecteur
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))

#Ajoutez des vecteurs pour toutes les étoiles.
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: #S'il y a des étoiles après tout ajout de vecteur, les coordonnées de départ sont la source de la réponse
            target_y, target_x = y, x 
            break
#La réponse est les coordonnées relatives aux premières coordonnées de la cible
answer_y = target_y - target[0][0]
answer_x = target_x - target[0][1]

print(answer_y, answer_x)

J'ai fait les indices y et x à l'inverse de la définition du problème, mais il y a une réponse.

La politique est

1. Maintenez la forme de constellation souhaitée en tant que vecteur target_vector``` (sens antihoraire)
2. Déplacez toutes les étoiles de la photo en fonction du vecteur et vérifiez s'il y a des étoiles dans les coordonnées déplacées
3. S'il n'y a pas d'étoile, break, s'il y en a, comptez le nombre de fois que le vecteur a été utilisé, et s'il peut être utilisé` `` m-1 fois, la reproduction de la constellation est terminée.
4. Si vous pouvez reproduire la constellation, prenez la différence entre la coordonnée de départ et la première coordonnée de la constellation cible, et c'est la réponse.

est.