2449 - PM

Enunţ

Vom numi secvenţă PM o succesiune formată din plus şi minus, care NU conţine două semne minus alăturate. De exemplu, există 5 secvenţe PM de lungime 3: + + + , + + - , + - + , - + + , - + -.

Cerința

Să se determine numărul de secvenţe PM care conţin x semne plus şi y semne minus.

Date de intrare

Fişierul de intrare pm.in conţine pe prima linie două numere naturale separate prin spaţiu x, y, cu semnificaţia din enunţ.

Date de ieșire

Fişierul de ieşire pm.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numărul de secvenţe PM care conţin x semne plus şi y semne minus.

Restricții și precizări

• 0 ≤ y ≤ x ≤ 250
• Rezultatul va avea maxim 100 cifre.
• Pentru 50% din testele de evaluare, x < 32.
• 10% din punctaj se va acorda pe exemple.

Exemplu 1

pm.in

2 1

pm.out

3

Exemplu 2

pm.in

300 200

pm.out

Date de intrare invalide.

Rezolvare

#2449 PM
def verificare_date_intrare(x, y):
  if not (0 <= y <= x <= 250):
    return False
  return True

def numar_secvente_PM(x, y):
  if not verificare_date_intrare(x, y):
    return "Date de intrare invalide."
  
  dp = [[0] * (y + 1) for _ in range(x + 1)]
  dp[0][0] = 1

  for i in range(1, x + 1):
    for j in range(min(i, y) + 1):
      if j == 0:
        dp[i][j] = dp[i - 1][j]
      else:
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]

  numar_total = sum(dp[x])

  return numar_total

def main():
  with open("pm.in", "r") as fin:
    x, y = map(int, fin.readline().split())

  rezultat = numar_secvente_PM(x, y)

  with open("pm.out", "w") as fout:
    fout.write(str(rezultat) + "\n")

if __name__ == "__main__":
    main()