AtCoder ABC161 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 161, der am 04.04.2020 (Sa) ausgehend von Problem A unter Berücksichtigung der Berücksichtigung durchgeführt wurde. Das erste Halbjahr befasst sich mit Fragen bis ABC. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF
Problemstellung Es gibt drei Felder $ A $, $ B $, $ C $. Jedes Feld enthält eine Ganzzahl. Derzeit sind die Ganzzahlen in den Feldern $ A $, $ B $, $ C $ $ X $, $ Y $, $ Z $. Suchen Sie die Ganzzahlen in jedem dieser Felder, nachdem Sie die folgenden Vorgänge der Reihe nach ausgeführt haben. ・ Tauschen Sie den Inhalt von Feld $ A $ und Feld $ B $ aus ・ Tauschen Sie den Inhalt von Feld $ A $ und Feld $ C $ aus
Ursprünglich geht der Inhalt von Box $ A $ in Box $ B $, der Inhalt von Box C in Box $ A $ und der Inhalt von Box $ B $ in Box $ C $. Daher enthält die Box $ A $ $ Z $, die Box $ B $ enthält $ X $ und die Box $ C $ enthält $ Y $, daher ist es in Ordnung, in dieser Reihenfolge auszugeben.
abc161a.py
x, y, z = map(int, input().split())
print(z, x, y)
Problemstellung Wir haben für die Produkte vom Typ $ N $ gestimmt. Waren $ i $ erhalten $ A_i $ Stimmen. Wählen Sie das beliebte $ M $ -Stück aus dieser Liste aus. Sie können jedoch keine Produkte auswählen, deren Stimmenzahl weniger als $ \ frac {1} {4M} $ der Gesamtzahl der Stimmen beträgt. Geben Sie "Ja" aus, wenn Sie beliebte Produkte im Wert von $ M $ auswählen können, oder "Nein", wenn Sie sie nicht auswählen können.
In der Erklärung wurde zuerst die Sortiermethode beschrieben, aber ich dachte, dass die zweite Lösung einfacher ist. Es ist in Ordnung, wenn Sie die Produkte zählen, für die die Anzahl der erhaltenen Stimmen $ \ frac {1} {4M} $ oder mehr der Gesamtzahl der Stimmen beträgt, und beurteilen, ob es mehr als $ M $ gibt. Wenn es zu WA wird, denke ich, dass "kleiner als ** **" mit dem Folgenden verwechselt werden kann oder ob "=" in den bedingten Ausdruck aufgenommen werden sollte oder nicht. sum (a_list) ist eine Funktion, die alle Zahlen in der Liste summiert.
abc161b.py
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
sum_a = sum(a_list)
count = 0
for a in a_list:
if a >= sum_a / (4 * m):
count += 1
if count >= m:
print("Yes")
else:
print("No")
Problemstellung Aoki kann die folgenden Operationen für jede Ganzzahl $ x $ ausführen. Operation: Ersetzen Sie $ x $ durch den absoluten Wert der Differenz zwischen $ x $ und $ K $. Gegeben der Anfangswert der ganzen Zahl $ N $. Suchen Sie den Mindestwert von $ N $, der verwendet werden kann, wenn die obige Operation für diese Ganzzahl so oft ausgeführt wird, wie Sie möchten.
Ich habe einige Zeit gebraucht, um dieses Problem zu lösen. Vorläufig dachte ich, dass das Minimum von $ N $ erhalten würde, wenn ich gemäß den Regeln eine Schleife machen würde, aber als ich das Programm schrieb, konnte ich "100000000000000000000 1" in Eingabebeispiel 3 nicht in 2 Sekunden lösen und hörte ein wenig auf. Wenn Sie sorgfältig darüber nachdenken, wenn die Eingabe $ N $ groß und $ K $ klein ist, werden Sie viele Male subtrahieren, aber vorerst wird entschieden, dass Sie $ N $ / $ K $ mal machen, damit Sie diesen Betrag sofort subtrahieren können. In diesem Sinne wurde der folgende Code vervollständigt. (Da ich keine Zeit hatte, den Code für die Person, deren Subtraktionsergebnis negativ ist, detailliert zu schreiben, wenn (n - k) vorerst negativ ist, wenn der absolute Wert der Differenz größer als die ursprüngliche Zahl ist, besteht vorerst keine Notwendigkeit, mehr zu tun, und wenn er kleiner ist Es hat funktioniert, wenn ich den absoluten Wert der Differenz auf n) aktualisiert habe.
abc161c.py
n, k = map(int, input().split())
while(True):
if n - k > 0:
if n // k > 0:
n = n - k * (n // k)
else:
if n - k < n:
n = n - k
else:
break
else:
if abs(n - k) < n:
n = abs(n - k)
else:
break
print(n)
Wenn es sich um einen echten Wettbewerb handelt, können Sie den obigen Code schreiben, aber ich habe den zusammenfassenden Artikel mit Bezug auf die Erklärung etwas einfacher umgeschrieben. Die Erklärung lautet wie folgt.
Kommentar Wenn $ x $ $ K $ oder mehr ist, wird es durch Ausführen der Operation zu $ x-K $. Das heißt, durch Ausführen von $ N / K $ -Operationen von $ N $ ist die Ganzzahl der Rest von $ N $ geteilt durch $ K $. Sei $ t $ der Rest von $ N $ geteilt durch $ K $. Wenn Sie mit $ t $ arbeiten, ist dies $ K - t $. Wenn Sie mit $ K - t $ arbeiten, kehrt es einfach zu $ t $ zurück. Das heißt, nur $ t $ oder $ K - t $ können als Wert kleiner als $ K $ angenommen werden. Die Antwort ist also die kleinere von $ t $ und $ K - t $, dh der Rest von $ N $ geteilt durch $ K $ und $ K− $ (der Rest von $ N $ geteilt durch $ K $). Der kleinere.
Es ist eine lange Geschichte in der Mitte, aber die Schlussfolgerung ist einfach und Sie können zu viel verwenden, um zu antworten. Wenn Sie den Code in Bezug darauf schreiben, ist dies wie folgt.
abc161c.py
n, k = map(int, input().split())
t = n % k
print(min(t, k - t))
Ich konnte in 3 Zeilen schreiben (lacht) Es ist offensichtlich im Vergleich zu dem, was ich ursprünglich eingereicht habe. Ich bedaure, nicht bemerkt zu haben, dass die Formel für n = n - k * (n // k), die ich ursprünglich geschrieben habe, n = n% k ist. Wenn die Erklärung nur aus Buchstaben besteht und schwer zu verstehen ist, können Sie sie anhand eines konkreten numerischen Beispiels leicht verstehen. Das Auflisten aller verschiedenen Muster erschwert das Lesen des Artikels. Nehmen wir also ein typisches Beispiel, wenn n = 1003 und k = 5. In diesem Fall werden 1003 bis 5 zuerst 200 Mal subtrahiert, und das Ergebnis ist 3. Diese 3 ist zu viel von 1003/5, so dass das Programm 3 mal 1003% 5 erhalten kann. Das heißt, t = 3. Was schließlich kleiner ist, t oder k - t, ist k - t = abs (t - k) = abs (3-5) = 2. Daher ist in 3 und 2 2 kleiner, daher lautet die Antwort 2.
Dies ist das Ende der ersten Hälfte. In der zweiten Hälfte wird das DEF-Problem erläutert. Vielen Dank, dass Sie vorerst bis zum Ende der ersten Hälfte gelesen haben. Fortsetzung in der zweiten Hälfte.
Recommended Posts