0679 - calatorie

Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul (0,0) al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate (X,X). Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate (a,b), ai 2 variante de deplasare: în punctul (a,b+1) sau în punctul (a+1,b). La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma (a,a) nu poți trece, iar în celelalte puncte care au abscisa egală cu ordonata poți trece și în plus, acolo se află câte o stație de benzină unde poți să „faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poți trece dar acolo nu se află stații de benzină. Rezervorul mașinii tale are o capacitate de K litri.

Cerința

Determinați numărul de trasee distincte prin care poți ajunge la destinație. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

Date de intrare

Fișierul calatorie.in conține pe prima linie două numere separate printr-un spațiu, X și K, cu semnificația din enunț.

Pe linia a 2-a se găsește un număr N, care reprezintă numărul de puncte de forma (a,a) care nu pot fi traversate. Pe fiecare dintre următoarele N linii se află câte un număr a, cu semnificația că punctul (a,a) nu poate fi vizitat.

Date de ieșire

Fișierul calatorie.out conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 997.

Restricții și precizări

• 1 ≤ X ≤ 50000
• 2 ≤ K ≤ 50
• 0 ≤ N ≤ 10
• Călătoria începe cu rezervorul plin;
• Se garantează că există cel puțin un drum.

Exemplu:

Intrare

3 10
1
1

Ieșire

8

Rezolvare

<syntaxhighlight lang="python3"> MOD = 997

def count_distinct_paths(x, k, blocked_points):

   dp = [[0 for _ in range(x + 1)] for _ in range(x + 1)]

   dp[0][0] = 1

   for i in range(1, x + 1):
       for j in range(1, x + 1):
           if (i == j) and (j in blocked_points):
               continue

           if j <= i:
               if dp[i - 1][j] > 0 and j + k >= i:
                   dp[i][j] += dp[i - 1][j]

               if dp[i][j - 1] > 0:
                   dp[i][j] += dp[i][j - 1]

           elif i <= j:
               if dp[i + 1][j] > 0 and j - k >= i:
                   dp[i][j] += dp[i + 1][j]

               if dp[i][j + 1] > 0:
                   dp[i][j] += dp[i][j + 1]

   return dp[x][x] % MOD

def main():

   with open("calatorie.in", "r") as input_file:
       x, k = map(int, input_file.readline().split())
       n = int(input_file.readline())
       blocked_points = set()
       for _ in range(n):
           blocked_points.add(int(input_file.readline()))

   distinct_paths = count_distinct_paths(x, k, blocked_points)

   with open("calatorie.out", "w") as output_file:
       output_file.write(str(distinct_paths))

if __name__ == "__main__":

   main()

</syntaxhighlight>