Lista de probleme 1991

Cif-Oji6 este o imprimantă matriceală numită şi imprimantă cu ace, deoarece tipărirea se realizează prin impactul acelor capului de imprimare pe o bandă cu tuş.
Acele sunt aranjate într-o grilă dreptunghiulară formată din 5 rânduri de ace, pe fiecare rând aflându-se la distanţe egale câte 3 ace, aşa cum se observă în figura alăturată.
Prin acţionarea diferitelor combinaţii de ace din grilă, se defineşte forma fiecărei cifre ce permite tipărirea acesteia prin puncte, în felul următor:

De exemplu, cifra 2 va fi tipărită prin 11 puncte ca rezultat al acţionării a 11 ace din grilă: din primul rând de ace al grilei se vor acţiona toate cele 3 ace, din următorul rând doar acul din dreapta, apoi de pe următorul rând toate cele 3 ace, apoi acul din stânga de pe penultimul rând iar din ultimul rând toate cele 3 ace.

a) Ştiind că imprimanta Cif-Oji6 a tipărit numărul N, determinaţi care este cea mai mare cifră a numărul N pentru care s-a acţionat un număr minim de ace ale grilei.
b) Ştiind că imprimanta mai are tuş pe bandă doar pentru imprimarea a K puncte, determinaţi cel mai mare număr natural ce poate fi tipărit prin exact K puncte.

Fascinat de Egiptul Antic, Rareș vrea să construiască cât mai multe piramide din cartonașe pătratice identice. El are la dispoziție N cartonașe numerotate de la 1 la N, albe sau gri, așezate în ordinea strict crescătoare a numerelor.

• Prima piramidă o va construi folosind primele trei cartonașe. Baza piramidei va fi formată din cartonașele 1 și 2 așezate alăturat, peste care va așeza cartonașul 3 (vârful piramidei).
• A doua piramidă va avea baza formată din cartonașele 4, 5 și 6 așezate alăturat, deasupra cărora se vor așeza cartonașele 7 și 8, alăturate, peste care se va așeza cartonașul 9 (vârful piramidei).
• Mai departe, va construi în ordine piramidele complete cu bazele formate din 4 cartonașe (cu numerele de la 10 la 13), respectiv 5 cartonașe (cu numerele de la 20 la 24), 6 cartonașe (cu numerele de la 35 la 40) etc., cât timp va putea construi o piramidă completă. De exemplu, dacă Rareș are N=75 cartonașe atunci el va construi piramidele complete 1, 2, 3, 4 și 5 din imaginile următoare. Din cele 75 de cartonașe el va folosi doar primele 55 de cartonașe, deoarece ultimele 20 cartonașe nu sunt suficiente pentru a construi piramida 6, cu baza formată din 7 cartonașe.

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de cartonașe), X (reprezentând numărul unui cartonaș), K (reprezentând numărul de cartonașe albe), numerele celor K cartonașe albe c1, c2, …, cK și care să determine:

a) numărul P al piramidei complete ce conține cartonașul numerotat cu X;
b) numărul M maxim de piramide complete construite de Rareș;
c) numărul C de cartonașe nefolosite;
d) numărul A al primei piramide complete care conține cele mai multe cartonașe albe.

Gică şi Lică lucrează la o fabrică de jucării, în schimburi diferite. Anul acesta patronul fabricii a hotărât să confecţioneze şi mărţişoare. Mărţişoarele gata confecţionate sunt puse în cutii numerotate consecutiv.

Cutiile sunt aranjate în ordinea strict crescătoare şi consecutivă a numerelor de pe acestea.
Gică trebuie să ia, în ordine, fiecare cutie, să lege la fiecare mărţişor câte un şnur alb-roşu şi apoi să le pună la loc în cutie.

În fiecare schimb, Gică scrie pe o tablă magnetică, utilizând cifre magnetice, în ordine strict crescătoare, numerele cutiilor pentru care a legat șnururi la mărțișoare.

Când se termină schimbul lui Gică, Lică, care lucrează în schimbul următor, vine şi ambalează cutiile cu numerele de pe tablă şi le trimite la magazine. Totul merge ca pe roate, până într-o zi, când, două cifre de pe tablă se demagnetizează şi cad, rămânând două locuri goale. Lică observă acest lucru, le ia de jos şi le pune la întâmplare pe tablă, în cele două locuri goale. Singurul lucru de care ţine cont este acela că cifra 0 nu poate fi prima cifră a unui număr.

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de numere scrise pe tablă) şi c1, c2, …, cN (reprezentând numerele scrise, în ordine, pe tablă, după ce Lică a completat cele două locuri goale cu cifrele căzute) și care să determine:
a) cele două cifre care au fost schimbate între ele, dacă, după ce au completat locurile goale, acestea au schimbat șirul numerelor scrise de Gică;
b) numărul maxim scris pe tablă de Gică.

