Я пытаюсь улучшить свои навыки в области компьютерных наук, поэтому начинаю участвовать в соревнованиях по программированию.
Я начал с Google Code Jam 2008.
Все было хорошо, пока я не нашел проблему, с которой мне действительно трудно справиться.
Она называется «Автобусные остановки», и вы можете найти ее здесь: https://zibada.guru/gcj/2008r4c/problems/#D
Я пытался понять ответ, который находится здесь: https://zibada.guru/gcj/2008r4c/problems/#anaанализ-D, но я застрял
с переходом матрицы. Я не знаю, как это вычислить
import math
#Value of dp[k][j+1]
def sum_(nb_states,k,j,C,dp,modulo):
s=0
for l in range(0,nb_states):
s=s+C[l][k]*dp[l][j]
s=s%modulo
return(s)
#k among N
def k_among_n(N,K):
g=math.factorial(N)
gg=math.factorial(K)
ggg=math.factorial(N-K)
l=(g)(gg*ggg)
return(l)
#sample is the input
#and follow this pattern : N, K, P
#N : Number of bus arrest, K : Number of buses, P : distance between any two consecutive stops for a bus
sample=[]
sample.append("10 3 3")
sample.append("40 4 8")
sample.append("3 2 2")
sample.append("5 2 3")
#sol is the output which is the answer to sample
sol=[]
sol.append(1)
sol.append(7380)
sol.append(1)
sol.append(3)
for o in range(0,len(sample)):
#Extract data
val=sample[o].split(" ")
N=int(val[0])
K=int(val[1])
P=int(val[2])
modulo=30031
#Computation of the number of states
nb_states=int(k_among_n(P,K))
#Initialization of the dp matrix
#dp[k] is the number of ways we can get into state s while having the window in position p
#a state is a combination of K buses in P
#ie : all the states are the value from K among P
#ie : K=2 N=4 the number of states are 6
#i have choose to put 1 at the j==0 because j==0 is the position 0 and there is only state for this position
dp=[]
for k in range(0,nb_states):
t=[]
for j in range(0,N):
if j==0:
t.append(1)
else:
t.append(0)
dp.append(t)
#C : matrice transition with C[k][j] is the
#number of ways to go from a state k to a state j
C=[]
#I need to put here the transition matrix
#but i dont know how to compute it
#loop to find the dp[k][j]
#j : the number of buses stop
#k : the number of states
for k in range(0,nb_states):
for j in range(0,N-1):
dp[k][j+1]=sum_(nb_states,k,j,C,dp,modulo)
#Sol2 : answer
sol2=dp[nb_states-1][N-1]%modulo
print("------ANSWER-----")
print(f"Good Answer :{sol[o]}")
print(f"My solution : {sol2}")
Подробнее здесь: https://stackoverflow.com/questions/798 ... ix-c-where
