Lista de probleme 6

Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câştigă existența ca zugrav.

Roberto a primit sarcina de a zugrăvi un zid având lungimea n metri şi înălţimea un metru. Pentru aceasta are la dispoziţie m zile. În fiecare zi i, el acoperă cu un singur strat de vopsea o porţiune compactă de înălțime un metru și de lungime l[i] metri, începând de la distanţa d[i] metri faţă de capătul din stânga al zidului.

Roberto ştie din experienţă că fiecare porţiune de zid trebuie acoperită cu cel puţin K straturi de vopsea pentru ca stratul final de vopsea să aibă consistenţa dorită. Din nefericire, firea lui de artist nu i-a permis să-şi poată planifica munca în mod optim, astfel că la capătul celor m zile de efort, Roberto a constatat că zidul are porţiuni pe care le-a acoperit de mai mult de k ori şi alte porţiuni pe care le-a acoperit de mai puţin de k ori.

Pentru a recupera în proprii săi ochi dar mai ales în ochii şefului de echipă, el trebuie să afle mai întâi suprafaţa totală a tuturor porţiunilor de zid care mai trebuie zugrăvite.

Cunoscând lungimea zidului n, numărul de zile m şi porţiunile compacte pe care le zugrăveşte în fiecare zi, determinaţi suprafaţa totală a zidului care mai trebuie zugrăvită.

Fie n și p două numere naturale.

Notăm cu A(n,p) mulțimea tuturor numerelor naturale cu proprietățile :

• sunt mai mari sau egale cu 2 și mai mici sau egale cu n;
• descompunerea lor în factori primi conține doar exponenți mai mici sau egali cu p.

Să se scrie un program care citește două numere naturale n și p și determină cardinalul mulțimii A(n,p).

Aţi auzit despre Nessie? Este un pleziozaur misterios care trăieşte în adâncurile lacului Loch Ness din munţii Scoţiei. Cu mulţi ani în urmă el a fost zărit pentru prima oară la suprafaţa lacului, iar de atunci, spre desfătarea turiştilor, el îşi face apariţia în mod periodic.

Nessie ştie de la managerii Loch Ness care este programul de vizitare a lacului pentru un interval de N zile. Mai exact, el cunoaşte datele primei și ultimei zile de şedere în preajma lacului pentru fiecare turist.

Contractul pe care Nessie l-a semnat cu managerii prevede faptul că fiecare dintre turişti trebuie să aibă posibilitatea să-l zărească, însă doar de departe şi doar o singură dată, deoarece Nessie intenţionează să rămână în continuare misterios. Pot exista zile fără turişti şi în aceste zile Nessie profită de fiecare dată ca să iasă la suprafaţa lacului.

Cunoscând prima şi ultima zi de şedere pentru fiecare turist, şi numărul total de zile prevăzute în contract, determinaţi numărul maxim de ieşiri la suprafaţa lacului, pe care Nessie le poate face, astfel încât fiecare turist să-l zărească o singură dată.

Fie A = (a[1],a[2],…,a[N]) o permutare a mulțimii {1,2,…,N}.

Permutarea A o numim K-swap dacă prin aplicarea algoritmului de sortare bubble-sort sunt necesare exact K swapuri (interschimbări) pentru ca aceasta să devină permutarea identică.
Reamintim algoritmul bubble-sort:

do {   
    ok = 1;    
    for ( i = 1; i < N; i ++ )      
        if ( a[i] > a[i+1] ){        
             swap(a[i], a[i+1]);   
             ok = 0;   
        }
}while( ok == 0 );          

Pentru N și K dat să se determine numărul de permutări K-swap ale mulțimii {1,2,…,N}.

Manole este extrem de răcit. Din această cauză a mers la medicul de familie care l-a sfătuit urmeze un tratament cu N pastile, din care trebuie să ia în fiecare zi câte o jumătate. A cumpărat de la farmacie o cutie în care se aflau exact N pastile, fiecare dintre ele având pe suprafață o dungă care marchează jumătatea ei.

Manole începe să își ia tratamentul și constată că poate proceda doar astfel:

• scoate din cutie o pastilă întreagă din care folosește, în ziua respectivă, doar jumătate din ea, iar jumătatea rămasă o pune înapoi în cutie;
• scoate din cutie o jumătate de pastilă, rămasă din una din zilele anterioare, pe care o folosește în ziua respectivă.

Scrieți un program care determină numărul de posibilități în care poate lua toate cele N pastile, procedând după procedeul descris mai sus.

Victor are la dispoziție multe cuburi din lemn, toate de aceeași dimensiune, fiecare fiind colorat cu una din culorile 0, 1, 2, …, 9. El a inventat un joc sub forma unui algoritm:

• Pasul 0 – Se inițializează variabila X cu zero.
• Pasul 1 – Se aleg la întâmplare un număr de cuburi și se formează cu ele un șir. Cuburile din șir sunt lipite unul de altul.
• Pasul 2 – Dacă toate cuburile din șir au aceeași culoare, atunci se afișează valoarea variabilei X și jocul se oprește. În caz contrar se trece la pasul 3.
• Pasul 3 – Se alege o culoare C și apoi toate cuburile de culoarea C se elimină din șir. Locurile cuburilor eliminate rămân temporar libere.
• Pasul 4 – Orice cub din șir va fi deplasat spre stânga lui, cât timp pozițiile vecine sunt libere. Se mărește X cu 1 la fiecare deplasare cu o poziție. Operațiile de deplasare se încheie când nu se mai pot efectua mutări spre stânga. Apoi se revine la pasul 2.

Se consideră un șir cu cel puțin două elemente reprezentând culorile cuburilor din șir. Se cere să se calculeze valoarea maximă pe care o poate avea X.