Lista de probleme 7

Se consideră algoritmul:

citeşte  k , n;
s = 0;
for (i1 = 1 ; i1 ≤ k ; i1++)
  for (i2 = 1 ; i2 ≤ i1 ; i2++)
    for (i3 = 1 ; i3 ≤ i2 ; i3++)
      ........................................
        for (in = 1 ; in ≤ in-1 ; in++)
          s = s + in;
scrie s;
stop.

Să se scrie un program care implementează algoritmul de mai sus.

Mihai a primit de ziua sa un joc de şah special. Tabla jocului are forma pătrată, de dimensiune N dar unele poziţii sunt marcate ca obstacole şi ele nu pot fi ocupate cu piese. În plus, jocul său are o singură piesă, numită “nebun”. Două poziţii pe tablă sunt desemnate ca poziţie iniţială şi poziţie finală. Mihai vrea să determine o modalitate de a deplasa nebunul, cu un număr minim de mutări, astfel încât acesta să ajungă din poziţia iniţială în poziţia finală. Mihai va respecta regulile de mutare a nebunului la jocul de şah, adică din poziţia curentă nebunul se poate muta doar pe diagonală, în oricare dintre cele 4 direcţii, oricâte poziţii deodată dar fără a sări peste obstacole. În plus, Mihai are voie la o excepţie de la această regulă: îi este permis să execute cel mult două mutări după regula de avansare a calului pe tabla de şah.

Dată fiind configuraţia tablei de şah precum şi poziţiile iniţială şi finală ale piesei, se cere determinarea numărului minim de mutări pentru a deplasa piesa între cele două poziţii.

Nici nu ştiţi cât de greu este să fii funcţionar. Zeci de rapoarte de întocmit, sute de cereri ce trebuiesc redactate, mii de semnături, sute de mii de hârtii de înregistrat. Circuitul nesfârşit al hârtiilor este cunoscut sub numele de birocraţie. În instituţia noastră sunt angajaţi N funcţionari, numerotaţi de la 1 la N.

Fiecare dintre ei trebuie să înregistreze un număr considerabil de documente. Acesta este motivul pentru care în fiecare zi, încă de la prima oră, funcţionarii se aşază la coadă la secretariat, în ordine de la 1 la N. Modalitatea de înregistrare a documentelor este următoarea: funcţionarul se aşează la coadă, aşteaptă până îi vine rândul, înregistrează un singur document, apoi, dacă mai are alte documente se reaşează la coadă, ş.a.m.d. Din păcate, serviciul de secretariat înregistrează într-o zi cel mult M documente.

Dacă se cunoaşte, pentru fiecare din cei N de funcţionari, numărul de documente pe care trebuie să le înregistreze la secretariat, determinaţi numărul de ordine al funcţionarilor care nu au reuşit semnarea tuturor documentelor până la încheierea zilei de muncă.

Bujorel s-a apucat de pomicultură şi a însămânţat un arbore (graf conex aciclic) cu N noduri, fiecare nod având o culoare dată dintr-un interval [1, K]. Acum, după ce arborele a crescut, el doreşte să ştie, pentru fiecare culoare, suma distanţelor dintre toate perechile de noduri ale arborelui ce au culoarea respectivă. Distanţa dintre două noduri se defineşte ca fiind numărul de muchii de pe drumul dintre cele două noduri. Deoarece Bujorel a folosit foarte mult îngrăşământ la plantarea arborelui, acesta a crescut foarte mult şi voi trebuie să scrieţi un program care calculează suma distanţelor dintre nodurile cu aceeaşi culoare.

Mircea şi Andrei sunt pasionaţi de construcţiile realizate din piese Lego. Fiecare dintre ei are un set format din N cuburi negre de latură 1 şi mai multe piese paralelipipedice de culoare albă cu care va construi o clădire de formă paralelipipedică având baza un pătrat de latură 2 şi înălţimea H.

