Vom numi secvenţă PM o succesiune formată din plus şi minus, care NU conţine două semne minus alăturate.

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

4 2

pm.out

10

#include <bits/stdc++.h>
using namespace std;

ifstream cin("pm.in");
ofstream cout("pm.out");

struct bigint
{
    int n , c[101];
}a[256] , b[256];

bigint aduna(bigint a , bigint b)
{
    bigint s = {0 , {0}};
    s.n = max(a.n , b.n);
    int t = 0;
    for(int i = 1 ; i <= s.n ; i++)
    {
        int cc = a.c[i] + b.c[i] + t;
        s.c[i] = cc % 10;
        t = cc / 10;
    }
    if(t > 0)
    {
        s.n++;
        s.c[s.n] = t;
    }
    return s;
}

void afisare(bigint a)
{
    for(int i = a.n ; i >= 1 ; i--)
        cout << a.c[i];
}

int main()
{
    int x , y;
    cin >> x >> y;
    for(int i = 1 ; i <= x + 1 ; i++)
    {
        for(int j = 0 ; j <= i ; j++)
            if(j == 0 || i == j) b[j] = {1 , {0 , 1}};
            else b[j] = aduna(a[j - 1] , a[j]);
        for(int j = 0 ; j <= i ; j++)
            a[j] = b[j];
    }
    afisare(a[y]);
}