Может ли кто-нибудь помочь мне, как вычислить матрицу перехода в задаче D Google Code Jam 2008? [закрыто] ⇐ Python

[Anonymous]

Я пытаюсь улучшить свои навыки в области компьютерных наук, поэтому начинаю участвовать в соревнованиях по программированию.

Я начал с Google Code Jam 2008.

Все было хорошо, пока я не нашел проблему, с которой мне действительно трудно справиться.

Она называется «Автобусные остановки», и вы можете найти ее здесь: https://zibada.guru/gcj/2008r4c/problems/#D

Я пытался понять ответ, который находится здесь: https://zibada.guru/gcj/2008r4c/problems/#anaанализ-D, но я застрял

с переходом матрицы. Я не знаю, как это вычислить. Может ли кто-нибудь мне помочь?

Я написал код (см. ниже), но не знаю, хорош ли он (например, инициализация матрицы dp)

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\[s\]\[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 ... e-jam-2008