== include(page="template/taskheader" task_id="nmult") ==
Poveste şi cerinţă...
Se consideră trei numere naturale nenule <tex>n</tex>, <tex>k</tex> şi <tex>w</tex>.
h2. Cerinţă
Să se scrie un program care determină numărul <tex>m</tex> al mulţimilor de forma <tex>\[\left \{ x_{1}, x_{2}, ..., x_{k} \right \}\]</tex>, având ca elemente numere naturale nenule, ce satisfac simultan condiţiile:
* <tex>\[1 \leq x_{1} < x_{2} < ... < x_{k} \leq n\]</tex>
* <tex>\[x_{i+1} - x_{i} \geq w, 1 \leq i \leq k-1\]</tex>
h2. Date de intrare
Fişierul de intrare $nmult.in$ ...
Fişierul de intrare $nmult.in$ conţine pe prima linie trei numere naturale nenule <tex>n</tex>, <tex>k</tex>, <tex>w</tex> separate prin câte un spaţiu, cu semnificaţia de mai sus.
h2. Date de ieşire
În fişierul de ieşire $nmult.out$ ...
În fişierul de ieşire $nmult.out$ va conţine pe prima linie restul împărţirii numărului <tex>m</tex> la <tex>666013</tex>.
h2. Restricţii
* $... ≤ ... ≤ ...$
* <tex>\[1 \leq n, k, w \leq 10^{6}.\]</tex>
h2. Exemplu
table(example). |_. nmult.in |_. nmult.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5 2 2 | 6 |
| 10 3 4 | 4 |
| 10 4 4 | 0
|
h3. Explicaţie
...
* <tex>\[n = 5, k = 2, w = 2\]</tex>.
** Există 6 mulţimi cu 2 elemente, astfel încât diferenţa între oricare 2 termeni consecutivi să fie cel puţin 2: <tex>\[\left \{ 1, 3 \right \}, \left \{ 1, 4 \right \}, \left \{ 1, 5 \right \}, \left \{ 2, 4 \right \}, \left \{ 2, 5 \right \}, \left \{ 3, 5 \right \}.\]</tex>
* <tex>\[n = 10, k = 3, w = 4\]</tex>.
** Există 4 mulţimi cu 3 elemente, astfel încât diferenţa între oricare 2 termeni consecutivi să fie cel puţin 4: <tex>\[\left \{ 1, 5, 9 \right \}, \left \{ 1, 5, 10 \right \}, \left \{ 1, 6, 10 \right \}, \left \{ 2, 6, 10 \right \}.\]</tex>
* <tex>\[n = 10, k = 4, w = 4\]</tex>.
** Nu există nicio mulţime de 4 elemente în care condiţiile să fie îndeplinite.
== include(page="template/taskfooter" task_id="nmult") ==
