Ceci est un article de synthèse pour les débutants des professionnels de la compétition.
La solution que j'écris ici est écrite en regardant les commentaires et les soumissions d'autres personnes. Ce n'est peut-être pas ce que vous avez réellement soumis.
Il s'agit de savoir si le nombre à 3 chiffres donné est un nombre avec 7.
Je pense que cela passera peu importe comment vous l'écrivez. Est-il préférable de le traiter comme une chaîne de caractères et de vérifier son existence avec ʻin`?
S = input()
if '7' in S:
print('Yes')
else:
print('No')
Il s'agit de ne compter que les nombres qui ne sont pas Fizz ou Buzz jusqu'au nombre K donné et de répondre combien ils seront au total.
Je l'ai écrit tel quel et il est passé. Si $ O (n) $ at $ N = 10 ^ 6 $, il n'est pas nécessaire d'améliorer l'efficacité.
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)
Il s'agit de savoir combien de promesses maximales sont additionnées pour les trois nombres ci-dessous K.
Créez toutes les combinaisons avec ʻitertools.combinations_with_replacement` pour trouver l'engagement maximum, ajoutez 6 fois celui pour $ a \ neq b \ neq c $ et 3 fois celui pour $ a \ neq b = c $ .. J'ai essayé d'accélérer en sauvegardant le numéro de promesse une fois calculé. Ça n'a pas l'air très joli, mais c'est parti.
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)
Il s'agit de savoir combien de combinaisons de trois types de RVB peuvent être faites. Cependant, la combinaison sera jouée sous certaines conditions.
Toutes les combinaisons RVB ont $ R nombre \ fois le nombre G \ fois le nombre B $. À partir de là, soustrayez le nombre de combinaisons qui captureront la condition.
La condition d'exclusion "combinaison séparée par une certaine distance" peut être obtenue en tournant la distance et le point de départ avec pour pour $ O (n ^ 2) $. Si cet index remplit R, G et B, il sera inclus comme cible d'exclusion.
J'ai donc écrit le code suivant. Je suis passé par là.
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)
Encore une fois, le problème est l'engagement maximal, mais la valeur a tellement augmenté que la solution précédente ne sera jamais à temps.
J'ai abandonné. Voir le commentaire.
$ \ gcd (a, b, c, ...) = X $ n'a pas le temps de trouver toutes les combinaisons de $ a, b, c, ... $ Comptez le nombre de combinaisons de $ a, b, c, ... $.
L'engagement maximum de $ a, b, c, ... $ est $ X $, ce qui signifie que "tous les $ a, b, c, ... $ sont divisibles par $ X
Tout d'abord, considérons la condition que "tous les $ a, b, c, ... $ sont divisibles par $ X $". Parmi les nombres de K à 1, il y a $ K \ sur X $ qui sont des multiples de X. Puisque seuls N d'entre eux sont alignés, il y a $ ({K \ over X}) ^ N $ combinaisons de $ a, b, c, ... $.
De plus, la condition selon laquelle "tous les $ a, b, c, ... $ ne sont pas cassés par $ n \ fois X $ (cependant, $ n> 1 $)" recherche X par ordre décroissant et $ 2X, 3X , ... Vous pouvez soustraire le nombre de combinaisons de choses qui sont des multiples de $ dans l'ordre.
De cette manière, le nombre de combinaisons qui deviennent X est obtenu, donc il peut être obtenu en additionnant le nombre de chaque combinaison x la valeur de X.
Ainsi, la mise en œuvre est la suivante.
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)
C'est tout pour cet article.
Recommended Posts