[PYTHON] Bilan 2019 du concours de programmation Sumitomo Mitsui Trust Bank

Il a été assez tard pour les réviser, mais je les ai tous résolus, alors j'aimerais écrire un article. J'ai fait quatre complets, mais mon impression était que je voulais en terminer cinq parce que EF (surtout F) était une période facile.

Problème A

answerA.py

m1,d1=map(int,input().split())
m2,d2=map(int,input().split())
if m1==m2:
    print(0)
else:
    print(1)

Il détermine simplement si m1 et m2 sont différents.

Problème B

answerB.py

x=[]
for i in range(1,50001):
    x.append(int(i*1.08))

n=int(input())
for i in range(50000):
    if n==x[i]:
        print(i+1)
        break
else:
    print(":(")

L'énoncé du problème était un peu long, j'ai donc pris un peu trop de temps. Regroupez tous les nombres possibles dans le premier tableau x et modifiez la sortie en fonction de l'existence ou non d'un nombre correspondant. Python est pratique car il est facile d'écrire en utilisant l'instruction else lors de la modification de la sortie en fonction de l'interruption ou non.

Problème C

answerC.py

x=int(input())
y=x//100
z=x%100
if z<=y*5:
    print(1)
else:
    print(0)

Puisqu'il est sous la forme de 100 + k (un entier de 0 <= k <= 5), vous pouvez voir que vous pouvez acheter jusqu'à x // 100 articles. (Il est nécessaire de le maximiser car nous voulons maximiser la plage de l'expression dans la phrase suivante.) À ce stade, si x% 100 est compris entre 0 ~ (x // 100) * 5, ce sera exactement X yen. Comme cela peut être fait, il sera affiché selon que cela peut être fait ou non. (J'ai utilisé mon esprit plus que le problème C habituel, mais j'ai été surpris qu'un bon nombre de personnes soit passé.)

Problème D

answerD.py

n=int(input())
s=[int(i) for i in input()]

def my_index(l,x,ind):
    '''
    l-Objet itérable
    x-Valeur que vous souhaitez trouver
    ind-Index que vous souhaitez rechercher
Valeur de retour-Indexer s'il existe, s'il n'existe pas-1
    '''
    global n
    if ind==n:
        return -1
    for i in range(ind,n):
        if l[i]==x:
            return i
    else:
        return -1

c=0
for i in range(10):
    x1=my_index(s,i,0)
    if x1!=-1:
        for j in range(10):
            x2=my_index(s,j,x1+1)
            if x2!=-1:
                for k in range(10):
                    if my_index(s,k,x2+1)!=-1:
                        c+=1
print(c)

J'étais confus par N, mais à la fin, il n'y a que 10 * 10 * 10 3 chiffres, donc je peux voir que tout ce que j'ai à faire est de les vérifier tous. Cependant, j'ai créé moi-même la fonction my_index car l'utilisation de la fonction d'index de Python générera une erreur si l'élément n'existe pas dans cet objet. Une fois que vous savez cela, vous pouvez savoir s'il y a 10 * 10 * 10 mots de passe différents dans l'ordre de l'avant.

Post-scriptum (12/11)

Si vous traitez s comme une chaîne de caractères sans la lister, vous pouvez la remplacer par la fonction find sans préparer la fonction my_index.

E problème

answerE.py

#En comptant de l'avant, ce qui se passe est uniquement déterminé
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    k=my_index(b[-1],a[i])
    if k==-1:
        print(0)
        break
    b.append([b[-1][j]+1 if j==k else b[-1][j] for j in range(3)])
else:
    x=1
    for i in range(n):
        x=x*b[i].count(a[i])%1000000007
    print(x)

L'impression que E était la plus difficile. (Je l'ai résolu après avoir vu la réponse.) Si le nombre de personnes portant des chapeaux de chaque couleur est défini comme ai, bi, ci et xi, yi, zi sont définis par ordre décroissant du nombre de personnes, les remarques du premier à ième personnes sont utilisées comme base. Cela permet de déterminer de manière unique les valeurs de xi, yi et zi. (Pour plus de détails, voir Answer. Vous pouvez le découvrir en bougeant la main.) La séquence b contient les combinaisons de xi, yi et zi jusqu'à la i-ème personne (à la 1ère origine), et en déplaçant i de 0 à n-1, la combinaison est obtenue pour chaque i. Ici, si le nombre de personnes (a [i]) mentionné dans la i + 1e remarque existe dans b [i], le nombre de i + 1e remarques et le nombre de chapeaux de chaque couleur dans la ième personne sont Bien qu'il n'y ait pas de contradiction, l'élément du nombre correspondant de personnes est incrémenté de +1 et peut être b [i + 1]. Cependant, il y a un cas (k = -1) où le nombre de chapeaux de chaque couleur jusqu'à la i-1ère personne est incompatible avec la remarque de la i-ième personne, donc dans ce cas 0 est sorti et une pause est effectuée. Jusqu'à ce point, le nombre de chapeaux de couleur pour chaque i peut être calculé, mais s'il y a plusieurs a [i] dans b [i], il y a plusieurs couleurs mentionnées dans l'instruction i + 1. La réponse peut être trouvée en multipliant les possibilités par a [i] dans chaque b [i].

Problème F

answerF.py

import math
t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
#Vitesse relative
c1,c2=a1-b1,a2-b2
#Distance loin
d1,d2=abs(c1*t1),-abs(c2*t2)

if (c1>0 and c2>0) or (c1<0 and c2<0) or d1+d2>0:
    print(0)
elif d1+d2==0:
    print("infinity")
else:
    x=d1//(-(d1+d2))
    y=d1%(-(d1+d2))
    if y==0:
        print(2*x)
    else:
        print(2*x+1)

Je n'ai vu aucun problème pendant le concours, mais j'ai été très déçu car c'était étonnamment facile à résoudre après le concours. Puisque nous nous rencontrerons, nous devrions considérer la position relative, et d'abord trouver la vitesse relative (c1 et c2). De là, nous allons bifurquer les conditions.

Premièrement, en considérant des modèles qui ne sont pas des temps finis, il y a les quatre modèles ci-dessus. Lorsque c1 et c2 sont tous les deux positifs (motif ①) et c1 et c2 sont tous deux négatifs (motif ②), ils sont toujours séparés et ne se rencontrent pas. Même si le déplacement de position relative au temps T1 est plus grand que le déplacement de position relative au temps T2 (motif ③), ils seront toujours séparés l'un de l'autre, de sorte qu'ils ne se rencontreront pas. De plus, si le déplacement de position relative en temps T1 est le même que le déplacement de position relative en temps T2 (motif pattern), la position relative ne change pas en un cycle de T1 et T2, donc elle continue indéfiniment.

Enfin, considérons le cas d'une rencontre un nombre fini de fois. À ce stade, la distance entre T1 et T2 est différente pour le positif et le négatif, alors prenez la valeur absolue et faites en sorte qu'il soit facile de la considérer comme positive pour T1 et négative pour T2. (Le reste de l'explication sera manuscrit.) Comme mentionné ci-dessus, j'ai pu compter le nombre de rencontres dans tous les cas.

Résumé

Pour le moment, jetons un œil au dernier problème. Jugez fermement si cela peut être résolu ou non. (Parfois je le laisse tomber sans voir un problème qui semble être résolu, et parfois j'essaie de résoudre un problème apparemment difficile.) C'est la même chose que les mathématiques pour passer un examen, réfléchir et expérimenter même si vous êtes impatient.