Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.
Die Lösung, die ich hier schreibe, wird geschrieben, während ich mir den Kommentar und die Beiträge anderer Leute ansehe. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.
Es ist eine Frage zu beantworten, ob die angegebene dreistellige Zahl eine Zahl mit 7 ist.
Ich denke, es wird vergehen, egal wie du es schreibst. Ist es das Beste, es als Zeichenkette zu behandeln und seine Existenz mit "in" zu überprüfen?
S = input()
if '7' in S:
print('Yes')
else:
print('No')
Es ist eine Frage, nur die Zahlen, die nicht Fizz oder Buzz sind, bis zur angegebenen Zahl K zu zählen und zu beantworten, wie viele sie insgesamt sein werden.
Ich schrieb es so wie es war und es ging vorbei. Wenn $ O (n) $ bei $ N = 10 ^ 6 $ liegt, muss die Effizienz nicht verbessert werden.
count = 0
n = int(input())
for i in range(1, n+1):
if i%3 and i%5:
count += i
print(count)
C - Sum of gcd of Tuples (Easy)
Es ist eine Frage zu beantworten, wie viele maximale Versprechen für alle drei Zahlen unter K addiert werden.
Erstellen Sie alle Kombinationen mit itertools.combinations_with_replacement, um die maximale Verpflichtung zu ermitteln. Fügen Sie das 6-fache für $ a \ neq b \ neq c $ und das 3-fache für $ a \ neq b = c $ hinzu .. Ich habe versucht, schneller zu werden, indem ich die einmal berechnete Versprechensnummer gespeichert habe.
Es sieht nicht sehr hübsch aus, aber es ist weg.
import itertools
import math
K = int(input())
g = [[0] * (K+1) for _ in range(K+1)]
out = 0
for a, b, c in itertools.combinations_with_replacement(range(1, K+1), 3):
if g[a][b] == 0:
g[a][b] = math.gcd(a, b)
d = g[a][b]
if g[d][c] == 0:
g[d][c] = math.gcd(d, c)
if a == b and b == c:
out += g[d][c]
elif a != b and b != c:
out += g[d][c] * 6
else:
out += g[d][c] * 3
print(out)
Es ist eine Frage, wie viele Kombinationen von drei Arten von RGB gemacht werden können. Die Kombination wird jedoch unter bestimmten Bedingungen gespielt.
Alle RGB-Kombinationen haben $ R-Nummer \ mal G-Nummer \ mal B-Nummer $. Subtrahieren Sie von hier die Anzahl der Kombinationen, die die Bedingung erfassen.
Die Ausschlussbedingung "Kombination durch einen bestimmten Abstand getrennt" kann erhalten werden, indem der Abstand und der Startpunkt mit for für $ O (n ^ 2) $ gedreht werden. Wenn dieser Index R, G und B ausfüllt, wird er als Ausschlussziel aufgenommen.
Also habe ich den folgenden Code geschrieben. Ich ging daran vorbei.
import itertools
N = int(input())
S = input()
out = S.count('R') * S.count('G') * S.count('B')
RGBs = list(itertools.permutations(['R', 'G', 'B'], 3))
for i in range(1, N):
for j in range(N-i*2):
if (S[j], S[j+i], S[j+i*2]) in RGBs:
out -= 1
print(out)
E - Sum of gcd of Tuples (Hard)
Auch hier ist das Problem das maximale Versprechen, aber der Wert hat sich so stark erhöht, dass die vorherige Lösung es nie rechtzeitig schaffen wird.
Ich gab auf. Siehe den Kommentar.
Da es keine Zeit gibt, alle Kombinationen von $ a, b, c, ... $ zu finden, um $ \ gcd (a, b, c, ...) = X $ zu finden, ist ein bestimmtes $ X $ erfüllt. Zählen Sie die Anzahl der Kombinationen von $ a, b, c, ... $.
Die Tatsache, dass die maximale Verpflichtung von $ a, b, c, ... $ $ X $ ist, bedeutet, dass "alle $ a, b, c, ... $ durch $ X $ geteilt werden" "$ a, Alle von b, c, ... $ werden nicht durch $ n \ times X $ gebrochen (sondern $ n> 1 $). "
Betrachten Sie zunächst die Bedingung, dass "alle $ a, b, c, ... $ durch $ X $ teilbar sind". Unter den Zahlen von K bis 1 gibt es $ K \ über X $, die Vielfache von X sind. Da nur N von ihnen in einer Reihe stehen, gibt es $ ({K \ over X}) ^ N $ Kombinationen von $ a, b, c, ... $.
Darüber hinaus sucht die Bedingung, dass "alle $ a, b, c, ... $ nicht durch $ n \ mal X $ (jedoch $ n> 1 $) gebrochen werden" in absteigender Reihenfolge nach X und $ 2X, 3X , ... Sie können die Anzahl der Kombinationen von Dingen, die ein Vielfaches von $ sind, nacheinander subtrahieren.
Auf diese Weise wird die Anzahl der Kombinationen erhalten, die zu X werden, so dass sie erhalten werden kann, indem die Anzahl jeder Kombination x der Wert von X summiert wird.
Die Implementierung ist also wie folgt.
N, K = map(int, input().split())
li = [0]*(K+1)
out = 0
mod = 10**9+7
for i in range(K, 0, -1):
li[i] = pow(K//i, N, mod)
for j in range(i*2, K+1, i):
li[i] -= li[j]
out += li[i] * i
print(out%mod)
Das ist alles für diesen Artikel.
Recommended Posts