O clepsidră este un dispozitiv folosit pentru a măsura timpul. Clepsidra este alcătuită din două incinte de sticlă, conectate printr-un tub fin. Una dintre incinte este umplută cu nisip, acesta scurgându-se în cea de-a doua incintă, cu o viteză constantă. Clepsidra poate fi întoarsă, pentru a măsura o altă perioadă de timp.

Arheologii au descoperit un dispozitiv, pe care l-au denumit clepsidru, format din n clepsidre identice, suprapuse, numerotate de la 1 la n, prin care nisipul poate circula de la o clepsidră la alta datorită forţei gravitaţionale.

Studiind acest obiect, arheologii au constatat că :

• dispozitivul poate fi utilizat atât în poziţia 1, când clepsidrele sunt în ordinea 1, 2 ,…, n cu clepsidra n aşezată pe sol, cât şi în poziţia 2, când clepsidrele sunt în ordinea n, n-1,…, 1 cu clepsidra 1 aşezată pe sol;
• viteza de trecere a nisipului de la o incintă la alta, a aceleiaşi clepsidre, este de 1 bob de nisip/secundă, pentru toate clepsidrele, indiferent de poziţie;
• trecerea clepsidrului dintr-o poziţie în alta presupune răsturnarea acestuia şi reaşezarea boabelor de nisip;
• timpul de trecere a boabelor de nisip de la o clepsidră la alta este 0.

Arheologii studiază comportarea clepsidrului realizând două experimente diferite, după cum urmează:

a) Se aşează clepsidrul în poziţia 1, se introduc în incinta de sus a clepsidrei 1 un număr b de boabe de nisip şi se determină după câte secunde vor ajunge toate boabele de nisip în incinta de jos a ultimei clepsidre;
b) Se aşează clepsidrul în poziţia 1, se introduc în incinta de sus a clepsidrei 1 un număr b de boabe de nisip, apoi se aşează clepsidrul în k stări consecutive, o stare fiind caracterizată de valorile si şi pi , 1 ≤ i ≤ k, ce reprezintă numărul de secunde, respectiv poziţia, în care este menţinut nemişcat clepsidrul, iar la final se determină numărul de boabe de nisip din incintele fiecărei clepsidre.

Spre exemplu, dacă clepsidrul este format din n=2 clepsidre, iar în incinta de sus a primei clepsidre se introduc b=3 boabe de nisip, la primul experiment se va obţine valoarea 4.

La al doilea experiment se aşează clepsidrul în k=2 stări, caracterizate prin s1=3, p1=1; s_{2=1, p2=2.}

Numărul de boabe de nisip din clepsidre va evolua ca în figura alăturată.

Să se scrie un program care citeşte valorile n şi b, precum şi valorile k, si, pi , 1 ≤ i ≤ k, şi calculează valorile obţinute de arheologi la realizarea celor două experimente.

Jocul betaşah se joacă folosindu-se doar piese asemănătoare damelor clasicului şah, numite tot dame. Suprafaţa de joc are o formă triunghiulară şi este formată din N*(N+1)/2 pătrate identice dispuse pe N rânduri şi N coloane. Rândurile se numerotează de sus în jos, de la 1 la N. Coloanele se numerotează de la stânga la dreapta, de la 1 la N. Primul rând conţine un singur pătrat, al doilea rând conţine două pătrate alăturate,…, al N-lea rând conţine N pătrate alăturate, ca în suprafeţele de joc cu N=6 din figurile de mai jos. Din cele N*(N+1)/2 pătrate, K sunt gri, iar restul sunt albe. Poziţia fiecărui pătrat de pe suprafaţa de joc este dată de rândul şi coloana în care acesta este situat.

Pe suprafaţa de joc sunt aşezate D dame în D pătrate albe distincte, ocupându-le. Într-un pătrat alb poate fi aşezată o singură damă, iar într-un pătrat gri nu poate fi aşezată nicio damă. Poziţia unei dame pe suprafaţa de joc este dată de poziţia pătratului alb în care este aşezată dama.

