C'était pareil même s'il n'y avait pas de collision parce que la vitesse a été prise en charge, en se disant "Il est très difficile de calculer le temps de collision dans l'ordre et de le traiter!". Il a été accroché et tué.
La réponse est que D est divisé par la vitesse totale et arrondi.
N, D = map(int, input().split())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
t = sum(v)
print((D + t - 1) // t)
Je ne pouvais pas le résoudre, je me demandais si le théorème de Fermat était impliqué, mais je ne pouvais pas penser à une conversion mathématique.
Addendum: A b c </ sup> </ sup> est A b × c </ sup> est une mathématique rudimentaire. Ici A P ! </ sup> est A P × (P-1) × (P-2)! </ Sup> = A P × (P-2)! × (P-1) </ sup > = A P × (P-2)! P-1 </ sup> </ sup>. D'après le théorème de Fermat, A P × (P-2) Si! </ Sup> est premier l'un à l'autre avec P, alors A P! </ Sup> = 1 (mod P). Au fait, P n'est pas un nombre composé mais un nombre premier, donc à la fin A et P sont premiers l'un à l'autre. Vous n'avez qu'à juger si c'est le cas.
Comme indiqué dans l'énoncé du problème, il s'agit de TLE en Python, le code suivant doit donc être soumis dans PyPy.
def make_prime_table(n):
sieve = list(range(n + 1))
sieve[0] = -1
sieve[1] = -1
for i in range(2, int(n ** 0.5) + 1):
if sieve[i] != i:
continue
for j in range(i * i, n + 1, i):
if sieve[j] == j:
sieve[j] = i
return sieve
readline = open(0).readline
prime_table = make_prime_table(5 * 10 ** 6)
T = int(readline())
result = []
for _ in range(T):
A, P = map(int, readline().split())
if prime_table[P] != P:
result.append(-1)
else:
if A % P == 0:
result.append(0)
else:
result.append(1)
print(*result, sep='\n')
Post-scriptum: Il était plus facile de comprendre s'il était réorganisé en A P-1 P × (P-2)! </ Su> </ sup>. 1 P × (P-2)! < / sup> ou 0 P × (P-2)! </ sup>, donc 1 ou 0 est un coup d'œil.
Postscript: j'ai également passé en Python.
def make_prime_table(n):
sieve = [True] * (n + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(n ** 0.5) + 1):
if not sieve[i]:
continue
for j in range(i * i, n + 1, i):
sieve[j] = False
return sieve
def main():
readline = open(0).readline
prime_table = make_prime_table(5 * 10 ** 6)
T = int(readline())
result = []
for _ in range(T):
A, P = map(int, readline().split())
if not prime_table[P]:
result.append(-1)
else:
if A % P == 0:
result.append(0)
else:
result.append(1)
print(*result, sep='\n')
main()
Après avoir écrit que cela peut être facilement résolu par le produit cumulatif, j'étais accro à ne pas penser à ce qui se passerait quand A i, j </ sub> était égal à 0.
Calculez le produit cumulé en excluant 0 pour tout, chaque ligne et chaque colonne. Remplissez la ligne r i </ sub> à partir du haut ou la colonne c i </ sub> à partir de la gauche. Mais s'il reste des 0, la réponse à cette requête est 0,0. S'il n'y a plus de 0, alors * O * (1) peut être utilisé pour calculer la réponse à la requête à l'aide du produit cumulatif précalculé.
readline = open(0).readline
H, W = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(H)]
Q = int(readline())
m = 1000000007
total = 1
rows = [1] * H
cols = [1] * W
total0 = 0
rows0 = [0] * H
cols0 = [0] * W
for i in range(H):
for j in range(W):
x = A[i][j]
if x == 0:
total0 += 1
rows0[i] += 1
cols0[j] += 1
else:
total *= x
total %= m
rows[i] *= x
rows[i] %= m
cols[j] *= x
cols[j] %= m
result = []
for _ in range(Q):
r, c = map(lambda x: int(x) - 1, readline().split())
x = A[r][c]
t = total0 - rows0[r] - cols0[c]
if x == 0:
t += 1
if t > 0:
result.append(0)
continue
t = total * pow(rows[r], -1, m) % m * pow(cols[c], -1, m) % m
if x != 0:
t *= x
t %= m
result.append(t)
print(*result, sep='\n')
Recommended Posts