[PYTHON] Code de l'éducation forces Round 92 Bacha Review (7/30)

résultat

Impressions

** Cette fois, j'ai fait une grosse erreur parce que la politique était appropriée ** ou ** j'ai abandonné parce que je pensais que ce serait difficile **. En conséquence, j'ai pu résoudre 5 questions (bien que j'aie vu des réponses), donc j'aimerais les résoudre lors de la production réelle.

Voir également @ e869120 cet article.

J'ai senti que c'était important. Je veillerai à le mettre en œuvre en gardant cela à l'esprit.

Problème A

Tous les $ x $, $ y $, $ lcm (x, y) $ sont compris entre $ l $ ou plus et $ r $ ou moins, et ** $ lcm (x, y) $ est le maximum parmi eux ** Ce sera. De plus, $ lcm (x, y) $ est un multiple de $ x $ et sa valeur minimale est $ 2x $ à partir de la condition que $ x <y $. Par conséquent, lorsque $ x = l, y = 2l, lcm (x, y) = 2l $, vous devriez vérifier si $ 2l $ est inférieur à $ r $.

A.py

t=int(input())
for _ in range(t):
    l,r=map(int,input().split())
    x,y=l,2*l
    if y<=r:
        print(x,y)
    else:
        print("-1 -1")

Problème B

L'ordre de Janken change en fonction de la position, mais ** $ c_1c_2… c_n $ jouera chacun $ n $ fois contre une autre main ($ s_1s_2… s_n $) ** (** Paraphrase du sujet et de l'objet) **). Par conséquent, pour $ c_i $, vous pouvez jouer contre $ s_1s_2… s_n $ et choisir le coup gagnant. Si «R» est le plus dans $ s_1s_2… s_n $, «P» et «S» sont les premiers. S'il y en a beaucoup, "R" et "P" devraient être les plus nombreux, et s'il y en a beaucoup, "S" devrait être utilisé. De plus, comme il se compose de n'importe quel $ i $, vous pouvez afficher la chaîne de caractères du nombre de fois de Janken.

B.py

t=int(input())
for i in range(t):
    S=input()
    l=len(S)
    r=S.count("R")
    s=S.count("S")
    p=S.count("P")
    m=max(r,s,p)
    if m==r:
        print("P"*l)
    elif m==s:
        print("R"*l)
    else:
        print("S"*l)

Problème C

Je pensais qu'il ne devrait pas y avoir de personnes excédentaires qui lisent mal, mais si vous regardez de près, cela dit qu'il y a peut-être des personnes excédentaires. C'est une réflexion.

Dans ce cas, ** les programmeurs les plus qualifiés doivent être combinés afin de dépasser ** $ x $. De plus, il peut y avoir des combinaisons de programmeurs qui ne dépassent pas $ x $ même à la fin, mais vous pouvez ignorer ces combinaisons.

Aussi, avec cette méthode gourmande, ** le plus petit nombre de personnes peut former un groupe **, on peut donc dire que le nombre de groupes est le plus grand.

C.py

t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    a=sorted(list(map(int,input().split())),reverse=True)
    now=[100000000000,0]
    for i in range(n):
        now=[min(now[0],a[i]),now[1]+1]
        if now[0]*now[1]>=x:
            d.append(now)
            now=[100000000000,0]
    print(len(d))

Problème D

J'ai également mal lu cela et j'ai rendu difficile de penser que ** Berserk peut spécifier deux personnes discontinues **. En fait, ce n'est pas si difficile car il n'y a que deux personnes d'affilée.

Les personnes qui sont continues peuvent être vaincues, alors faites attention à la partie où la personne qui bat est continue ** (ci-après dénommée partie continue). De plus, si vous voulez vaincre la dernière personne restante dans une partie continue avec Berserk, l'une des personnes non vaincues ($ L $ et $ R $) qui prend cette partie en sandwich doit avoir ** plus de pouvoir que cette personne * * Donc, nous avons besoin des informations de la personne qui les prend en sandwich.

