Lista de probleme 7

Fie N și T două numere naturale.

Să se determine numărul soluțiilor diferite S, ale ecuației \( x_1 \cdot x_2 \cdot \cdots \cdot x_N = T \), în mulțimea numerelor naturale.

Anul 2154, undeva pe luxurianta planetă Pandora.

Aici coloniștii RDA (Resources Development Administration) doresc să-și stabilească o bază stelară pentru a exploata rezervele naturale de unobtainium, un minereu rar și prețios aflat din belșug pe munții plutitori (Hallelujah Mountains), munți ce plutesc lent purtați de curenții magnetici asemănător aisbergurilor în mare, pe suprafața planetei formată din gaz lichid.

Pentru prospectarea și exploatarea zăcămintelor de minereu este necesară cartografierea suprafeței planetei și întocmirea unei hărți digitizate reprezentate sub forma unui tablou bidimensional. Astfel, regiunea de interes geologic este împărţită în N×N pătrate teritoriale identice (zone), fiecare zonă fiind identificată prin tripletul (x,y,c), unde (x,y) reprezintă coordonatele zonei teritoriale (x – linia, y – coloana), iar c cota (înălțimea). Între zonele ocupate de munții există vaste zone de gaz lichid, zone care au cota 0.

Pentru recoltarea și transportul unobtainiumului către baza stelară coloniștii RDA folosesc spice-harvesters, nave speciale cu aterizarea pe verticală.

Aterizarea pe munții plutitori reprezintă o adevărată provocare pentru piloții RDA. Pentru a putea ateriza, piloții trebuie să identifice un sector plat (platformă de aterizare), platformă care să respecte designul trenului de aterizare al navelor (vezi figura alăturată). Platforma are forma unui pătrat de latură k ce este format din k*k zone teritoriale, astfel (k*k)-4 zone au aceeași cotă, iar cele 4 colțuri ale pătratului au cota strict mai mică decât restul zonelor pătratului.

Cunoscând descrierea a M zone teritoriale ce alcătuiesc munții plutitori să se determine coordonatele colțului stânga-sus al platformelor de aterizare pentru munții plutitori care permit aterizarea.

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Există N candidați la alegerile prezidențiale. Fiecare dintre cei N candidați știe exact cu cine va vota. O persoană poate vota o singură altă persoană (se poate vota și pe sine). Scopul tău este să creezi confuzie între candidați. Pentru asta, ai dreptul să le interzici la cel mult K dintre candidați să participe. Atunci când un candidat este eliminat, toți candidații care ar fi votat cu el votează cu persoana cu care ar fi votat candidatul eliminat (deoarece au încredere în decizia sa). Dacă cel eliminat ar fi votat cu sine sau era INDECIS, toți cei care ar fi votat cu el devin INDECIȘI. Pentru fiecare K de la 1 la N, se cere numărul minim de candidați “deciși” pe care îi putem avea dacă am elimina K dintre candidați.

Pe șoseaua care duce spre intrarea în oraș se află n autovehicule, dintre care m
sunt autovehicule de gabarit redus, pe care le vom numi în continuare autoturisme, iar restul sunt de gabarit mare și le vom numi camioane. Orașul are o șosea ocolitoare, numită popular centură. Camioanele trebuie să ocolească orașul
trecând în mod obligatoriu pe drumul de centură. Autoturismele pot continua drumul pe șoseaua care intră în oraș sau pot ocoli orașul intrând pe șoseaua de centură. Pe centură, camioanele circulă cu viteză redusă îngreunând traficul.

De aceea s-a impus restricția R: nu vor fi admise pe drumul de centură coloane formate din mai mult decât k camioane consecutive.

Cunoscând n, k și distribuția autovehiculelor pe șosea, să se determine două numere naturale V și T, unde V reprezintă numărul de variante de dirijare a traficului astfel încât să fie respectată restricția R, iar T reprezintă numărul minim de autoturisme care trebuie să fie deviate pe drumul de centură pentru a se respecta aceeași restricție R.

Se consideră un șir de numere naturale a[1], a[2], …, a[n] așezate circular. Acest lucru înseamnă că a[1] are ca vecini numerele a[n] și a[2], iar a[n] are ca vecini pe a[n-1] și a[1]. Se consideră de asemenea un număr natural K.

Să se determine suma maximă care se poate obține din exact K secvențe nevide, disjuncte și ne-vecine.

În țara lui Oblio toate lucrurile sunt sub formă de triunghi. Chiar și fotografiile sunt sub formă de triunghi. Fotografiile sunt formate din pixeli, care evident, la rîndul lor sunt triunghiuri ca în figura de mai jos.

Fotografiile sunt alb negru și fiecare pixel este identificat prin rândul pe care se găsește și prin poziție, adică al câtelea triunghi este în rândul respectiv numărând de la 1, d­e la stânga la dreapta. Fiecare pixel are culoarea alb sau negru. Fiecare pixel are dimensiunea 1, dar mai mulți pixeli vecini pot forma triunghiuri cu vârful în sus cu laturi de diferite lungimi. În figura din dreapta avem 3 triunghiuri de dimensiune 1 (rândul 2 poziția 1, rândul 3 poziția 1, rândul 3 poziția 3) și un triunghi de dimensiune 2 (cu colțurile: în rândul 2 poziția 1, rândul 3 poziția 1 și rândul 3 poziția 3).

Se știe că în fotografie sunt n rânduri și m pixeli albi, fiecare pixel fiind identificat prin rând și poziție.

Se cere să se determine, pentru p lungimi de laturi date, câte triunghiuri de culoare neagră (adică pline numai cu pixeli de culoare neagră) și cu vârful în sus se găsesc în fotografie pentru fiecare lungime.