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

résultat

Impressions

Depuis hier, j'ai décidé de faire du bacha Kodofo tous les jours autant que possible pour augmenter la quantité de résolution. Le D ~ F d'AtCoder est bloqué par un problème qui semble être un peu plus résolu à chaque fois, donc résolvez div2 ou edufo de Kodofo près de la bande de niveau. ABC était bien, mais j'ai rempli environ 70% des problèmes et j'ai senti qu'il y avait peu de problèmes au niveau, alors j'ai décidé de résoudre Kodofo.

Cette fois, j'ai mal lu les problèmes C et D et je les ai utilisés pendant longtemps, donc je n'ai pas pu résoudre le problème D pendant le concours. Ni l'un ni l'autre n'est difficile du tout, donc si vous ne savez pas, essayez de relire le problème **.

Problème A

Même avec ce problème, l'échantillon ne correspondait pas car j'ai fait une erreur lors de la sortie **. Pour la séquence de nombres donnée $ p $, s'il y a même une ** inversion d'augmentation / diminution (valeur extrême) **, le nombre est enregistré et sorti avec avant et après. De plus, lorsqu'il n'y a pas de valeur extrême, la séquence de nombres entière décroît ou augmente de manière monotone, il n'y a donc pas d'ensemble de $ i, j, k $ qui satisfait le sujet, et No doit être affiché.

A.py

#erreur de lecture(Erreur de sortie)
t=int(input())
for _ in range(t):
    n=int(input())
    p=list(map(int,input().split()))
    for i in range(1,n-1):
        if p[i-1]<p[i] and p[i]>p[i+1]:
            print("Yes")
            print(i,i+1,i+2)
            break
    else:
        print("No")

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 cela peut être dit pour tout $ i $, il suffit de sortir une chaîne de caractères de la longueur 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, vous pouvez combiner ** les programmeurs les plus qualifiés afin de dépasser ** $ x $, et il est possible que certains programmeurs ne dépassent pas $ x $ même s'ils sont combinés à la fin. , De telles combinaisons peuvent être ignorées.

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 eu du mal à 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 de suite.

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 * * Nous avons donc 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 est nécessaire de 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.

Aussi, 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é.

Ce qui précède est implémenté et ressemble à ce qui suit, mais comme je ne pouvais pas très bien y penser, le code devient un peu compliqué.

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)

Après le problème E

Je ne peux pas résoudre cette fois.