[PYTHON] Educational Codeforces Round 90 Bacha Review (8/19)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich gab es auf zu denken, dass es unmöglich wäre, selbst wenn ich die Richtung der Idee wüsste. Ich bin mir nicht sicher, ob ich es aufgeben und fallen lassen soll. In diesem Fall möchte ich tief durchatmen und dann mit Überlegungen fortfahren **. Selbst wenn ich es eilig habe, möchte ich mich beruhigen und verstehen, was schwierig ist und was ich verbessern möchte.
Problem A
Wenn Sie den ersten Donut billiger als den zweiten machen möchten, kaufen Sie am besten nur einen ersten Donut und einen Satz des zweiten Donuts. Zu diesem Zeitpunkt kann $ a <c $ billiger sein, daher ist 1 die Antwort. Wenn es $ a \ geqq c $ ist, kann es bei keinem Kauf billiger sein, also ist -1 die Antwort.
Wenn Sie den zweiten Donut billiger als den ersten machen möchten, kaufen Sie am besten nur $ b $ für den ersten Donut und nur ein Set für den zweiten Donut. Zu diesem Zeitpunkt kann es billiger sein, wenn $ c <a \ times b $ ist, also ist $ b $ die Antwort. Außerdem kann $ c \ geqq a \ times b $ time bei keinem Kauf billiger sein, daher ist -1 die Antwort.
A.py
for _ in range(int(input())):
a,b,c=map(int,input().split())
ans=[]
if a<c:
ans.append(1)
else:
ans.append(-1)
if a*b>c:
ans.append(b)
else:
ans.append(-1)
print(" ".join(map(str,ans)))
B-Problem
Ich denke, es ist eine häufige Problemstellung. Wählen Sie benachbarte mit 0 und 1 aus und löschen Sie sie. Der Player verliert, wenn er nicht bedienbar ist. ** Wenn 0 und 1 beide in der Zeichenfolge enthalten sind, gibt es 0s und 1s, die nebeneinander liegen **, sodass die letzte verbleibende Zeichenfolge (die eine leere Zeichenfolge sein kann) entweder 0 oder 1 ist. Nur bleibt. Daher ist die Häufigkeit, mit der benachbarte Nullen und Einsen ausgewählt werden können, die kleinste der enthaltenen Nullen und Einsen. Wenn diese Zahl ungerade ist, ist es der erste Sieg, und wenn sie gerade ist, ist es der zweite Sieg.
B.py
for _ in range(int(input())):
s=input()
print(["NET","DA"][min(s.count("1"),s.count("0"))%2])
C-Problem
Es war schwer zu lesen, da die Problemstellung Pseudocode war. Hat die Writer-Person es übersprungen?
Bei Betrachtung der Zeichenfolge ändert sich die Variable cur als -1 für "-" und +1 für "+". Der Anfangswert von cur beim Scannen einer Zeichenfolge ist init und steigt in der Reihenfolge von 0 an.
Bei solchen Problemen verbessert ** das Experimentieren und Erfassen des Verhaltens ** die Aussichten. Wenn Sie also mit der ersten Probe "- + -" experimentieren, ist dies wie folgt.
Wenn das obige Experiment verbalisiert wird und die kumulative Summe in der Reihenfolge von links betrachtet wird, wird bis ** gesucht, wo die Aktualisierung des Mindestwerts erfolgt ** (zu Beginn auf 0 gesetzt), und bei Aktualisierung zum Anfang zurückgekehrt. Wenn Sie die obigen Schritte wiederholen und alle Stellen überprüfen, an denen die Aktualisierung erfolgt, ** scannen Sie alle Elemente am Ende **, um den Scan abzuschließen.
Mit anderen Worten, die Antwort besteht darin, die Summe der aktualisierten Indizes (1-indiziert) zu finden, während der Mindestwert gespeichert wird, während die kumulative Summe in der Reihenfolge von vorne betrachtet wird, und die Länge der Zeichenfolge als letzten Scan hinzuzufügen.
C.py
from itertools import accumulate
for _ in range(int(input())):
s=input()
l=len(s)
t=[1 if s[i]=="+" else -1 for i in range(l)]
t=list(accumulate(t))
now=0
ans=0
for i in range(l):
if t[i]<now:
ans+=(i+1)
now=t[i]
if i==l-1:
ans+=(i+1)
print(ans)
D Problem
Ich wollte gerade die richtige Antwort finden, verlor aber meine Konzentration. Schließlich denke ich, dass diese ** Aufrechterhaltung der Mentalität, wenn ich kurz davor bin, meine Konzentration zu verlieren **, die größte Herausforderung für mich ist.
Betrachten Sie den Fall, in dem die Summe der Zahlen, die den geraden Indizes entsprechen, wenn eine bestimmte fortlaufende Unterspalte ausgewählt und invertiert wird, das Maximum ist. Erstens, wie Sie leicht sehen können, ändert sich die Summe vor und nach dem Invertieren des ausgewählten kontinuierlichen Teilstrings nicht, wenn die Länge des ausgewählten kontinuierlichen Teilstrings ungerade ist. Berücksichtigen Sie also ** gerade **.
Daher werden für die Elemente, die in der ausgewählten zusammenhängenden Spalte mit gerader Länge enthalten sind, die Elemente mit dem ungeraden Index anstelle der Elemente mit dem geraden Index ausgewählt. Zu diesem Zeitpunkt habe ich auch versucht, mir einen kontinuierlichen Teilstring vorzustellen, der den Unterschied in der Änderung beim Wechsel von gerade zu ungerade maximiert, aber ** Da es schwierig ist, mit der gierigen Methode zu arbeiten, wird DP wie die maximale Teilsumme gesetzt. Ich denke, es ist eine natürliche Idee, mit ** zu denken (ich konnte meine Gedanken während des Wettbewerbs nicht organisieren ...).
Wenn hier eine fortlaufende Unterspalte ausgewählt wird (** mit Annahmen berücksichtigen ), ist es möglich, einen geraden Index vor und nach der fortlaufenden Unterspalte und einen ungeraden Index in der fortlaufenden Unterspalte auszuwählen. Ja ( 3 Arten von Zuständen !! **), DP kann wie folgt definiert werden.
$ dp [i] [j]: = $ (maximale Summe in jedem Zustand $ j $, wenn $ i $ -Indizes ausgewählt sind)
Wenn jedoch $ j = 0 $ ist, wurde die fortlaufende Unterspalte noch nicht ausgewählt, wenn $ j = 1 $, wurde die fortlaufende Unterspalte nicht ausgewählt, und wenn $ j = 2 $, wurde die fortlaufende Unterspalte noch nicht ausgewählt. Es wird gesagt. (Kontinuierliche Unterspalten haben wahrscheinlich zwei Muster: ** Verwalten Sie das Ende der fortlaufenden Unterspalte und nehmen Sie die Akkumulation am Ende ** Muster und ** Verwalten Sie, ob die fortlaufende Unterspalte ausgewählt ist **, also halten Sie sie niedrig. Ich will.)
Beachten Sie auch, dass Sie die Summe der Elemente des ausgewählten Index ermitteln möchten. Es sollte also das $ i $ th sein, nicht das ** $ i $ th **.
Darüber hinaus gibt es ** Muster, die mit einem geraden Index beginnen, und Muster **, die mit einem ungeraden Index beginnen, für fortlaufende Unterspalten mit gerader Länge, und das erstere, das $ i $ entspricht, ist $ a_ {2i-1} $. $ a_ {2i} $, letzteres entspricht $ i $ ist $ a_ {2i} $ und $ a_ {2i + 1} $.
Unter Berücksichtigung des Übergangs von DP, der durch Ausführen von DP für jedes der beiden Muster erhalten werden kann, ist dies wie folgt. Außerdem betrachten wir im Folgenden ein Muster, das mit einem ungeraden Index beginnt.
(1) Wenn $ j = 0 $
Sie haben keine andere Wahl, als Elemente mit geraden Indizes auszuwählen, wie unten gezeigt.
(2) Wenn $ j = 1 $
Es bleibt keine andere Wahl, als ein Element mit einem ungeraden Index auszuwählen, und es kann zwei Übergangsquellen geben, $ dp [i-1] [0] und dp [i-1] [1] $.
(3) Wenn $ j = 2 $
Es bleibt keine andere Wahl, als ein Element mit einem geraden Index auszuwählen, und es kann zwei Übergangsquellen geben, $ dp [i-1] [1] und dp [i-1] [2] $.
Wenn Sie es implementieren, während Sie auf $ i = 0 $ ~ $ [\ frac {n-1} {2}] $ achten, sieht es wie folgt aus.
D.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
dp0=[[0,0,0] for i in range((n-1)//2+1)]
for i in range((n-1)//2+1):
if i==0:
dp0[i][0]=a[2*i]
continue
dp0[i][0]=dp0[i-1][0]+a[2*i]
dp0[i][1]=max(dp0[i-1][0],dp0[i-1][1])+a[2*i-1]
dp0[i][2]=max(dp0[i-1][1],dp0[i-1][2])+a[2*i]
dp1=[[0,0,0] for i in range((n-1)//2+1)]
for i in range((n-1)//2+1):
if i==0:
dp1[i][0]=a[2*i]
if 2*i+1<n:dp1[i][1]=a[2*i+1]
continue
dp1[i][0]=dp1[i-1][0]+a[2*i]
if 2*i+1<n:dp1[i][1]=max(dp1[i-1][0],dp1[i-1][1])+a[2*i+1]
if 2*i<n:dp1[i][2]=max(dp1[i-1][1],dp1[i-1][2])+a[2*i]
#print(dp0)
#print(dp1)
print(max(dp0[(n-1)//2]+dp1[(n-1)//2]))
E Problem
Wenn beispielsweise $ x = 108, k = 3 $ ist, sind es $ 108.109.110.111 $, aber wenn es keinen Übertrag gibt, gilt $ f (x + 1) = f (x) + 1 $. Daher werden wir Fälle mit ** ohne Übertrag und mit ** klassifizieren und nach Fällen mit angegebenem $ n $ suchen. Wenn es mehrere $ x $ -Kandidaten gibt, sollte der kleinste ausgegeben werden. (Hier natürlich ** habe ich die Implementierung aufgegeben, weil es mühsam war, sie auszuführen **, aber ich konnte sie nach dem Wettbewerb lösen, ich bedauere es ...)
(1) Wenn kein Übertrag vorliegt
Wenn man sich die letzte Ziffer ansieht, ist es $ i, i + 1,…, i + k $. Zu diesem Zeitpunkt, wenn $ i, i + 1, ..., i + k $ und $ i + l, i + l + 1, ..., i + l + k $ mit $ l> 0 $ verglichen werden, ist letzteres oben. Die Summe jeder Ziffer ist $ (k + 1) \ mal l $ kleiner als die erstere. Daher sollte ** die niedrigstwertige Ziffer so groß wie möglich sein ** und $ 9-k, 9-k + 1,…, 9-k + k $ ist optimal (✳︎). Zu diesem Zeitpunkt ist die Summe der niedrigstwertigen Ziffern $ \ frac {(18-k) (k + 1)} {2} $, sodass die darüber liegenden Ziffern $ n- \ frac {(18-k) sind. Betrachten Sie das Konstruieren mit (k + 1)} {2} $. Hier, ** weil es keinen Übertrag gibt, sind die oberen Ziffern alle gleich **, und wenn die Summe der Ziffern $ X $ ist, dann $ n- \ frac {(18-k) (k + 1)} {2} = X \ times (k + 1) $ muss gelten. Wenn dies wahr ist, wird es zu $ X = \ frac {n- \ frac {(18-k) (k + 1)} {2}} {k + 1} $. Um die obere Ziffer so klein wie möglich zu machen, sollte die überschüssige Zahl in die höchstwertige Ziffer gesetzt werden, wenn 9 in der Reihenfolge von der unteren Ziffer platziert wird. Darüber hinaus ist ungefähr (✳︎) $ n \ leqq \ frac {(18-k) (k + 1)} {2} $ nicht optimal, so dass ** $ x = 0 $ ~ $ 9-k $ zu diesem Zeitpunkt. Sie können alle Straßen ausprobieren **.
(2) Wenn es einen Übertrag gibt
Zu diesem Zeitpunkt müssen beide Informationen zu (1) ** wie viele 9s ohne die niedrigste Ziffer ** und (2) ** zu überprüfen sind, in welcher Zahl die niedrigste Ziffer 9 erscheint **. .. In Bezug auf (1) haben wir diesmal bis zu $ 19 $ untersucht, da $ n $ ungefähr 150 $ beträgt. Für (2) können Sie auch die Zahl (0-indiziert) ausprobieren, bei der die niedrigstwertige Ziffer 9 von $ 0 $ bis $ k-1 $ ist. Daher ist das erstere $ num9 $ und das letztere ist $ j $. Da das Schreiben in Buchstaben kompliziert ist, wird die aktuelle Situation in einem Diagramm dargestellt. (Wenn Sie den Fall von (1) nicht verstehen, möchten Sie möglicherweise ein Diagramm zeichnen.)
Wie in der obigen Abbildung gezeigt, ist +1 im Übertrag $ 1 \ mal (kj) $, aufeinanderfolgende 9s ohne die niedrigstwertige Ziffer sind $ num9 \ mal 9 \ mal (j + 1) $ und die niedrigstwertige Ziffer ist $ \ frac. {(18-j) (j + 1)} {2} + \ frac {(kj) (kj-1)} {2} $, das von $ n $ subtrahiert wird und (1) bleibt ) Und die gleiche Überlegung. Die Grundlagen sind die gleichen, aber beachten Sie nur, dass ** die letzte Ziffer in der oberen Ziffer nicht 9 sein kann und 8 ** ist, um das Tragen zu verhindern.
Das Obige ist implementiert und wird wie folgt. Als ich es löste, hatte ich das Gefühl, dass die Implementierung schwer war, aber ich hatte das Gefühl, dass es ein Problem war, dass ich die Aussicht auf Implementierung verbessern konnte, indem ich nicht nur Verbalisierung, sondern auch Diagramme verwendete.
E.py
for _ in range(int(input())):
n,k=map(int,input().split())
ans=[]
#Nicht tragen
if n<=(18-k)*(k+1)//2:
for i in range(10):
check=n
for j in range(k+1):
if i+j>9:
break
else:
check-=(i+j)
else:
if check==0:
ans.append(i)
else:
check=n-(18-k)*(k+1)//2
if check%(k+1)==0:
check//=(k+1)
i,j=check%9,check//9
if i==0:
ans.append(int("9"*j+f"{9-k}"))
else:
ans.append(int(f"{i}"+"9"*j+f"{9-k}"))
#Es gibt einen Carry
for num9 in range(20):
for j in range(k):
check=n-(18-j)*(j+1)//2-(k-j)*(k-j-1)//2
check-=(num9*9*(j+1))
check-=(1*(k-j))
#print(check)
if check>=0:
if check%(k+1)==0:
check//=(k+1)
h,i=check%9,check//9
#Sie müssen nicht durch 9 teilen
if i==0:
if h==0:
ans.append(int("9"*num9+f"{9-j}"))
else:
ans.append(int(f"{h}"+"9"*num9+f"{9-j}"))
else:
check-=8
h,i=check%9,check//9
if h==0:
ans.append(int("9"*i+"8"+"9"*num9+f"{9-j}"))
else:
ans.append(int(f"{h}"+"9"*i+"8"+"9"*num9+f"{9-j}"))
#print(ans)
if len(ans):
print(min(ans))
else:
print(-1)
Nach F Problem
Ich werde diesmal überspringen
Recommended Posts