sg1

Sg1

== include(page="template/taskheader" task_id="sg1") ==

O misiune a echipei SG1 consta in activarea unui dispozitiv extraterestru actionat cu ajutorul unei tastaturi ciudate formate din $n$ comutatoare aflate initial toate in aceeasi pozitie (sa o notam cu $0$). Se stie ca trebuie setate (trecute in pozitia $1$) exact $k$ comutatoare si ca nu conteaza ordinea in care trebuie actionate comutatoarele. In plus, cu ajutorul unor documente antice, au aflat ca intre oricare doua comutatoare succesive setate se pot afla cel putin $d1$ si cel mult $d2$ comutatoare nesetate. De exemplu, pentru $n=7$, $k=3$, $d1=1$, $d2=2$, o configuratie care corespunde cerintei este: $0100101$, in timp ce configuratiile $1010001$, $1100100$, $1010101$ nu corespund datelor problemei.Daca o combinatie de comutatoare setate nu activeaza dispozitivul, nu se intampla nimic deosebit (ce plictisitor episod!), ci comutatoarele se reseteaza automat, permitand incercarea altei combinatii.
Scrieti un program care, pentru valorile $n$, $k$, $d1$, $d2$ date, determina numarul total de configuratii posibile de comutatoare ce respecta conditiile din enunt.

O misiune a echipei SG1 consta in activarea unui dispozitiv extraterestru actionat cu ajutorul unei tastaturi ciudate formate din $n$ comutatoare aflate initial toate in aceeasi pozitie (sa o notam cu $0$). Se stie ca trebuie setate (trecute in pozitia $1$) exact $k$ comutatoare si ca nu conteaza ordinea in care trebuie actionate comutatoarele. In plus, cu ajutorul unor documente antice, au aflat ca intre oricare doua comutatoare succesive setate se pot afla cel putin $d{~1~}$ si cel mult $d{~2~}$ comutatoare nesetate. De exemplu, pentru $n=7$, $k=3$, $d{~1~}=1$, $d{~2~}=2$, o configuratie care corespunde cerintei este: $0100101$, in timp ce configuratiile $1010001$, $1100100$, $1010101$ nu corespund datelor problemei. Daca o combinatie de comutatoare setate nu activeaza dispozitivul, nu se intampla nimic deosebit (ce plictisitor episod!), ci comutatoarele se reseteaza automat, permitand incercarea altei combinatii.
Scrieti un program care, pentru valorile $n$, $k$, $d{~1~}$, $d{~2~}$ date, determina numarul total de configuratii posibile de comutatoare ce respecta conditiile din enunt.

h2. Date de intrare

In fisierul $text sg1.in$ se dau, pe aceeasi linie, despartite prin spatii, valorile $n$, $k$, $d1$ si $d2$.

In fisierul text $sg1.in$ se dau, pe aceeasi linie, despartite prin spatii, valorile $n$, $k$, $d{~1~}$ si $d{~2~}$.

h2. Date de iesire

* $0 < n < 101$
* $0 < k &le; n$

* $0 &le; d1 &le; d2 < n$

* $0 &le; d{~1~} &le; d{~2~} < n$

h2. Exemplu
table(example). |_. sg1.in |_. sg1.out |_. Explicatie|

|$7 3 1 2$|$8$|cele $8$ configuratii sunt:
$1010100$, $1010010$,
$1001010$, $1001001$,
$0101010$, $0101001$,
$0100101$, $0010101$
|
|$5 2 0 0$|$4$|cele $4$ configuratii sunt:
$11000$, $01100$,
$00110$, $00011$
|
|$14 8 1 5$|$0$|Nu exista configuratii care sa respecte cerintele problemei|

|$7 3 1 2$|$8$|$1010100$, $1010010$, $1001010$, $1001001$, $0101010$, $0101001$, $0100101$, $0010101$|
|$5 2 0 0$|$4$|$11000$, $01100$, $00110$, $00011$|
|$14 8 1 5$|$0$|Nu exista configuratii care respecta cerintele problemei|

== include(page="template/taskfooter" task_id="sg1") ==

1881