Toate piesele de culoare albă au înălţimea 2 iar celelalte laturi egale cu 1 şi nu pot fi răsturnate în momentul în care se asamblează pentru a construi clădirea. Aceasta va conţine întotdeauna toate piesele negre din set şi atâtea piese de culoare albă cât e necesar pentru finalizarea ei.

În momentul finalizării clădirii, cei doi băieţi observă că deşi au folosit aceleaşi seturi de piese, cele două clădiri sunt diferite deoarece combinaţiile de culori alb-negru de pe faţadele (nordică, sudică, vestică sau estică) clădirilor nu arată la fel.

Scrieţi un program care să calculeze numărul T de clădiri diferite care se pot construi cu piesele date, ştiind că două clădiri sunt identice dacă sunt îndeplinite simultan următoarele condiţii:

• faţada dinspre nord a uneia este identică cu faţada dinspre nord a celeilalte;
• faţada dinspre est a uneia este identică cu faţada dinspre est a celeilalte;
• faţada dinspre sud a uneia este identică cu faţada dinspre sud a celeilalte;
• faţada dinspre vest a uneia este identică cu faţada dinspre vest a celeilalte.

Programul va afişa restul împărţirii numărului T la 666013.

Jocul cmin constă în a găsi o strategie pentru a deplasa un anumit număr de jetoane identice pe o tablă pătratică, în scopul obţinerii unei configuraţii finale, cu un cost minim.

Tabla are n*n celule, aflate la intersecţia a n rânduri numerotate de la 1 la n de sus în jos şi a n coloane, numerotate de la 1 la n de la stânga spre dreapta. Numărul n este întotdeauna par.

La momentul iniţial al jocului, pe tablă se găsesc k jetoane în poziţii cunoscute. Fiecare jeton poate fi deplasat doar pe verticală, din celula iniţială într-o celulă finală neocupată de un alt jeton. Un jeton poate fi deplasat chiar dacă între poziţia sa iniţială şi cea finală există celule ocupate de către alte jetoane.

Costul deplasării unui jeton pe verticală, din celula curentă într-o celulă adiacentă este 1 (o unitate). Un jeton poate fi mutat de mai multe ori. Jucătorul decide ordinea deplasării jetoanelor. Acesta poate să mute 0, 1 sau chiar toate jetoanele pentru a termina jocul cu un cost total minim. Costul total este suma costurilor deplasării tuturor jetoanelor.

Jocul cmin se termină când diferenţa în valoare absolută dintre numărul de jetoane care se află pe primele n/2 rânduri (cele de sus) şi numărul de jetoane care se găsesc pe ultimele n/2 rânduri (cele de jos), este minimă.

Cunoscând numărul n de rânduri şi de coloane ale tablei şi poziţiile iniţiale ale jetoanelor, determinaţi costul total minim necesar pentru deplasarea acestora, astfel încât diferenţa în valoare absolută dintre numărul jetoanelor care se vor găsi în final pe primele n/2 rânduri şi numărul jetoanelor care se vor găsi pe ultimele n/2 rânduri, să fie minimă.

Pentru a putea ţine evidenţa mai uşor, administratorul unui magazin întocmeşte o listă cu produsele care se găsesc în magazin la începutul zilei. El scrie numele produselor, folosind cuvinte de aceeaşi lungime, formate doar din literele mici ale alfabetului englez. Îndată finalizată lista, el îi asociază un cod reprezentând cel mai mic cuvânt în sens lexicografic, obţinut prin preluarea unei litere din fiecare nume de produs, în ordinea în care acestea au fost scrise pe listă.

El observă că acest cod poate fi obţinut în mai multe moduri. Doreşte însă să identifice varianta în care literele alese sunt cât mai apropiate, altfel spus, distanţa, reprezentând numărul de poziţii, între poziţia cea mai mică şi poziţia cea mai mare pe care sunt plasate caracterele alese, este minimă. De exemplu:

Pentru lista care cuprinde produsele de mai jos: