[PYTHON] AtCoder Beginner Contest 081 Revue des questions précédentes

Temps requis

Impressions

J'ai résolu le problème D correctement deux fois de suite. J'ai pu le résoudre en y réfléchissant attentivement, mais avant de le savoir, je le résolvais en faisant du FX ... J'ai le sentiment que si je ne me contrôle pas, que je ne me concentre pas pendant le bachacon et que je suis fermement les règles, je ne pourrai pas me connecter au futur.

Problème A

Comptez le nombre de 1. Au départ, j'ai utilisé find au lieu de count. Pourquoi ne comprenez-vous même pas les fonctions de base ...

answerA.py

print(input().count("1"))

Problème B

Hmm, écrivez simplement. Vérifiez si tous les éléments sont divisibles par 2. Il semble y avoir une manière d'écrire plus concise. (← Je l'ai ajouté car j'ai reçu un commentaire.)

answerB.py

n=int(input())
a=list(map(int,input().split()))
ans=0
def check_all():
    global a,n
    for i in range(n):
        if a[i]%2!=0:
            return False
    return True
while check_all():
    ans+=1
    for i in range(n):
        a[i]//=2
print(ans)

Postscript (27/03/2020)

J'ai publié les deux types de solutions que j'ai reçues dans les commentaires. C'est la première fois que j'utilise la fonction appelée all, donc j'aimerais l'utiliser à partir de maintenant.

answerB_better.py

n=int(input())
a=list(map(int,input().split()))

ans=0
while all(i%2==0 for i in a):
    ans+=1
    for j in range(n):
        a[j]//=2
print(ans)

answerB_better.py

from functools import reduce
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
x=reduce(gcd,a)

ans=0
while x%2==0:
    ans+=1
    x//=2
print(ans)

Problème C

Je veux réduire le nombre de balles à réécrire, c'est-à-dire que je ne veux pas réécrire celles avec plusieurs balles avec le même numéro, donc après avoir trié et placé le même nombre de balles les unes à côté des autres, regroupez-les avec le groupe par fonction. Après le regroupement, triez par ordre décroissant du nombre de boules et réécrivez tous les nombres de boules dans les groupes k + 1er et suivants (avec 1-index).

answerC.py

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
def groupby():
    global a
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
b=groupby()
b.sort(key=lambda x:x[1],reverse=True)
l=len(b)
ans=0
for i in range(k,l):
    ans+=b[i][1]
print(ans)

Problème D

Tout d'abord, cela signifie que vous pouvez décider librement dans les 2N fois, je vais donc chercher un moyen pratique. Tout d'abord, considérons le cas où tous les éléments sont égaux à 0 ou plus. Dans ce cas, vous pouvez facilement créer une séquence de nombres qui satisfait la condition en ** ajoutant à l'élément de droite dans l'ordre à partir de la gauche ** (jusqu'à n-1 fois) ($ a_1, a_1). + a_2,…, a_1 + a_2 +… + a_ {n-1} + a_n $.) Cependant, il y a des nombres négatifs ici, donc cette méthode ne peut pas remplir les conditions. Par conséquent, au contraire, on suppose que tous les éléments sont égaux à 0 ou moins. Dans ce cas, vous pouvez voir que ** vous pouvez effectuer l'opération inverse ** (jusqu'à n-1 fois). A partir de la considération ci-dessus, il est possible de créer une séquence de nombres qui satisfait la condition si le modèle est soit "tous les éléments sont 0 ou plus" ou "tous les éléments sont 0 ou moins". Par conséquent, envisagez ** de créer un tel modèle en ** n + 1 fois **. Afin de créer un tel modèle, nous nous sommes concentrés sur le nombre avec la valeur absolue maximale. Si ce nombre est négatif, vous pouvez l'ajouter à tous les autres éléments pour rendre tous les autres éléments négatifs, et s'il est positif, vous pouvez rendre tous les autres éléments positifs (jusqu'à n-1). Fois). Effectuez les deux opérations ci-dessus afin d'obtenir ce qui suit.

answerD.py

n=int(input())
a=list(map(int,input().split()))
c,d=min(a),max(a)
ans=[]
if abs(c)>abs(d):
    c_=a.index(c)
    for i in range(n):
        if i!=c_ and a[i]>0:
            ans.append(str(c_+1)+" "+str(i+1))
    for i in range(n-1,0,-1):
        ans.append(str(i+1)+" "+str(i))
else:
    d_=a.index(d)
    for i in range(n):
        if i!=d_ and a[i]<0:
            ans.append(str(d_+1)+" "+str(i+1))
    for i in range(n-1):
        ans.append(str(i+1)+" "+str(i+2))
l=len(ans)
print(l)
for i in range(l):
    print(ans[i])