Lista de probleme 5

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Gigel are n bile și k cutii. În câte moduri poate plasa Gigel bilele în cutii, știind că pot rămâne și cutii goale.

Gigel are n bile și k cutii. În câte moduri poate plasa Gigel bilele în cutii, știind că în fiecare cutie trebuie plasată cel puțin o bilă.

Ilinca este o fetiţă căreia îi place foarte mult să deseneze; ea a făcut multe desene pe care le-a numerotat de la 1 la d şi apoi le-a multiplicat (toate copiile poartă acelaşi număr ca şi originalul după care au fost făcute). În vacanţă s-a hotărât să-şi deschidă propria expoziţie pe gardul bunicilor care are mai multe scânduri; pe fiecare scândură ea aşează o planşă (un desen original sau o copie). Ilinca ţine foarte mult la desenele ei şi doreşte ca fiecare desen să apară de cel puţin k ori (folosind originalul şi copiile acestuia). Ilinca se întreabă în câte moduri ar putea aranja expoziţia. Două moduri de aranjare sunt considerate distincte dacă diferă cel puţin prin numărul unei planşe (de exemplu: 2 1 3 3 este aceeaşi expoziţie ca şi 2 3 1 3, dar este diferită de 2 1 3 1 şi de 1 3 3 1).

Cunoscând n numărul de scânduri din gard, d numărul desenelor originale şi k numărul minim de apariţii al fiecărui desen, să se determine în câte moduri poate fi aranjată expoziţia, ştiind că Ilinca are la dispoziţie oricâte copii doreşte.

Fie un șir a de N numere întregi. Trebuie construit un nou șir b (tot cu N elemente) astfel:

  • dacă \( {a}_{i}>0 \), atunci \( {b}_{i}={a}_{i} \)
  • dacă \( {a}_{i}=0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă
  • dacă \( {a}_{i}<0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă cu excepția lui \( -{a}_{i} \)

Se garantează că \( {a}_{1} \) și \( {a}_{N} \)au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă.

Știindu-se șirul a, să se calculeze numărul de moduri de a forma șirul b astfel încât acesta să fie crescător (nu neapărat strict). Deoarece acest număr poate fi foarte mare, se va afișa doar restul împărțirii la 1.000.000 007.

#3703 Potter

În Hogwarts există o tablă de șah cu N linii și M coloane. Harry Potter a găsit plasate, de către Hagrid, T ture care apără fiecare linia și coloana pe care este așezată. El trebuie să plaseze în siguranță K pioni pe tablă, adică fără ca vreunul dintre ei să fie atacat de vreo tură. Tabla de șah din Hogwarts este specială deoarece în cadrul unei celule pot fi plasați chiar și mai mulți pioni simultan! Cunoscând toate aceste reguli, ajutați-l pe Harry Potter să determine în câte modalități poate plasa în siguranță toți cei K pioni pe tabla de șah.