Damele pot accesa orice pătrat alb neocupat situat pe direcţiile: verticală, orizontală sau diagonală, numerotate de la 1 la 8 în figura b). Accesul pe o direcţie se face trecând din pătrat alb în pătrat alb (doar pătrate albe neocupate) până la întâlnirea unui pătrat gri sau a unui pătrat alb ocupat de o altă damă sau până la terminarea suprafeţei de joc.

Numim pătrat accesibil orice pătrat alb neocupat (de pe suprafaţa de joc) care ar putea fi accesat de cel puţin una din cele D dame.

De exemplu, pentru suprafaţa de joc din figura c) numărul de pătrate accesibile (marcate cu X) de pe suprafaţă este 11; pentru suprafaţa de joc cu N=6, D=3 şi K=4 din figura d) numărul de pătrate accesibile de pe suprafaţă este 13. În figura e) sunt marcate cu X pătratele accesibile fiecărei dame de pe suprafaţa de joc din figura d).

Pătratele accesibile damei din rândul 3 şi coloana 2	Pătratele accesibile damei din rândul 5 şi coloana 2	Pătratele accesibile damei din rândul 5 şi coloana 4	Pătratele accesibile de pe suprafaţa de joc
Figura e)

Scrieţi un program care să citească numerele naturale N, D, K, poziţiile damelor şi ale pătratelor gri pe suprafaţa de joc şi care să determine:
a) numărul maxim M de pătrate albe conţinute de un rând al suprafeţei de joc;
b) numărul P de pătrate accesibile de pe suprafaţa de joc.

Considerăm o tablă de șah pătratică formată din 2n linii și 2n coloane, unde n este un număr natural nenul, formată din 2n*2n zone. Aceasta poate fi acoperită, cu excepția unei singure zone, cu piese în formă de L, fiecare piesă acoperind 3 zone. De exemplu, pentru n=2, o acoperire este următoarea, în care zona neagră este cea neacoperită de piese:

Pentru n dat, determinați o modalitate de acoperire a tablei cu piese, astfel încât să nu se suprapună piesele și să rămână o singură zonă neacoperită.

Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.

Roata are n cabine, numerotate de la 1 la n în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina 1 aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire 1 EUR şi poate cumpăra un număr oarecare de rotiri.

Cei p clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine i îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri ci, 1≤ i ≤ p, apoi se aşează la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet.

Să se scrie un program care, cunoscând numărul n de cabine al roţii, numărul p de clienţi, precum şi numărul de rotiri cumpărate de fiecare client, ci, 1≤ i ≤ p, să calculeze:

• suma totală încasată de administratorul roţii de la clienţi;
• ordinea în care coboară clienţii din roată;
• numărul cabinei din care coboară ultimul client.

Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrăţele de aceeaşi dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrăţele de gazon sunt numerotate de sus în jos cu numerele 1, 2, …, m, iar coloanele cu pătrăţele de gazon sunt numerotate de la stânga la dreapta cu numerele 1, 2, …, n. Din cauza tipului diferit de iarbă se ştie care dintre pătrăţele de gazon sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional a cu m linii şi n coloane, cu elemente 0 şi 1 (aij = 0 înseamnă că pătrăţelul aflat pe linia i şi coloana j este afectat de umbră, iar aij = 1 înseamnă că pătrăţelul aflat pe linia i şi coloana j nu este afectat de umbră). Fiecare elicopter are 3 roţi pe care se sprijină. Roţile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere.

Pentru a preciza poziţia unui elicopter pe teren este suficient să cunoaştem linia şi coloana vărfurilor ipotenuzei şi poziţia vârfului deasupra (codificată prin 1) sau dedesubtul ipotenuzei (codificată prin -1). Pentru exemplu, elicopterul din stânga sus este dat prin (1,1), (3,3) şi -1, cel din dreapta sus prin (1,9), (5,5) şi 1, cel din stânga jos prin (5,1), (6,2) şi 1, iar cel din dreapta jos prin (5,9), (6,8) şi 1.

Un elicopter se consideră că a aterizat greşit, dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrăţele afectate de umbră.

Administratorul terenului de fotbal doreşte să determine numărul N1 de elicoptere, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare: e1, e2, …, eN2, ştiind că există k elicoptere codificate prin numerele 1, 2, …, k.

Scrieţi un program care să determine, pentru fişierul cu datele din enunţ: numărul de elicoptere N1, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare, precedate de numărul lor N2.

Să se scrie un program care determină minimul a trei numere întregi.

Se dau două șiruri cu câte n, respectiv m elemente. Dacă înmulțim fiecare element din primul șir cu fiecare element din al doilea șir, să se afle câte produse sunt mai mici decât p.