Lista de probleme 46

Să se calculeze câte numere de n cifre au gradul de frumusțe k.

Le Quack vrea să bombardeze un oraș având N bombe numerotate de la 1...N. Dacă el detonează bombă cu valorea i atunci va putea să detoneze doar bombe încă nedetonate cu valori mai mici decât i. În cazul în care nu mai există astfel de bombe , poate detona orice bombă nedetonata. Le Quack va da numărul N și vrea să îi spuneți în câte moduri poate detona toate cele N bombe după regulă descrisă anterior.

După ce Julius Caesar l-a învins pe Pompey în bătălia de la Pharsalus , acesta decide să țină un festin în cinstea soldaților săi loilai . El are q scenarii posibile pt oaspeți definite printr o pereche (n,k) care înseamnă că fiecare dintre cei n invitați pot alege unul dintre cele k feluri de mâncare . Deoarece Julius Caesar a plătit cei mai buni bucătari pentru a prepara mancarea , el își dorește ca fiecare fel de mâncare să fi fost ales de minimum un invitat. O configurație este un șir de n numere a , al i-lea soldat a ales felul a(i) . Câte configurații distincte există care să îndeplinească cerințele marelui Julius Caesar ? Două șiruri sunt distincte dacă diferă prin cel puțin o poziție.

Azi este ziua secvenței! Profesoara de mate a scris câteva secvențe pe tablă, fiecare având N numere distincte cuprinse între 1 și N, și le-a spus studenților că aceste secvențe au o proprietate specială. După o analiză atentă, Deni, una din studente, a ghicit corect proprietatea. Toate secvențele de pe tablă au cel puțin o pereche de numere adiacente de forma (x, x+1). Deni a fost așa de fericită încât a denumit acest tip de secvențe drăguțe. Scrieți programul care pentru un N dat trebuie să-i spună lui Deni care este numărul de secvențe drăguțe. Acest număr poate fi foarte mare, așa că trebuie calculat modulo M.

Aflându-se la moșia lui Pascalopol, Otilia este fascinată de vasta întindere de pământ pe care bărbatul o deține. Cum Pascalopol este un om darnic și îi face toate poftele Otiliei, încă de când era mică, acesta îi dăruiește tinerei o bucată de pământ de dimensiune N*M împărțită în parcele de dimensiune 1*1, dispuse pe N linii și M coloane (numerotate de la 1 la N, respectiv de la 1 la M). Pentru că Felix este gelos pe Pascalopol și nu suportă ca Otilia să-i ofere atât de multă atenție, tânărul i-a pus următoarea întrebare moșierului, vrând prin aceasta să-i arate că el este net superior din punct de vedere informatic:

“- Dacă eu plec din parcela (1,1), iar calul meu poate face un salt cu orice lungime între 1 și K la sud (linia crește) sau la est (coloana crește), în câte moduri pot ajunge în parcela (L,C), ținând cont că nu pot păși pe o parcelă care conține o groapă.”. Pentru că numărul poate fi foarte mare, Felix se mulțumește doar cu restul acestuia la împărțirea cu 1.000.000.007.Cum Pascalopol nu le are cu calculatoarele, iar aceasta este clar o problemă de Informatică, moșierul vă cere ajutorul și vă va oferi în schimb 100 de puncte.

RAU-Gigel se pregătește pentru admiterea la facultate. Curios din fire, el împrumută niște cursuri de la un prieten student, de unde află despre limbajele formale, gramatici, automate finite, expresii regulate și multe alte lucruri interesante. Găsește acolo și o problemă:

Se consideră un alfabet X format din N simboluri (diferite două câte două). Pe mulțimea X este definită o relație de ordine totală (să o numim lexicografică) astfel: orice două elemente a și b alegem din X (a diferit de b), avem fie a<b, fie b<a. Câte cuvinte se pot forma cu simboluri din alfabetul X astfel încât simbolurile prezente în cuvânt să fie în ordine strict crescătoare (de la stânga spre dreapta) și să nu existe în cuvânt două simboluri consecutive lexicografic?