Fişierul intrare/ieşire:nmult.in, nmult.outSursăONI 2015, clasa a 10-a
AutorCiprian ChescaAdăugată deharababurelPuscas Sergiu harababurel
Timp execuţie pe test0.05 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nmult

Se consideră trei numere naturale nenule n, k şi w.

Cerinţă

Să se scrie un program care determină numărul m al mulţimilor de forma \[\left \{ x_{1}, x_{2}, ..., x_{k} \right \}\], având ca elemente numere naturale nenule, ce satisfac simultan condiţiile:

  • \[1 \leq x_{1} < x_{2} < ... < x_{k} \leq n\]
  • \[x_{i+1} - x_{i} \geq w, 1 \leq i \leq k-1\]

Date de intrare

Fişierul de intrare nmult.in conţine pe prima linie trei numere naturale nenule n, k, w separate prin câte un spaţiu, cu semnificaţia de mai sus.

Date de ieşire

În fişierul de ieşire nmult.out va conţine pe prima linie restul împărţirii numărului m la 666013.

Restricţii

  • \[1 \leq n, k, w \leq 10^{6}.\]

Exemplu

nmult.innmult.out
5 2 26
10 3 44
10 4 40

Explicaţie

  • \[n = 5, k = 2, w = 2\].
    • Există 6 mulţimi cu 2 elemente, astfel încât diferenţa între oricare 2 termeni consecutivi să fie cel puţin 2: \[\left \{ 1, 3 \right \}, \left \{ 1, 4 \right \}, \left \{ 1, 5 \right \}, \left \{ 2, 4 \right \}, \left \{ 2, 5 \right \}, \left \{ 3, 5 \right \}.\]
  • \[n = 10, k = 3, w = 4\].
    • Există 4 mulţimi cu 3 elemente, astfel încât diferenţa între oricare 2 termeni consecutivi să fie cel puţin 4: \[\left \{ 1, 5, 9 \right \}, \left \{ 1, 5, 10 \right \}, \left \{ 1, 6, 10 \right \}, \left \{ 2, 6, 10 \right \}.\]
  • \[n = 10, k = 4, w = 4\].
    • Nu există nicio mulţime de 4 elemente în care condiţiile să fie îndeplinite.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?