Lista de probleme 56

Se dă o matrice de rebus cu n linii și m coloane. Fiecare celulă conține unul dintre caracterele:

• '+' – celulă blocată (nu poate conține literă)
• '-' – celulă liberă (trebuie completată cu o literă)

De asemenea, se dă o listă de W cuvinte (formate doar din litere mari A-Z) care trebuie completate în rebus.

Un cuvânt poate fi plasat:

• pe orizontală (în aceeași linie), sau
• pe verticală (în aceeași coloană),

într-un segment maximal de celule '-' consecutive (numit slot). Lungimea cuvântului trebuie să fie egală cu lungimea slotului.

Două cuvinte se pot intersecta (o celulă poate aparține atât unui slot orizontal, cât și unuia vertical), dar în acest caz litera rezultată în acea celulă trebuie să coincidă pentru ambele cuvinte.

Fiecare cuvânt din listă trebuie folosit exact o singură dată.

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale.

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale distincte.

Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale pare.

Se dă un număr natural n. Determinați, în ordine lexicografică, toate modalitățile de a-l scrie pe n ca sumă de numere naturale impare distincte.

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile.

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine în câte moduri se poate plăti integral o sumă dată S cu bancnotele disponibile, astfel încât să se folosească cel puțin o bancnotă de fiecare tip.

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile, astfel încât să se folosească cel puțin o bancnotă de fiecare tip.

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile, știind că se pot folosi oricâte bancnote de orice tip.

Se dă un număr natural nenul n. Să se determine toate modalităţile distincte de descompunere a numărului n în sumă de 3 şi 5.