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

Temps requis

Impressions

Je suis content que l'ancien problème ait de bonnes performances, mais je suis bon dans ce domaine, alors j'aimerais resserrer mon esprit. Je ne suis pas bon en DP, alors j'aimerais bientôt prendre des mesures contre DP (je pense qu'il y avait quelque chose comme un concours de DP).

Problème A

Découvrez si $ A \ times B $ est pair ou impair.

answerA.py

a,b=map(int,input().split())
print("Yes" if (a*b)%2==1 else "No")

Problème B

Il prend les chaînes en entrée dans l'ordre et vérifie dans l'ordre si la première lettre correspond à la fin du mot précédent. En outre, stockez la chaîne de caractères dans l'ensemble et vérifiez s'il y a une couverture.

answerB.py

n=int(input())
now=input()
s=set()
s.add(now)
for i in range(n-1):
    now2=input()
    if now[-1]!=now2[0]:
        print("No")
        break
    now=now2
    s.add(now)
else:
    if len(s)==n:
        print("Yes")
    else:
        print("No")

Problème C

Vous ne pouvez déplacer que y → y + D, y-D, et comme vous êtes à la coordonnée X au début, vous ne pouvez visiter que les coordonnées où la distance de X est un multiple de D. Comme il suffit de considérer le nombre maximum dans D, l'engagement maximum est la solution lorsqu'on considère la distance à la coordonnée X des coordonnées $ x_1, x_2,…, x_n $.

answerC.py

from fractions import gcd
n,X=map(int,input().split())
x=list(map(int,input().split()))
ans=abs(X-x[0])
for i in range(1,n):
    ans=gcd(abs(X-x[i]),ans)
print(ans)

Problème D

Tout d'abord, il est difficile de rendre le nombre de pièces pair pour chaque carré car vous pouvez déplacer une pièce pour chaque carré et il n'y en a que des ** pairs ou impairs **. J'ai trouvé qu'il n'y avait pas de **. J'ai donc pensé à une opération permettant de faire un nombre pair de pièces pour toutes les cases **. Ensuite, en faisant attention à chaque ligne, j'ai trouvé qu'une telle opération semble être possible en vérifiant la régularité du nombre de pièces dans chaque carré de l'extrémité gauche à l'extrémité droite. En d'autres termes, si le nombre de pièces dans le carré que vous vérifiez est impair, déplacez une pièce vers la droite, et s'il est pair, ne la déplacez pas. Cela vous permet de ** rendre le nombre de pièces pair ** pour toutes les lignes, à l'exception du carré le plus à droite. De plus, vous pouvez maximiser le nombre de carrés avec un nombre pair de pièces en déplaçant les pièces de haut en bas pour le carré le plus à droite (c'est-à-dire la colonne W la plus à droite). De plus, vous ne pouvez pas déplacer des pièces dans les cases (H, W), mais si le nombre total de pièces sur toutes les cases est impair, vous ne pouvez faire que le nombre de pièces de cette case un nombre impair. Au contraire, si le nombre total de pièces est pair, le nombre de pièces dans les carrés (H, W) est également pair, de sorte que le nombre de carrés dans lesquels même les pièces sont placées peut être maximisé. Je comprends.

✳︎ La dernière sortie était 1WA car elle était sortie sous forme de tableau. Ne négligez pas ** Vérifiez le format de sortie **.

answerD.py

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
ans=[]
for i in range(h):
    for j in range(w-1):
        if a[i][j]%2==1:
            a[i][j+1]+=1
            a[i][j]-=1
            ans.append([i+1,j+1,i+1,j+2])
for i in range(h):
    if a[i][w-1]%2==1:
        if i!=h-1:
            a[i+1][w-1]+=1
            a[i][w-1]-=1
            ans.append([i+1,w,i+2,w])
l=len(ans)
print(l)
for i in range(l):
    print(" ".join(map(str,ans[i])))