[PYTHON] Educational Codeforces Round 92 Bacha Review (30.07.)

Ergebnis

Impressionen

** Dieses Mal habe ich einen großen Fehler gemacht, weil die Richtlinie angemessen war ** oder ** Ich habe aufgegeben, weil ich dachte, es wäre schwierig **. Infolgedessen konnte ich 5 Fragen lösen (obwohl ich einige Antworten gesehen habe), daher möchte ich sie während der eigentlichen Produktion lösen.

Siehe auch @ e869120's dieser Artikel.

Ich fand es wichtig. Ich werde darauf achten, dies in diesem Sinne umzusetzen.

Problem A

Alle $ x $, $ y $, $ lcm (x, y) $ liegen im Bereich von $ l $ oder mehr und $ r $ oder weniger, und ** $ lcm (x, y) $ ist das Maximum unter ihnen ** Es wird sein. Außerdem ist $ lcm (x, y) $ ein Vielfaches von $ x $ und sein Mindestwert ist $ 2x $ unter der Bedingung, dass $ x <y $ ist. Wenn also $ x = l, y = 2l, lcm (x, y) = 2l $ ist, sollten Sie prüfen, ob $ 2l $ kleiner als $ r $ ist.

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")

B-Problem

Die Reihenfolge von Janken ändert sich je nach Position, aber ** $ c_1c_2… c_n $ spielt jeweils $ n $ mal gegen eine andere Hand ($ s_1s_2… s_n $) ** (** Paraphrase von Subjekt und Objekt) **). Daher können Sie für $ c_i $ gegen $ s_1s_2… s_n $ spielen und den Gewinnzug wählen. Wenn „R“ in $ s_1s_2… s_n $ am meisten ist, sind „P“ und „S“ die ersten. Wenn es viele gibt, sollten "R" und "P" am meisten sein, und wenn es viele gibt, sollte "S" verwendet werden. Da es aus einem beliebigen $ i $ besteht, können Sie auch die Zeichenkette so oft wie Janken ausgeben.

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)

C-Problem

Ich dachte, dass es keine überschüssigen Leute geben sollte, die es falsch verstanden haben, aber wenn Sie genau hinschauen, heißt es, dass es möglicherweise überschüssige Leute gibt. Es ist ein Spiegelbild.

In diesem Fall sollten ** die erfahrensten Programmierer kombiniert werden, um ** $ x $ zu überschreiten. Es kann auch einige Programmiererkombinationen geben, die $ x $ auch am Ende nicht überschreiten, aber Sie können solche Kombinationen ignorieren.

Mit dieser gierigen Methode kann ** die kleinste Anzahl von Personen eine Gruppe bilden **, so dass gesagt werden kann, dass die Anzahl der Gruppen die größte ist.

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))

D Problem

Ich habe dies auch falsch verstanden und es schwierig gemacht zu glauben, dass ** Berserk zwei diskontinuierliche Personen spezifizieren kann **. Eigentlich ist es nicht so schwierig, weil nur zwei Leute hintereinander sind.

Menschen, die kontinuierlich sind, können besiegt werden. Achten Sie daher auf den Teil, in dem die Person, die besiegt, kontinuierlich ist ** (im Folgenden als kontinuierlicher Teil bezeichnet). Wenn Sie die letzte verbleibende Person in einem fortlaufenden Teil mit Berserk besiegen möchten, muss eine der nicht besiegten Personen ($ L $ und $ R $), die diesen Teil einklemmt, ** mehr Macht als diese Person * haben. * Wir brauchen also die Informationen der Person, die sie einschließt.

Wenn hier die Länge des fortlaufenden Teils durch $ k $ geteilt wird und ein Rest angezeigt wird, muss der Rest durch Berserk und zu diesem Zeitpunkt die Person mit der maximalen Leistung im fortlaufenden Teil ($ X $) reduziert werden. Es ist am besten, die Menschen auf beiden Seiten auszuwählen und zu besiegen.

Wenn $ X $ eine höhere Potenz als $ L $ und $ R $ hat, müssen Sie diese $ X $ mit Fireball ** besiegen, und Fireball kann nicht verwendet werden ($ \ leftrightarrow $ Länge des fortlaufenden Teils). Wenn (kürzer als $ k $ ist) und wenn die Reihenfolge der verbleibenden Personen unterschiedlich ist, ist das Thema nicht erfüllt, daher sollte -1 ausgegeben werden.

Bestimmen Sie zum Zeitpunkt der Implementierung, ob $ X $ eine höhere Leistung als $ L $ und $ R $ hat → Wenn dies bestimmt ist, besiegen Sie es zuerst mit Fireball → Teilen Sie die Länge des fortlaufenden Teils durch $ k $ Besiege den Teil mit Berserker → Wiederhole den Rest mit Feuerball und Berserker, was effizienter ist und einfacher wird.

Als ich es gelöst habe ** konnte ich die Implementierung nicht organisieren **, daher ist der Code etwas chaotisch. Ich möchte auch auf die Sauberkeit der Implementierung achten können.

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!=[]:
            #Kanten- und Maximalindex(Die Kante ist-1,n kann sein)
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
            now=[]
#Derjenige, dessen Position nicht in Ordnung ist
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)
        #Ich muss sie einmal mit k besiegen
        ans+=x
        ans+=min((f//k-1)*x,(f//k-1)*k*y)
print(ans)

E Problem

Betrachten Sie $ x + (y-1) d = y + (x-1) d \ (mod \ w) $ unter $ 1 \ leqq x, y \ leqq min (d, m) $. Hier können Sie ** Ausdruckstransformation ** mit $ x + (y-1) d = y + (x-1) d \ leftrightarrow (d-1) (x-y) = 0 $ durchführen. Wenn also $ d-1 = 0 \ (mod \ w) $ ist, wird jedes $ x, y $ dies erfüllen. Wenn Sie also $ z = min (d, m) $ setzen, dann ist $ \ _ {z } C \ _2 $ Es wird so sein wie es ist.

Wenn ** $ d-1 \ neq 0 \ (mod \ w) $ ist, scheint es hier $ x = y \ (mod \ w) $ zu sein, aber das ist falsch **. Richtig, $ v = gcd (w, d-1) $ ist $ x = y \ (mod \ v) $ (✳︎).

Daher ist ** $ mod \ v $ $ 1 $ ~ $ min (d, m) $, und es gibt verschiedene Werte **, aber ** $ mod \ v $ ist am Anfang von 1 * schwer zu denken. * Überlegen Sie also, wie viele Möglichkeiten es für $ 0 $ ~ $ min (d, m) -1 $ gibt.

Wenn Sie $ X = [\ frac {min (d, m) -1} {v}], Y = (min (d, m) -1) % v $ setzen, dann ist $ 0 $ ~ $ Y \ ( Im Fall von mod \ v) $ gibt es $ X + 1 $ Möglichkeiten, also gibt es $ _ {X + 1} C_2 $ Möglichkeiten, $ x bzw. y $ auszuwählen. Wenn $ Y + 1 $ ~ $ v-1 \ (mod \ v) $ ist, gibt es $ X $ Straßen, sodass Sie $ x und y $ bzw. $ \ _ {X} C \ _2 $ auswählen können. Es wird eine Straße sein.

Daher ist aus dem Obigen, wie man die Summe von $ x, y $ auswählt, $ \ _ {X + 1} C_2 \ mal (Y + 1) - \ _ {X} C \ _2 \ mal Y $, und dies wird ausgegeben. TU es einfach.

E.py

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)

Nach F Problem

Ich kann diesmal nicht lösen.