Ici, si la longueur de la partie continue est divisée par $ k $ et qu'un reste apparaît, il faut réduire le reste par Berserk, et à ce moment, la personne avec la puissance maximale dans la partie continue ($ X $) Il est préférable de sélectionner et de vaincre les personnes situées des deux côtés.

De plus, si $ X $ a une puissance supérieure à $ L $ et $ R $, vous devez ** vaincre ce $ X $ avec Fireball **, et Fireball ne peut pas être utilisé ($ \ leftrightarrow $ longueur de la partie continue). Lorsque (est plus court que $ k $) et que l'ordre des personnes restantes est différent, le sujet n'est pas satisfait, donc -1 doit être affiché.

Au moment de l'implémentation, déterminez si $ X $ a une puissance plus élevée que $ L $ et $ R $ → S'il est déterminé, vaincre-le d'abord avec Fireball → Diviser la longueur de la partie continue par $ k $ Battez la partie avec Berserk → Répétez le reste avec Fireball et Berserk, ce qui est plus efficace, et ce sera plus facile.

Quand je l'ai résolu ** je n'ai pas pu organiser l'implémentation **, donc le code est un peu compliqué. Je veux aussi pouvoir faire attention à la propreté de la mise en œuvre.

D.py

n,m=map(int,input().split())
x,k,y=map(int,input().split())
a=list(map(int,input().split()))
c=list(map(int,input().split()))
b=set(c)
d=[]
now=[]
for i in range(n):
    if a[i] not in b:
        now.append(i)
        if i==n-1:
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
    else:
        if now!=[]:
            #Indice de bord et max(Le bord est-1,n peut être)
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
            now=[]
#Celui dont la position n'est pas en ordre
now=0
lc=len(c)
for i in range(n):
    if a[i]==c[now]:
        now+=1
        if now==lc:
            break
else:
    exit(print(-1))
l=len(d)
ans=0
for i in range(l):
    e=d[i]
    f=e[2]-e[0]-1
    if e[0]==-1:
        m=a[e[2]]
    elif e[2]==n:
        m=a[e[0]]
    else:
        m=max(a[e[0]],a[e[2]])
    if m>a[e[1]]:
        ans+=(f%k*y)
        ans+=min((f//k)*x,(f//k)*k*y)
    else:
        if f<k:exit(print(-1))
        ans+=(f%k*y)
        #Je dois les vaincre une fois avec k
        ans+=x
        ans+=min((f//k-1)*x,(f//k-1)*k*y)
print(ans)

Problème E

Envisagez de trouver $ x + (y-1) d = y + (x-1) d \ (mod \ w) $ sous $ 1 \ leqq x, y \ leqq min (d, m) $. Ici, vous pouvez effectuer une ** transformation d'expression ** avec $ x + (y-1) d = y + (x-1) d \ leftrightarrow (d-1) (x-y) = 0 $. Par conséquent, quand $ d-1 = 0 \ (mod \ w) $, tout $ x, y $ satisfera cela, donc si vous définissez $ z = min (d, m) $, alors $ \ _ {z } C \ _2 $ Ce sera tel quel.

Ici, quand ** $ d-1 \ neq 0 \ (mod \ w) $, cela semble être $ x = y \ (mod \ w) $, mais c'est faux **. Correctement, $ v = gcd (w, d-1) $ est $ x = y \ (mod \ v) $ (✳︎).

<détails>

t=int(input())
from math import gcd
for _ in range(t):
    m,d,w=map(int,input().split())
    z=min(d,m)
    d-=1
    if d%w==0:
        print(z*(z-1)//2)
        continue
    w//=gcd(d,w)
    z-=1
    x=z//w
    y=z%w+1
    print(x*(x-1)//2*(w-y)+(x+1)*x//2*y)