Manual Facultate Informatica 08.07.2015

7/21/2019 Manual Facultate Informatica 08.07.2015

http://slidepdf.com/reader/full/manual-facultate-informatica-08072015 1/59

Ana Intuneric

Ana Întuneric1

Manual de pregătire pentru facultatea de informatică

Ana Întuneric



Ana Intuneric

Ana Întuneric2

Cuprins

Algoritmi de bază și idee ................................................................................................................ 4 Covor ............................................................................................................................................................................... 4

Numerus. ........................................................................................................................................................................ 5

Ciurul lui Eratostene....................................................................................................................... 6 descompunere ................................................................................................................................................................ 7

numarare ........................................................................................................................................................................ 7

extraprime ...................................................................................................................................................................... 7

secvenţe .......................................................................................................................................................................... 8

factorial .........................................................................................................................................................................10

nrprime .........................................................................................................................................................................11

Descompunere în factori primi .....................................................................................................................................11

Vectori-teorie ................................................................................................................................................................12

Cautare binara ..............................................................................................................................................................13

Numarare triunghiuri ....................................................................................................................................................14

Factorial ........................................................................................................................................................................15

Transport ......................................................................................................................................................................16

secventa ........................................................................................................................................................................17

Generare submultimi utilizand vectorul caracteristic ..................................................................................................18

235 ................................................................................................................................................................................18

maxD .............................................................................................................................................................................20Reuniune de intervale ...................................................................................................................................................21

tabara ............................................................................................................................................................................22

moretime ......................................................................................................................................................................23

sport ..............................................................................................................................................................................25

bal .................................................................................................................................................................................26

Carti ...............................................................................................................................................................................27

baze ...............................................................................................................................................................................28

Panglica .........................................................................................................................................................................29

pluton ............................................................................................................................................................................29

buline ............................................................................................................................................................................31

Numere mari .................................................................................................................................. 32 Suma a doua numere mari ...........................................................................................................................................32

Inmultirea unui numar mare cu un numar mic ............................................................................................................33

Inmultirea unui numar mare cu un numar mare ..........................................................................................................33

Scaderea a doua numere mari ......................................................................................................................................33Impartirea unui numar mare la un numar mic .............................................................................................................33

Restul unui numar mare la un numar mic ....................................................................................................................33



Ana Intuneric

Ana Întuneric3

next .............................................................................................................................................................................. 33

Idee ................................................................................................................................................. 34 politic............................................................................................................................................................................ 34

nasturi .......................................................................................................................................................................... 36

Generare tablou ........................................................................................................................................................... 37

Paranteze ..................................................................................................................................................................... 38

Selecție ......................................................................................................................................................................... 38

triunghi ......................................................................................................................................................................... 39

expresie ........................................................................................................................................................................ 40

Urmatoarea permutare lexicografica .......................................................................................................................... 41

Elementul majoritar ..................................................................................................................................................... 42

maxp ............................................................................................................................................................................. 42

Matrice ............................................................................................................................................ 44

Păianjen ........................................................................................................................................................................ 44Maximum Sum. ............................................................................................................................................................ 44

cladiri ............................................................................................................................................................................ 45

cartele .......................................................................................................................................................................... 47

Tehnica Greedy ............................................................................................................................. 50 Problema spectacolelor_1 ........................................................................................................................................... 50

Problema programarii spectacolelor_2 ....................................................................................................................... 51

reactivi .......................................................................................................................................................................... 52

Bere .............................................................................................................................................................................. 53

Depozit ......................................................................................................................................................................... 55

Şiruri de caractere ......................................................................................................................... 55 TEXT.............................................................................................................................................................................. 55

comp ............................................................................................................................................................................ 57



Ana Intuneric

Ana Întuneric4

CovorBunica Marei țese un covor. Mara urmărește cu mareatenție modelul și încearcă să-l reconstituie pe caietul dematematică. Modelul este format din romburi. Primul romb,de indice 1, are latura formată din două pătrățele, al doilearomb, de indice 2, are latura formată din trei pătrățele etc.Un romb de indice i are latura formată din i+1 pătrățele. Romburile sunt unite, consecutiv, ca în exemplul dinimaginea alăturată. Săgețile indică sensul în care bunicațese covorul. Ca să nu uite modelul, Mara scrie pe caiet, î ncepând cu 1,numere consecutive care să indice modul în care țese bunica covorul. În exemplul următor este reprezentat modul în care se țese un model format din patru romburi. Cerinţe Cunoscându-se numerele n și k să sedetermine:

1. numărul maxim de rombur i complete carepot forma modelul unui covor, descris cuajutorul unui șir format din maximum n numere naturale consecutive (primulnumăr din șir fiind 1);

2. cel mai mic indice al unui romb ce conținenumărul k.

Date de intrareFişierul de intrare covor.in conţine pe prima linie, separate prin spațiu, două numere naturale: n (reprezentând numărul maxim de numere consecutive utilizate la descrierea unui model) și k (reprezentândun număr din șirul celor n numere consecutive). Linia a doua conţine una dintre valorile 1 sau 2 reprezentândcerinţa 1, dacă se cere determinarea numărului maxim de romburi complete care pot forma modelul unui

covor descris cu ajutorul unui șir format din maximum n numere, respectiv cerinţa 2, dacă se ceredeterminarea celui mai mic indice al unui romb ce conține numărul k. Date de ieşire Fişierul de ieşire covor.out conţine pe prima linie o valoarea naturală reprezentând numărul maxim deromburi complete care pot forma modelul unui covor, descris cu ajutorul unui șir format din maximum n numere, dacă cerinţa a fost 1, respectiv un număr natural reprezentând cel mai mic indice al unui romb ceconține numărul k, dacă cerinţa a fost 2.Restricţii și precizări

4 ≤ n,k ≤ 999999999; 1≤k≤n Dacă numărul k nu se află pe niciunul dintre romburile complete ce pot fi construite folosind maximum

n numere, atunci răspunsul de la cerința 2 este 0.

Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă acerinţei 2 se acordă 70% din punctaj.Exemple

covor.in covor.out Explicaţii 40 321

4 Cel mai mare număr de romburi ce pot forma un model descris cu maximum40 de numere este 4.

40 322

3 Numărul 32 se află pe cel de-al treilea romb.

37 72

2 Numărul 7 se află pe cel de-al doilea și pe cel de-al treilea romb. Cel mai micindice al unui romb ce conține numărul 7 este 2.

14 122

0 Numărul 12 nu se află pe niciunul dintre cele două romburi ce pot forma unmodel descris cu maximum 14 de numere.

Se observă că primul romb este format din 4 pătrătele, al doilea este format din 8 pătrățele, … rombul cuindicele i este format din 4i pătrățele. Atunci când formeză un covor, romburile se suprapun =>un model format din r romburi va fi descris printr-unșir format din 4x1+4x2+....+4xr -(r-1) = 4r(r+1)/2-(r-1)=2r(r+1)-(r-1) numere.Pentru determinarea numărului maxim de romburi complete care pot forma modelul unui covor, descris cu

Algoritmi de bază și idee



Ana Intuneric

Ana Întuneric5

ajutorul unui șir format din maximum nnumere, se calculează cel mai mare număr r cu proprietatea2r(r+1)-(r-1)<=n.Pentru determinarea celui mai mic indice al unui romb ce conține numărul k, se calculează numărul denumere necesare pentru completarea romburilor la o trecere dus, respectiv întors, de la rombul 1 la rombul r,respectiv de la rombul r la rombul 1, și se calculează poziția lui k în raport cu această valoare.Se observă că atunci când k este o valoare ce se află pe două romburi, primul romb pe care se găseste estecel care se completează la prima trecere (dus).

int n,k,r,p,m,c;int main(){ f>>n>>k>>c;

r=1; while(2*(r+1)*(r+2)-r<=n) r++;if(c==1)

g<<r<<'\n';else{if(k> 2*r*(r+1)-(r-1)) g<<0<<'\n';else

{ p=1; m=1+r*(r+1);if(k<=m) { while(k>1+p*(p+1))p++;

g<<p<<'\n';}

else{ p=r; while(k>(m+2*p-1))

{ m=m+2*p-1; p--;}

g<<p<<'\n';}

}}

f.close();g.close();return 0;

}

Numerus.La ora de matematică distractivă, domnul profesor Numerus propuneelevilor săi să completeze cu numere naturale o grilă cu 6 coloanenumerotate cu literele mari A, B, C, D, E şi F şi cu un număr infinit delinii. Grila va fi completată cu numere naturale, începând cu numărul 1.Pe liniile impare completarea se va face de la stânga la dreapta, iar pecele pare de la dreapta la stânga. Ultimul număr de pe o linie va fiidentic cu penultimul număr (în sensul completării) de pe aceeaşi linie. În figura alăturată aveţi completate primele 7 linii ale grilei. Deoarece pe tablă sau pe o foaie de hârtie numărul de linii este limitat,deci grila poate fi efectiv completată doar pentru un număr mic de linii,domnul profesor Numerus doreşte ca elevii săi să determine, cuajutorul calculatorului, conţinutul unei anumite linii a grilei şi locul saulocurile pe care se poate afla un număr natural, suficient de mare. Cerinţe: Deduceţi regula după care se completează linia k a grilei şi scrieţi unprogram care să citească numerele naturale k şi n şi care să determine: a) Numerele naturale de pe linia k, vizualizate de la stânga la dreapta;

b) Linia pe care se află în grilă numărul natural n;c) Coloana sau coloanele pe care se află în grilă numărul natural n.Date de intrare

Fişier ul numerus.in conţine o singură linie pe care sunt scrise două numere naturale k şi n, separate printr-un singur spaţiu. Date de ieşire Fişierul de ieşire numerus.out va conţine 3 linii:a) pe prima linie, se vor scrie numerele de pe linia k a grilei, separate prin câte un spaţiu, în ordinea



Ana Intuneric

Ana Întuneric6

vizualizării de la stânga la dreapta;b) pe a doua linie, se va scrie un număr natural reprezentând linia pe care se află în grilă numărul natural n; c) pe a treia linie, se va scrie litera sau literele care reprezintă coloana, respectiv coloanele pe care se află îngrilă numărul natural n. Restricţii şi precizări: Numerele k şi n sunt naturale nenule 5 ≤ k 200000000 1 ≤ n 999999999

dacă numărul n se află pe mai multe coloane din grilă, atunci pe a treia linie a fişieru lui numerus.out sevor scrie literele corespunzătoare acestor coloane, separate prin câte un spaţiu. Pentru rezolvarea cerinţei a) se acordă 40% din punctaj, pentru cerinţa b) 30% din punctaj şi pentrucerinţa c) 30% din punctaj.Exemplu:

numerus.in numerus.out Explicaţii

10 40 50 50 49 48 47 468 A B

int n,i,k,a,b,l,c;

int main(){

f>>k>>n;//a)a=5*(k-1)+1;b=5*k;if(k%2==1){

for(i=a;i<=b;i++) g<<i<<' ';

g<<b;}

else{g<<b<<' ';for(i=b;i>=a;i--) g<<i<<' ';

}g<<'\n';//b)l=n/5;if(n%5!=0)l++;g<<l<<'\n';//c)if(n%5==0)

if(l%2==0) g<<'A'<<' '<<'B';else g<<'E'<<' '<<'F';else if(l%2==1) {char c='A'+n%5-1;g<<c;}

else{char c='F'-n%5+1;g<<c;}g<<'\n';f.close();

g.close();return 0;

}

Ciurul lui Eratostene

for(i=2; i*i<=n; i++)if (ciur[i]==0) // elimin toti multiplii lui i<=n

for(j=i*i; j<=n; j+=i) ciur[j]=1;



Ana Intuneric

Ana Întuneric7

descompunereSă se descompună un numar natural n în toate modurile ca suma de două numere prime. Dacă nu existănicio descompunere, atunci să se afişeze 0.

bool v[1001];int n,i,j,nrs;int main(){

f>>n;nrs=0;

//ciurul lui Eratostenefor(i=2;i<=n;i++)if(v[i]==0)

for(j=i*i;j<=n;j=j+i) v[j]=1;if(n%2==1){

if(v[n-2]==0) g<<2<<'+'<<n-2<<'\n';else g<<0<<'\n';

}else{

for(i=1;i<=n/2;i++)if(v[i]==0 && v[n-i]==0){

nrs++;g<<i<<'+'<<n-i<<' ';

}if(nrs==0) g<<0<<'\n';

}f.close();g.close();return 0;

}

numarareDandu-se un numar natural n, sa se determine numarul numerelor prime mai mici sau egale cu n, unde n seva citi din fisierul eratostene.in, iar numarul numerelor prime se va afisa in fisierul eratostene.out. bool prim[2000002];

long long i,j,n,nrprime;int main(){

f>>n;for(i=2;i*i<=n;i++)

if(prim[i]==0){ nrprime++; for(j=i*i;j<=n;j=j+i) prim[j]=1;}g<<nrprime<<’\n’; f.close();g.close();return 0;

}

extraprimeGigel, mare amator de probleme de matematică şi informatică, a observat că unele numere prime au oproprietate interesantă: orice cifră ar elimina dintr -un astfel de număr, numărul obţinut este tot număr prim. A

numit astfel de numere numere extraprime . De exemplu, numărul 317 este un număr extraprim : el estenumăr prim şi, în plus, dacă eliminăm cifra 3, obţinem 17, care este prim; dacă eliminăm 1, obţinem 37, careeste prim; dacă eliminăm 7, obţinem 31, care este şi el număr prim. Cerință Spunem că x este între a şi b dacă x≥a şi x≤b. Fiind date două valori naturale a şi b, să se determine câtenumere extraprime există între a şi b, precum şi cel mai mic şi cel mai mare număr extraprim dintre a şi b. Date de intrarePe prima linie a fişierului de intrare extraprime.in se găsesc cele două valori naturale a şi b, separate printr -un spaţiu. Date de ieșire Fişierul de ieşire extraprime.out va avea 3 linii. Pe prima linie se va scrie un număr natural nr reprezentândnumărul de numere extraprime dintre a şi b. Pe linia a doua a fişierului de ieşire se va scrie cel mai micnumăr extraprim dintre a şi b, iar pe linia a treia a fişierului de ieşire se va scrie cel mai mare numărextraprim dintre a şi b. Restricții și precizări 10 < a ≤ b < 10000000;



Ana Intuneric

Ana Întuneric8

Numărul 1 nu este prim; Pentru datele de test există întotdeauna soluţie; Răspunsurile la cele trei cerinţe vor fi scrise exact pe linia indicată; în cazul în care nu cunoaşteţirezolvarea la una dintre cerinţe, pe linia respectivă se va scrie valoarea -1; Pentru numărul de numere extraprime scris corect se va acorda 40% din punctaj; pentru determinarea şiafişarea corectă a celui mai mic număr extraprim se va acorda 30% din punctaj; pentru determinarea şiafişarea corectă a celui mai mare număr extraprim se va acorda 30% din punctaj; fiecare linie din fișierul de intrare se termină cu caracterul sfârșit de linie.

Exempluextraprime.in extraprime.out Observaţii

10 100 42373

Se află 4 numere extraprime mai mari decât 10 şi mai micidecât 100: 23, 37, 53 şi 73.

O rezolvare posibilă bool v[10000002];int q,p,x,y,c,i,j,a,b,max1,min1;int main(){

f>>a>>b;

//ciurul lui Eratostene cu inversarea valorilor 0 si 1v[1]=1; v[2]=0;for (i=2;i<=10000;i++)

if (v[i]==0) for (j=i*i;j<=10000000;j=j+i) v[j]=1;

c=0;for (i=a;i<=b;i++)

if (v[i]==0) //daca este prim{

y=i; p=1; q=0; while (y>0)

{x=i/p/10*p+i%p; //eliminam cifra de pe pozitia p (unitati sau zeci sau sute …)

if (v[x]==1)//daca x nu este prim{q=1;break;

} p=p*10;y=y/10;

}if (q==0)

{c++;if (c==1) {min1=i;max1=i;}else max1=i;

}}

g<<c<<’\n’<<min1<<’\n’<<max1<<’\n’; f.close();g.close();return 0;

}

secvenţe Mariei îi plac numerele prime şi puterile numerelor prime. Pornind de la un număr prim p, ea

construieşte noi numere, fiecare număr construit fiind un produs de forma py (yN, y≠0) sau q∙pm, mN şi qun număr prim, numindu-le numere p-prime. De exemplu, numerele 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 16, 17sunt primele 13 numere 2-prime deoarece 2=21, 3=320, 4=22, 5=520, 6=321, 7=720, 8=23, 10=521, 12=322,13=1320, 14=721, 16=24, 17=1720.

Într-o zi Maria a găsit o foaie de hârtie, pe care era scris un şir format din n numere naturale nenule.Cum pe lângă numerele p-prime ea este pasionată şi de secvenţe, şi-a pus următoarea întrebare:

câte secvenţe sunt pe foaie cu următoarele proprietăţi: conţin exact k numere p-prime; încep şi se termină cu un număr p-prim.

În plus, Maria doreşte să ştie care este poziţia de început şi cea de final, pentru fiecare secvenţădescoperită, relative la şirul scris pe foaia de hârtie.



Ana Intuneric

Ana Întuneric9

Cerinţă Scrieţi un program care să citească mai multe seturi de date, fiecare set fiind format din numerele n, p, k, cusemnificaţiile din enunţ, şi şirul cu n elemente a1, a2, a3, ... an, numerele Mariei. Programul va determinapentru fiecare set de date numărul secvenţelor ce conţin exact k numere p -prime, precum şi poziţiile de început şi de final ale acestor secvenţe în şirul din set. Date de intrarePe prima linie a fişierului secvente.in se află numărul D reprezentând numărul de seturi de date din fişier.Seturile de date sunt scrise în fişier pe linii succesive. Pentru fiecare set de date, prima linie conţine câte treinumere naturale: n (numărul de elemente de pe foaie), p şi k (cu semnificaţia din enunţ), separate prin câteun spaţiu, iar fiecare dintre următoarele n linii conţine câte un număr natural al şirului a 1, a2, a3, ... an,numerele din şirul Mariei. Date de ieşire Fişierul secvente.out va conţine D soluţii corespunzătoare celor D seturi de date. Pentru fiecare soluţieprima linie va conţine un număr x reprezentând numărul de secvenţe ce îndeplinesc proprietăţile cerute, iarfiecare dintre următoarele x linii vor conţine câte 2 numere naturale, separate printr -un spaţiu, reprezentândpoziţia de început, respectiv de final a fiecărei secvenţe, linii ordonate crescător după poziţia de început.Dacă în şir nu există o astfel de secvenţă, prima linie a setului va conţine valoarea 0. Restricţii şi precizări 1 D 15; 1 k n 15000;

2 p 30000; p este un număr natural prim 1 a1, a2, a3,...,an 30000; a1,a2,a3,...anN*(poziţiile din şir sunt numerotate de la 1) numărul 1 nu este p-prim. o secvenţă dintr-un şir este formată din elemente aflate pe poziţii consecutive în şirul dat.Exemplu:

secvente.in secvente.out Explicaţii

25 3 272744513 5 7345

21 22 40

Cum D=2, fişierul de intrare conţine două seturi de date.Primul set de date: n=5, p=3, k=2 şi a=(7, 27, 4, 45, 1). Şirul din acestset conţine următoarele numere 3-prime: a1=7 (număr prim), a2=27=33

(putere a lui 3) şi a4=45=5*32 (număr prim înmulţit cu o putere a lui 3). În şir sunt două secvenţe cu câte 2 numere 3-prime: a1, a2 respectiv a2,a3, a4. Pe prima linie a fişierului de ieşire se va scrie valoarea 2, iar peurmătoarele două linii, poziţiile de început şi de final ale celor douăsecvenţe determinate.Şirul a din al doilea set de date, n=3, p=5, k=7,a=(3, 4, 5), nu conţinenici o secvenţă cu proprietatea cerută. Astfel, în fişierul de ieşire, pecea de-a patra linie, se va scrie valoarea 0.

Timp de rulare/test: 1 secundă 1. Pana la 90 puncte La citire se verifică pentru fiecare număr daca este p-prim. Mai întâi se împarte numărul în mod repetat la patât timp cât este posibil, iar apoi verifică dacă valoarea rămasă este număr prim. Pozitiile numerelor prime se memoreaza într-un vector V. Să notăm cu m dimensiunea lui V. Daca avem k>mse afiseaza 0. In caz contrar sunt m-k+1 perechi care indeplinesc conditia, acestea determinându-se afişând

perechi de valori din V cu proprietatea că se afla la distanţa k-1 una de cealaltă. În prima etapa, verificarea primalităţii unui număr se face parcurgand divizorii acestuia până la radicalul său,

adică în O( ). Complexitate O(n )2. Alte doua variante de 100 puncte a. Se pot determina toate numerele prime până la n folosind ciurul lui Eratostene cu o complexitate O(nlgn)saub. se pot memora numerele prime într-un vector de constante (rămâne însă O(lgp n) gasirea puterii lui ppentru fiecare numar). Cautarea în vectorul de numere prime se rezolvă folosind cautarea binară.

int poz[15001],x,n,p,k,m; bool ciur[30001];int main()

{int i,j,D;//ciurfor(i=2;i*i<=30000;i++)

if(ciur[i]==0)for(j=i*i;j<=30000;j=j+i)ciur[j]=1;



Ana Intuneric

Ana Întuneric10

f>>D;for(j=1;j<=D;j++){f>>n>>p>>k;m=0;int gasit=0;for(i=1;i<=n;i++){

f>>x;if(x!=1){

while(x%p==0) x/=p;

if(ciur[x]==0) poz[++m]=i;if(m>1 && poz[m]-poz[m-1]==k-1) gasit=1;

}}if(gasit){

g<<m-1<<'\n';for(i=1;i<=m-k+1;i++)

g<<poz[i]<<' '<<poz[i+k-1]<<'\n';}else g<<0<<'\n';}f.close();g.close();return 0;

}

factorialFactorialul unui număr natural nenul n, notat n!, se defineşte ca fiind produsul numerelor naturale de la 1 lan. Una dintre modalităţile de reprezentare a factorialului este prin enumerarea factorilor primi pe care îiconţine şi a exponenţilor acestora. Cerinţă Fiind dat un număr natural n, scrieţi un program care determină suma exponenţilor factorilor primicorespunzători descompunerii în factori primi a lui n factorial.Date de intrareFişierul de intrare factorial.in conţine pe prima linie numărul natur al n.Date de ieşire Fişierul de ieşire factorial.out va conţine pe prima linie un număr reprezentând suma exponenţilor numerelorprime din descompunerea în factori primi a lui n!.Restricţii şi precizări 2 ≤ n≤ 100000

Se generează toate numerele prime mai mici sau egale cu n utilizând “ciurul lui Eratostene”.Matematic putem afla puterea la care apare numărul prim P în N! folosind formula[N /P] + [N /P

2] + [N /P3] + ...

Aplicând această formulă pentru toate numerele prime mai mici sau egale cu n şi însumând rezultatele,obţinem soluţia problemei. int n,i,j,ciur[100001],s,np,x;int main(){

f>>n;for (i=2;i*i<=n;i++)

if (!ciur[i])for (j=i*i;j<=n;j+=i) ciur[j]=1;

for (i=2;i<=n;i++){

if (!ciur[i])

{ x=i; while (n/x!=0){

s+=n/x; x*=i;}

factorial.in factorial.out Explicaţii

5 5 5! = 1*2*3*4*5 = 23 * 31 * 51 3+1+1=5



Ana Intuneric

Ana Întuneric11

}}

g<<s<<'\n';f.close();g.close(); return 0;}

nrprimeGheorghe a învățat la școală despre numere prime. A învățat că un număr este prim, dacă se divide doarcu 1 și cu el însuși(1 nu este considerat număr prim). A aflat că există algoritimi foarte eficienți care potdetermina dacă un număr este prim sau nu, în timp chiar sub polinomial. Din păcate acești algoritmi sunt

foarte complicați, și Gheorghe s-a gândit la o aproximare. Ideea lui este să consideri un număr prim dacă nuse divide la primele K numere prime.Cerinţă Demonstrează că ideea lui Gheorghe este doar o aproximare. Dându-se un număr K (1 ≤ K ≤ 100.000 ), aflăcel mai mic numar N care nu este divizibil cu primele K numere prime, dar nu este prim.Date de intrare Pe prima linie din fişierul prim.in se va afla numărul K .Date de ieşire Pe prima linie a fişierului prim.out se va gasi numarul N căutat. Exemplu Pentru valoarea 3 ca dată de intrare se va afișa 49, pentru că primele 3 numere prime sunt 2, 3, 5 . Numerelecare nu sunt divizibile cu 2, 3 sau 5 sunt : 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 49, .. 49 este cel mai mic

numar care nu este prim.Soluţie Deoarece nu știm de câte numere vom avea nevoie, am declarat vectorul ciur cu 1000000 elemente. Pânăacolo vom face parcurgerea vectorului, aplicând Ciurul lui Eratostene. Variabila nrp desemnează numărul deparcurgeri, astfel, când se ajunge la k+1 parcurgeri n va lua valoarea pătratului lui i , până atunci multipliilui i fiind “eliminaţi”, valoarea lor din vector devenind 0. Condiția de la început if(prim[i]) se asigură că se vorverifica doar numerele prime. Datorită faptului că pătratul unui număr prim nu se poate divide la numărul primanterior, ne dăm seama că soluția i*i după k+1 parcurgeri este cea corectă. bool ciur[1000001];int k,nrp,gasit,i,j;long long n;int main()

{f>>k;f.close();for(i=2;i<dim;i++) ciur[i]=1;for(i=2;i<=dim && !gasit;i++)

if(ciur[i]){

nrp++;if(nrp==k+1){n=i*i;g<<n<<endl;gasit=1;

}for(j=i+i;j+i<=dim;j=j+i) ciur[j]=0;

}

g.close();return 0;}

Descompunere în factori primid=2; while(n>1){

puterea=0; while(n%d==0) puterea++,n=n/d;if(puterea>0) g<<d<<" la puterea "<<puterea<<endl;d=d+1;

}

Observaţie: dacă n=f 1p *f 2

p *…*f kp , atunci numărul său de divizori este (p1+1)*(p2+1)*…*(pk+1)

dacă n=f 1p1*f 2

p2*…*f kpk, atunci numărul de numere mai mici decât n și prime cu n

este: n*(1-1/f1)*(1-1/f2)*...*(1-1/fk)



Ana Intuneric

Ana Întuneric12

Vectori-teorie

Inserarea elementului x pe poziţia i învectorul v de dimensiune n

Ştergerea elementului de pe poziţia i

din vectorul v cu n componenten++;for(k=n;k>i;k--) v[k]=v[k-1];v[i]=x;

for(k=i;k<n;k++) v[k]=v[k+1];n--;

Permutarea circulară a vectorului v M n(R) cu o poziţie spre stânga aux=v[1];

for(i=1;i<=n-1;i++) v[i]=v[i+1];v[n]=aux;Interclasarea a doi vectori a[m] şi b[n]sortaţi crescător

C ăutarea binară( căutarea lui nr seface într-un vector a[n] sortatcrescător)

i=1;j=1;k=0; while(i<=m && j<=n)if(a[i]<b[j]) {k++;c[k]=a[i];i++;}else {k++;c[k]=b[j];j++;} while(i<=m)//s-a terminat vectorul b{k++;c[k]=a[i];i++;} while(j<=n)// s-a terminat vectorul a{k++;c[k]=b[j];j++;}

st=1;dr=n;gasit=0; while(!gasit && st<=dr){

mijloc=(st+dr)/2;if(nr==a[mijloc]) gasit=1;else if(nr<a[mijloc]) dr=mijloc-1;

else st=mijloc+1;}

O solutie cu aceeasi complexitate teoretica dar mai rapida in practica foloseste cautarea binara pe biti: int N, A[N];

int cautare_binara_biti(int val)

{

inti, step;

for(step = 1; step < N; step <<= 1);

for(i = 0; step; step >>= 1)

if(i + step < N && A[i + step] <= val)

i += step;

return i;

}

int n, v[51];//qsort-----------O(n )

void QS(int st, int dr){

int i=st,j=dr,aux;int pivot=v[(st+dr)/2];

// cautam pivotul a.i. toate elem. aflate la stanga sa sa fie mai mici si toate elem. aflate la dreapta sa sa fie mai mari while (i <= j)

{ while (v[i]<pivot) i++; while (v[j]>pivot) j--;if (i <= j){

aux=v[i];v[i]= v[j];v[j]=aux;i++;j--;

}}

//apelul recursiv if(st<j) QS(st,j);if(i<dr) QS(i,dr);

}



Ana Intuneric

Ana Întuneric13

void interc(int st, int m, intdr){

//a[st---i---m];a[m+1---j---dr]int b[11],k,i,j;i=st;j=m+1;k=0;

while(i<=m && j<=dr)if(a[i]<=a[j]){b[++k]=a[i];i++;}else {b[++k]=a[j];j++;}

while(i<=m){b[++k]=a[i];i++;}

while(j<=dr){b[++k]=a[j];j++;}

//refacere a[st]..i.a[dr]j=1;for(i=st;i<=dr;i++)a[i]=b[j++];

}

void DEI(intst,intdr){

if(st<dr){

int m=(st+dr)/2;DEI(st,m);DEI(m+1,dr);interc(st,m,dr);

}}

Cautare binaraSe da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu segaseste in sir1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Segaranteaza ca cel mai mic numar al sirului este mai mic sau egal decat x 2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Segaranteaza ca cel mai mare numar din sir este mai mare sau egal decat x Date de intrarePe prima linie a fisierului de intrare cautbin.in se afla numarul N reprezentandnumarul de elemente alesirului. Pe urmatoarea linie se gasesc N numere reprezentand elementele sirului. Linia a treia continenumarul M reprezentand numarul de intrebari. Apoi urmeaza M linii, fiecare cu unul dintre cele 3 tipuri deintrebari.Date de iesire

In fisierul de iesire cautbin.out se vor afisa M linii reprezentand raspunsul la cele M intrebari.Restrictii 1 ≤ N ≤ 100 000 1 ≤ M ≤ 100 000 Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de bitiExemplu

cautbin.in cautbin.out51 3 3 3 530 31 32 3

442



Ana Intuneric

Ana Întuneric14

int n,m,v[100010];

int cb0(int s, int d, int val){

int m; while(s <= d){

m = (s + d) / 2;if (v[m] <= val) s = m + 1;else d = m - 1;

} m = (s + d) / 2;if (v[m] > val) m--;if (v[m] == val) return m;return -1;

}


int m, n = d; while(s < d){

m = (s + d) / 2;if (v[m] <= val) s = m + 1;else d = m;

} m = (s + d) / 2;if (v[m] > val) m--;return m;

}


int m; while (s < d)

{ m = (s + d) / 2;if (v[m] < val) s = m + 1;else d = m;

} m = (s + d) / 2;if (v[m] < val) m++;return m;

}

int main(){

int i, tip, val;

f>>n;for (i = 1; i <= n; i++) f>>v[i];f>>m;for (i = 1; i <= m; i++){

f>>tip>>val;if (tip == 0) g<<cb0(1, n, val)<<'\n';if (tip == 1) g<<cb1(1, n, val)<<'\n';if (tip == 2) g<<cb2(1, n, val)<<'\n';


}

Recomandări pentru implementare În cazul utilizării instructiunii m=(st+dr)/2 pot apărea erori nedorite. st+dr poate depasi tipul de data alvariabilelor st si dr . De asemenea pot aparea erori in cazul in care capetele intervalului pot lua si valorinegative. De aceea se recomanda scrierea instructiunii mid = lo + (hi-lo)/2 in loc de mid = (st+dr)/2 .Numarare triunghiuri



Ana Intuneric

Ana Întuneric15

Andrei are N betisoare de lungimi nu neaparat diferite. El vrea sa afle in cate moduri poate alege treibetisoare astfel incat sa poata forma cu ele un triunghi.CerintaDandu-se lungimile betisoarelor aflati in cate moduri se pot alege trei dintre ele astfel incat sa se poata formaun triunghi cu ele.Date de IntrarePe prima linie a fisierului nrtri.in se afla N , numarul de betisoare. Pe urmatoarea linie se afla N numereseparate prin spatii ce reprezinta lungimile betisoarelor.Date de IesireFisierul nrtri.out contine un singur numar ce reprezintanumarul cerut de problema.Restrictii si precizari 1 ≤ N ≤ 800 1 ≤ lungimea unui betisor ≤ 30000 se considera triunghiuri si cele care au un unghi de 180 de grade si celelalte doua de 0 grade

(2 segmente coliniare se confunda cu al 3-lea) pentru 75 de puncte se garanteaza 1 ≤ N ≤ 150

Exemplunrtri.in nrtri.out

42 3 7 4

2

ExplicatiiSingurele triunghiuri care se pot forma sunt alcatuite din urmatoarele betisoare (date prin numarul deordine):1, 2, 42, 3, 4

#include <fstream>

#include <algorithm>

using namespace std;

ifstream f("nrtri.in");

ofstream g("nrtri.out");

int v[801],s,S,i,j,dr,st,mij,n,p;

int main()

{

f>>n;

for(i=1;i<=n;i++)

f>>v[i];

sort(v+1,v+n+1);

for(i=1;i<=n;i++)

for(j=i+1;j<=n;j++)

{ p=0;

s=v[i]+v[j];

st=j;dr=n;

while(st<=dr){

mij=(st+dr)/2;

if(s<v[mij]){dr=mij-1;}

else{st=mij+1;p=mij;}}

if(p!=0)S+=p-j;}

g<<S;

return 0;

}

FactorialSe da un numar intreg P . Sa se gaseasca cel mai mic numar natural strict pozitiv N pentru care N! areexact P cifre de 0 la sfarsit. Se stie ca N! = 1 * 2 * 3 * .... * (N - 1) * N .Date de intrareFisierul fact.in va contine pe prima linie numarulintreg P .



Ana Intuneric

Ana Întuneric16

Date de iesirePe prima linie a fisierului fact.out se va scrie acel numar N care indeplinestecondiitle impuse sau -1 daca nuexista un astfel de N .Restrictii 0 ≤ P ≤ 10 8

Exemplefact.in fact.out

0 1

2 1010 45

int main()

{

Int n , c ;

long long st , dr , m , x ;

st=1 ;dr=1000000000 ;

f>>n ;

while(st<=dr)

{

m=(st+dr)/2 ;

x=m; c=0;

while(m!=0)

{

c=c+m/5 ;

m=m/5;

}

if(c==n)

{

if(x-x%5==0) g<<"1";

else g<<x-x%5 ;

dr=-1 ;

}

else if(c>n) dr=(st+dr)/2-1 ;

else st=(st+dr)/2+1 ;

}

if(dr!=-1) g<< "-1";

return 0;

}

TransportO firma ce produce saltele cu apa are N astfel de saltele intr-un depozit, asezate una peste alta (intr-o stiva).Fiecare saltea este caracterizata prin volumul sau (un numarintreg, exprimat in decimetri cubi). Pentru a letransporta la magazin, in vederea comercializarii, firma va inchiria un camion care va avea o capacitateegala cu C decimetri cubi. Acest camion va trebuie sa efectueze cel mult K transporturi (s-a estimat duratafiecarui transport si s-a ajuns la concluzia ca daca s-ar efectua mai mult de K transporturi, camionul ar ajungela magazin in afara orelor de aprovizionare, astfel ca saltelele nu ar putea fi comercializate). La fiecaretransport, camionul poate fi incarcat cu saltele, cu conditia ca suma volumelor saltelelor incarcate in camionsa nu depaseasca capacitatea camionului. Deoarece saltele sunt asezateintr-o stiva, nu este posibil sa seincarce in camion o saltea decatdupa ce au fost incarcate (si eventual transportate) toate saltelele dedeasupra ei. Intrucat costul inchirierii camionului depinde de capacitatea acestuia, firma doreste sa inchiriezeun camion cu capacitatea cat mai mica care sa poata transporta toate cele N saltele, efectuandmaxim K transporturi.

Date de intrarePe prima linie a fisierului transport.in se afla numerele intregi N si K (separate printr-un spatiu). Pe fiecare dinurmatoarele N linii se afla un numarintreg, reprezentand volumul unei saltele. Prima din aceste N linii contine

volumul saltelei din varful stivei, a doua linie contine volumul celei de-a doua saltele, etc.Date de iesireIn fisierul transport.out vetiafisa un singur numarintreg, reprezentand capacitatea minima pe care trebuie sao aiba camionul pentru a putea transporta cele N saltele efectuand maxim K transporturi.



Ana Intuneric

Ana Întuneric17

Restrictii si precizari 1 ≤ N ≤ 16 000 1 ≤ K ≤ 16 000 1 ≤ volumul oricarei saltele ≤ 16 000

Exemplutransport.in transport.out

6 37

32314

8

Explicatie: la primul transport este incarcata prima saltea (care are volumul 7). La cel de-al doilea transportsunt incarcate saltele 2 si 3 (volumul total este 3 + 2 = 5). La cel de-al treilea transport sunt incarcate saltele4, 5 si 6 (volumul total este 3 + 1 + 4 = 8).

int n, li, ls, m, s, sol, a[16010], i, Max, nr, k;

int main()

{

f>>n>>k;

for(i=1;i<=n;i++)

{

f>>a[i];

if(a[i]>Max) Max=a[i];

s+=a[i];

}

li=Max;

ls=s;

m=(li+ls)/2;

while(li<=ls)

{

s=0;

nr=0; for(i=1;i<=n;i++)

{

s+=a[i];

if(s>m && i!=n) nr++, s=a[i];

else if(i==n) nr++;

}

if(s-m>0) nr++;

if(nr<=k)

{

sol=m;ls=m-1;

}

else li=m+1;

m=(li+ls)/2; }

g<<sol;

return0;

}

secventaDin fisierul lungime.in se citeste un numar n mai mic decat 2000000000 si apoi se citesc n numere naturale. Afisati in fisierul lungime.out lungimea celei mai lungi secvente din numerele citite care are proprietatea caincepe si se termina cu aceeasi valoare si nu mai contine acea valoare (inafara de primul si ultimul elemental secventei).Exemplu:

lungime.in lungime.out143 2 4 3 4 2 3 4 5 6 7 2 5 5

7

int main(){



Ana Intuneric

Ana Întuneric18

int n,x,ap1[100]={0}, ap2[100]={0};f>>n;for(int i=1;i<=n;i++){

f>>x;if(ap1[x]==0) ap1[x]=i;//prima aparitieelse if(ap2[x]==0) ap2[x]=i;

else if(i-ap2[x]>ap2[x]-ap1[x]){

ap1[x]=ap2[x];ap2[x]=i;//refac prima si ultima aparitie

}}int maxx=0;for(int i=0;i<100;i++)

if(ap2[i]-ap1[i]>maxx) maxx=ap2[i]-ap1[i];g<<maxx+1<<endl;f.close();g.close();return 0;

}

Generare submultimi utilizand vectorul caracteristicSe citeste o multime a cu n elemente numere naturale. Sa se afiseze toate submultimile multimii a.Indicatie: Se contruiesc intr-un vector caracteristic toate modalitatile de a pune valorile 0 si 1 pe n pozitii si

corespunzator fiecarei variante se asociaza o submultime astfel: pozitiile pe care este valoarea 1 corespundelementelor alese in submultime, iar cele cu valoarea 0 celor care nu sunt alese in submultime.Exemplu: Pentru n=5 si elementele 1 3 5 7 9 se genereaza:0 0 0 0 0 - multimea vida1 0 0 0 0 - submultimea {1}0 1 0 0 0 - submultimea {3}1 1 0 0 0 - submultimea {1, 3}0 0 1 0 0 - submultimea {5}...1 1 0 1 1 - submultimea {1, 3, 7, 9}etc

while(p[n+1]!=1){

for(i=1;i<=n;i++)if(p[i]==1) g<<a[i]<<" ";

g<<endl;i=1; while(p[i]==1 && i<=n) //caut primul 0 de la stanga la dreapta{

p[i]=0;i++;} p[i]=1;

}

235Definim o putere a lui 3 un număr de forma 3k, (k număr natural strict pozitiv), o putere a lui 5 un număr deforma 5k (k număr natural strict pozitiv) iar o putere a lui 2 un număr de forma 2k (k număr natural strictpozitiv).Se dă un şir de n numere naturale. Plecând de la acest şir, formăm un nou şir prin eliminarea tuturornumerele care nu sunt puteri ale lui 3 şi nici puteri ale lui 5. Ordinea relativă între numerele care nu sunteliminate se păstrează. Cerinţe Să se determine câte numere conţine şirul nou format. Să se determine deasemenea numărul de secvenţe având lungimea egală cu o putere a lui 2 existente înşirul nou format în care numărul de puteri ale lui 3 este egal cu numărul de puteri ale lui 5. O secvenţă esteformată din elemente aflate pe poziţii consecutive în acest şir nou format iar lungimea unei secvenţe este

egală cu numărul de elemente pe care aceasta îl conţine. Date de intrarePe prima linie in fişierul 235.in se afla un număr natural n. Pe fiecare dintre următoarele n linii câte un numărnatural mai mare decat 1 reprezentând numerele şirului iniţial. Date de ieşire



Ana Intuneric

Ana Întuneric19

Pe prima linie a fişierului 235.out se va afla o valoare naturală m care va reprezenta numărul de elementerămase în şir după eliminare. Pe a doua linie se va afla o valoare naturală s reprezentând numărul desecvenţe din şirul nou format care au proprietăţile cerute. Restricţii şi precizări 2 n 500000Numerele din şirul iniţial sunt numere naturale din intervalul [2,2000000000].Se garantează că m ≤ 40000 pentru fiecare set de date de intrare. Pentru determinarea corectă a valorii numărului m se acordă 30% din punctaj iar pentru determinareacorectă a ambelor valori (m şi s) se acordă 100% din punctaj.

Exemplu:235.in 235.out Explicaţii 8625125591581100

125

64

Şirul rămas după eliminarea numerelor care nu sunt puteriale lui 5 sau ale lui 3 are 6 elemente:625, 125, 5, 9, 81, 125. În acest şir sunt: - două secvenţe formate din două valori care conţin unnumăr egal de puteri ale lui 3 şi ale lui 5: 5,9 şi 81,125;- două secvenţe de patru numere care conţin un număr egalde puteri ale lui 3 şi ale lui 5: 125, 5, 9, 81 şi 5, 9, 81, 125

Timp de rulare/test: 1 secundă Ineficient timp, 50 puncte

int n,k,i,x,m,L,p,nr3,nr5,nrs;unsigned int v[40001];int main(){

f>>n;//mai eficient timp ar fi sa constr//un vector cu puterile lui 3 si sa cautam binar in el pe xfor(i=1;i<=n;i++){

f>>x; nr3=nr5=0; while(x%3==0){x=x/3; nr3++;}if(x==1 && nr3>0) v[++m]=-1; while(x%5==0){x=x/5;nr5++;}if(x==1 && nr5>0 && nr3==0) v[++m]=1;

}g<<m<<'\n';//verificam secventele de lungime putere a lui 2for(L=2;L<=m;L*=2){

int s=0;for(i=1;i<=L;i++)s+=v[i];if(s==0) nrs++;

for(i=2;i<=m-L+1;i++){s=s-v[i-1]+v[i+L-1];//actualizare suma de puteriif(s==0)nrs++;

}}g<<nrs<<'\n';return 0;

}

Rezolvare de 100 de puncte

int n,k,i,x,m,L,nr3,nr5,nrs,gasit,mij,st,dr;

int v[40001],p[33]={3,5,9,25, 27, 81, 125, 243, 625, 729, 2187, 3125, 6561, 15625,19683, 59049, 78125, 177147, 390625, 531441, 1594323, 1953125, 4782969, 9765625,14348907, 43046721, 48828125, 129140163, 244140625, 387420489, 1162261467, 1220703125} ;

int main(){



Ana Intuneric

Ana Întuneric20

f>>n;//mai eficient timp ar fi sa constr//un vector cu puterile lui 3 si sa cautam binar in el pe xfor(i=1;i<=n;i++){

f>>x;//caut binar x in vectorul p[]st=1;dr=32; gasit=0; while(st<=dr && !gasit){

mij=(st+dr)/2;

if(x==p[mij]) gasit=1;else if(x<p[mij]) dr=mij-1;

else st=mij+1;}if(gasit)

if(x%3==0) v[++m]=-1;else v[++m]=1;

}g<<m<<'\n';//verificam secventele de lungime putere a lui 2for(L=2;L<=m;L*=2){

int s=0;

for(i=1;i<=L;i++)s+=v[i];if(s==0) nrs++;for(i=2;i<=m-L+1;i++){

s=s-v[i-1]+v[i+L-1];//actualizare suma de puteriif(s==0)nrs++;

}}g<<nrs<<'\n';return 0;

}

maxD Fiind elev în clasa a IX-a, George, îşi propune să studieze capitolul divizibilitate cât mai bine. Ajungând lanumărul de divizori asociat unui număr natural, constată că sunt numere într -un interval dat, cu acelaşinumăr de divizori. De exemplu, în intervalul [1, 10], 6, 8 şi 10 au acelaşi număr de divizori, egal cu 4. De asemenea, 4 şi 9 auacelaşi număr de divizori, egal cu 3 etc. Cerinţă Scrieţi un program care pentru un interval dat determină care este cel mai mic număr din interval ce arenumăr maxim de divizori. Dacă sunt mai multe numere cu această proprietate se cere să se numere câtesunt.Date de intrare Fişierul de intrare maxd.in conţine pe prima linie două numere a şi b separate prin spaţiu (a≤b) reprezentând

extremităţile intervalului. Date de ieşire Fişierul de ieşire maxd.out va conţine pe prima linie trei numere separate prin câte un spaţiu min nrdiv contor cu semnificaţia: min = cea mai mică valoare din interval care are număr maxim de divizori nrdiv = numărul de divizori ai lui min contor = câte numere din intervalul citit mai au acelaşi număr de divizori egal cu nrdiv Restricţii şi precizări 1 ≤ a ≤ b ≤ 1000000000 0 ≤ b-a ≤ 10000 Exemplu

Explicaţie



Ana Intuneric

Ana Întuneric21

În primul exemplu, 6 este cel mai mic numar din interval care are maxim de divizori egal cu 4 şi unt 3 astfelde numere (6, 8, 10). În cel de-al doilea exemplu, 200 are 12 divizori, iar în intervalul [200,200] există un singur număr cu aceastăproprietate.

int a,b,d,m,i,j,nrd=1,k=0;int min=a,nrdiv=1,contor=0;int v[10001];

int main(){f>>a>>b;for(i=a;i<=b;i++){

j=i;nrd=1;d=2; while(j>1) //fac descompunerea in factori primi{ m=0; while(j%d==0) m++,j=j/d;//daca multiplicitatea lui d in n este diferita de 0if(m!=0)

nrd=nrd*(1+m); //atunci inmultesc numarul de divizori de pana acum cu 1+m

d++; //trec la urmatorul divizor posibil }v[k]=nrd; //al catelea numar din interval estek++; // primeste numarul de divizori pentru numarul a+kif(nrd>nrdiv) nrdiv=nrd; //daca numarul de divizori este mai mare ca cel gasit pana acum atunci el este noul nrdiv

}for(i=0;i<(b-a+2);i++) //parcurg vectorul v{

if(v[i]==nrdiv) contor++; //daca contine numarul nrdiv atunci il numar if(v[i]==nrdiv && contor==1) min=a+i; //si retin care a fost primul numar cu nrdiv divizori

}g<<min<<' ' <<nrdiv<<' '<<contor<<’\n’; f.close(); g.close();return 0;

}

Reuniune de intervaleSe citeste un numar natural n si apoi n intervale deschise cuextremitatile numere intregi. Afisati reuniunea celor n intervale citite.

struct interval{int a,b;}X[100];int n;

int main(){

int i,j,xr,yr;interval aux;f>>n;for(i=1;i<=n;i++) f>>X[i].a>>X[i].b;//citim capetele fiecarui intervalfor(i=1;i<n;i++)//sortam intervalele dupa capatul din dreapta

for(j=i+1;j<=n;j++)if(X[i].b>X[j].b){

aux=X[i]; X[i]=X[j]; X[j]=aux;}

xr=X[1].a; yr=X[1].b;for(i=2;i<=n;i++)

if(X[i].a<yr){

if(X[i].a<xr) xr=X[i].a;

yr=X[i].b;}

else{

g<<"("<<xr<<","<<yr<<") U ";

date.in date.out41 63 4.57 95 6

(1,6) U (7,9)

[a,b] v[0],v[b-a+1]

a+k v[k]



Ana Intuneric

Ana Întuneric22

xr=X[i].a; yr=X[i].b;}g<<"("<<xr<<","<<yr<<") ";f.close();g.close();return 0;

}

tabara Într-o tabară la munte s-au întâlnit copii veniţi din n regiuni diferite ale ţării. Tabara are în dotare suficientecabane identice cu câte n paturi. Directorul taberei a stabilit, pentru o cât mai bună socializare, următoarele

reguli: în fiecare cabană trebuie să fie cazate exact n persoane, dintre care cel puţin n-1 trebuie să fie copii şi celmult un profesor; copiii cazaţi în fiecare cabană trebuie sa provină din regiuni diferite ale ţării; nici un copil sau profesor nu poate fi cazat în mai multe cabane.Cerinţă Să se găsească numărul maxim M de cabane care pot fi completate respectând restricţiile de mai sus. Date de intrareFişierul de intrare tabara.in conţine pe prima linie două numere naturale n şi p, unde n este numărul deregiuni, iar p este numărul de profesori. Pe linia a doua, se găsesc n numere naturale, c1, c2, ... cn separateprin câte un spaţiu. Valoarea ci reprezintă numărul copiilor veniţi din regiunea i. Date de ieşire

În fişierul de ieşire tabara.out se va scrie pe prima linie numărul natural M.Restricţii şi precizări 2 <= n, p<= 50000 ;1 <= c1, c2, ... cn<= 50000 Este posibil ca după completarea celor M cabane, nu toţi elevii şi/sau profesorii să fie cazaţi Numărul total de persoane care trebuie cazate nu va depăşi pe nici un test 2.000.000.000Exempletabara.in tabara.out Explicaţie 2 21 3

3 Codificând cele două regiuni cu x şi y, se pot completa maxim 3 cabane înfelul următor: [x1,y1], [p1,y2], [p2,y3] .x1 reprezintă singurul copil din regiunea 1, y1,y2,y3 reprezintă cei trei copii dinregiunea 2, iar p1,p2 sunt cei doi profesori.

tabara.in tabara.out Explicaţie 3 42 3 4

4 Dacă cele 3 regiuni sunt x, y, z, atunci se pot completa 4 cabane în felulurmător:[x1,y1,z1], [x2,p1,z2], [p2,y2,z3], [p3,y3,z4]x1,x2 identifică cei doi copii din regiunea 1, etc. Profesorul p4 nu va fi cazat.

Să observăm că rolul unui profesor nu diferă de cel al oricărui copil, deci putem să considerăm că avem unşir a cu n+1 elemente, pe care îl vom sorta în ordine crescătoare.Conform principiului cutiei lui Dirichlet, dacă dintr -o regiune avem r elevi, atunci ei vor încăpea într -un numărde c cabane numai cu condiţia c ≥r . Într-adevăr, dacă c <r , există o cutie (cabană) în care ar fi mai mulţi copiidin regiunea r , ceea ce nu ne convine. Deci în acest caz putem caza c elevi, iar r-c elevi nu mai au loc înnicio cabană, în concluzie îi putem elimina. Pentru a obţine numărul maxim de cabane, vom calcula suma totală s de elevi cazaţi (profesorul e elev!), şi împărţind la n, obţinemprintr -o primă aproximare numărul de cabane care se pot umple cu elevi. Să notăm

acest prag cu p=[s/n]. Acest prag se va recalcula în mod repetat ţinând cont de principul lui Dirichlet, conformcăruia vom înlocui în şirul a toate elementele a[i ] mai mari decât p cu p, şi recalculând suma elementelor,până când toate elementele şirului vor respecta condiţia a[i ]≤ p.Rezultatul final va fi p=[s/n]=max(a[i]).

int profi,copii[50000], L,R,M,p,n,i;int main(){//citire

f >> n >> profi;for (i = 1; i<=n; i++) f >> copii[i]; m=n;

//sortam crescatordo{

sortat=1;for(i=1;i<m;i++)



Ana Intuneric

Ana Întuneric23

if(copii[i]>copii[i+1]){

aux=copii[i];copii[i]=copii[i+1];copii[i+1]=aux;sortat=0;

} m--;

} while(!sortat);

L = 0; R = copii[n] + profi + 1;

while (L + 1 < R){

M = (L + R) / 2; p = 0;for (i = 1; i <=n; i++)

if (copii[i] < M) p = p+M - copii[i];if (p <= M && p<= profi) L = M;else R = M;

}g << L << '\n';f.close(); g.close(); return 0;

}

moretimeLa banca Moretime, moneda este Time-ul. Cei n clienţi ai băncii au conturi identificate prin valori naturalenenule, distincte două câte două. La deschiderea contului, fiecare client a depus un fond de siguranţăreprezentat printr-un număr natural nenul (cantitatea de Time aferentă contului, ce poate fi folosită de bancă,pentru urgenţe majore). Un client al băncii este considerat premium dacă numărul său de cont începe şi setermină cu aceeaşi cifră nenulă.Lumea este lovită de criza de timp şi banca Moretime a hotărât să susţină doar clienţii premium printr-unprogram special. Astfel, banca va colecta fondurile de siguranţă ale unora dintre clienţii premium iar sumaobţinută o va folosi integral pentru a finanţa, cu cantităţi egale de Time, pe fiecare client premium, inclusivpe cei de la care a colectat fondul.Cerinţă Cunoscând n, numărul de clienţi, conturile şi valorile fondurilor de siguranţă ale acestora, să se determine: a. numărul clienţilor premium b. numărul clienţilor premium ce pot fi aleşi de bancă astfel încât suma fondurilor de siguranţă colectată de

la aceştia să poată fi distribuită în mod egal fiecărui client premium c. numerelor de cont ale celor selectaţi la punctul b). Date de intrareFişierul text moretime.in conţine pe prima linie n, numărul de clienţi ai băncii iar pe următoarele n liniiperechi de numere, separate prin câte un spaţiu, reprezentând numărul contului şi valoarea fondului desiguranţă, pentru fiecare dintre cei n clienţi. Date de ieşire Fişierul de ieşire moretime.out va conţine, pe prima linie cp, numărul de clienţi premium, pe a doua linie p,numărul de clienţi premium ce pot fi aleşi de bancă în condiţiile de mai sus iar pe linia a treia, un şir de p

numere separate prin câte un spaţiu, reprezentând conturile acestor clienţi. Dacă sunt mai multe soluţii se vascrie una dintre acestea.Restricţii şi precizări 1 ≤ p ≤ cp ≤ n ≤ 10000;Moneda Time nu este divizibilă. Numerele de cont sunt numere naturale cu cel puţin două şi cel mult cinci cifre.Fondurile de siguranţă sunt numere naturale nenule mai mici decât 100000. Pentru răspunsuri corecte se acordă punctaje parţiale astfel: a) 30%; a)+b)+c) 100%

Exemplumoretime.in moretime.out Explicaţii



Ana Intuneric

Ana Întuneric24

6112 100217 501231 2003000 5002902 20044 100

322902 44

sunt 3 clienţi premium pot fi aleşi 2 clienţi premium pentru colectarea fondurilor

de siguranţă clienţii cu conturile 2902 şi 44 pot fi aleşi pentru că suma

fondurilor lor (200+100=300) poate fi împărţită în mod egalcelor 3 clienţi premium (fiecare ar primi 100).

Se citesc cele n perechi de numere reprezentand conturile si fondurile celor n clienti.Se memoreaza in vectorii cont si fond doar valorile corespunzatoare clientilor premium (prima cifra si ultimacifra a numarului de cont sunt egale).

cp=numarul clientilor premiumPe vectorul fond se aplica principiul cutiei lui Dirichlet, conform caruia, pentru orice multime de cp numerenaturale exista o submultime de suma divizibila cu cp. Se construiesc pe rand sumeles1=fond[1];s2=fond[1]+fond[2];...si=fond[1]+...+fond[i];...

Daca si este divizibila cu cp atunci submltimea cautata este formata din primii i clienti cu cont[1],...cont[i]Daca nicio suma nu este divizibila cu cp, cum sunt cp resturi distincte posibile la impartirea la cp (0,1,2,..cp-1) iar restul 0 nu s-a obtinut, exista cel putin doua sume diferite care dau acelasi rest r la impartirea la cp.Pentru a memora resturile vom construi vectorul rest cu semnificatia rest[k]=i, unde si % cp = k

Fie sj, si (j<i) doua sume care dau restul r la impartirea la cp (r din multimea 1, 2, ...cp-1).Conform teoremei impartirii cu rest, sj = c1*cp + r iar si = c2 * cp + r. Atunci, si - sj = (c2-c1) * cp.

Deci, suma elementelor cuprinse intre j+1 si i va fi divizibila cu cp iar valorile cautate sunt i-j sicont[j+1],....cont[i].

int n, m, cp, p, cont[10001], fond[10001];

int r[10001];

int main(){

//citirea si construirea vectorilor cu conturi si fonduri ale clientilor premiumint x, a, y, i, rest, s, u;f>>n;for (i=1; i<=n; i++){

f>>x>>y; a=x; u=a%10; while (a>9) a/=10;if(a==u) cont[++cp]=x, fond[cp]=y;

}g<<cp<<'\n';//determinarea submultimii de clienti premium pentru care suma fondurilor este

divizibila cu cp, algoritmul bazat pe principiul cutiei lui Dirichlets=0;for (i=1; i<=cp; i++){

s=s+fond[i];if (s%cp==0){

x=1; y=i; break;}else{

rest=s%cp;if (r[rest]==0) r[rest]=i;else {

x=r[rest]+1; y=i; break;}

}



Ana Intuneric

Ana Întuneric25

}//afisarea conturilor clientilor selectatig<<y-x+1<<'\n';for (int i=x; i<=y; i++)

g<<cont[i]<<' ';f.close();g.close(); return 0;

}

sport

La ora de sport, cei N elevi din clasă s-au aliniat pe un singur rând în faţa profesorului. Nu au încercat să seordoneze după înălţime, deoarece ştiau că profesorul are propria metodă de ordonare, pe care o aplică la

începutul fiecărei ore. Profesorul alege un elev, pe care-l trimite la unul dintre cele două capete ale rândului.Procedeul se repetă până când şirul de elevi este ordonat crescător după înălţime. Copiii s-au gândit să-lajute pe profesor să-şi perfecţioneze metoda, astfel încât numărul de elevi care vor fi mutaţi prin acestprocedeu la un capăt sau la celălalt al şirului să fie minim. Cerinţă Cunoscând numărul de elevi, înălţimile şi poziţiile lor iniţiale în şir, determinaţi numărul minim de mutări pecare profesorul de sport trebuie să le aplice, pentru a ordona şirul de elevi, crescător după înălţime.Date de intrareFişierul de intrare sport.in conţine pe prima linie numărul natural N reprezentând numărul de copii. Pe linia adoua, se găsesc N numere naturale distincte: H[1], H[2], …, H[N], separate prin câte un singur spaţiu. Al i-

lea număr de pe linie reprezintă înălţimea copilului care se află pe poziţia i înainte de orice operaţie demutare.Date de ieşire În fişierul de ieşire sport.out se va scrie pe prima linie un număr natural M, reprezentând numărul minim demutări pe care profesorul le poate face pentru a sorta şirul de elevi, crescător după înălţime. Restricţii şi precizări 1 <N ≤ 1000 1 ≤ H[i] ≤ 10000 sport.in sport.out Explicaţie

42 1 3 5

1 Profesorul mută elevul de înălţime 1 la capătul din stânga: 1 2 3 5

33 2 1

2 Profesorul are la dispoziţie mai multe variante cu minimum 2 mutări.Prezentăm una dintre acestea:

Mută elevul de înălţime 1 la capătul din stânga: 1 3 2Mută elevul de înălţime 3 la capătul din dreapta: 1 2 3

53 7 2 6 9

3 Minimum 3 mutări. Una dintre variante este: Mută elevul de înălţime 7 la capătul din dreapta: 3 2 6 9 7Mută elevul de înălţime 2 la capătul din stânga: 2 3 6 9 7Mută elevul de înălţime 9 la capătul din dreapta: 2 3 6 7 9

Fie G este şirul obţinut din H prin sortare. Vom face următoarele observaţii:G se compune din 3 secvenţe de numere: S1, S2 şi S3. Prima secvenţă, S1, este constituită din cele maimici N1 elemente. A fost obţinută prin N1 operaţii de mutare la începutul şirului. A doua secvenţă, S2,alcătuită din cele mai mari N2 elemente, s-a creat la celălalt capăt al şirului, prin N2 operaţii de mutare lasfârşit. A treia secvenţă, S3, este cuprinsă între primele două şi este formată din elementele şirului care nuau fost mutate. Cele trei secvenţe (mulţimi ) sunt evident ordonate crescător şi reuniunea lor este întregul şirG.Exemplu:

H = ( 3, 7, 4, 5, 2, 9, 8, 6, 1 )G = ( 1,2, 3, 4, 5, 6, 7, 8, 9 )

S1 are N1 = 2 elemente: (1, 2).S2 are N2=3 elemente: (7, 8, 9 ),S3 are 4 elemente: (3, 4, 5, 6).Pentru un număr minim de mutări, este nevoie de un număr maxim de elemente în S3, adică în mulţimea deelemente care nu vor fi mutate. Ideea este de a căuta în şirul sortat G, cea mai lungă secvenţă consecutivăS3 căreia îi corespunde un subşir al şirului H, format din aceleaşi elemente. În exemplu, este vorba deelementele marcate cu roşu în şirul H. Evident, elementele subşirului din H sunt ordonate, însă nu sunt

neaparat consecutive. Se porneşte de la fiecare poziţie din G, începând cu poziţia 1 şi se caută cea mailungă secvenţă căreia să-i corespundă un subşir crescător în H, reţinând maximul max al lungimilorsecvenţelor găsite. Se afişează N – max. Complexitatea soluţiei este O(N*N).int H[10000]; // inaltimile copiilorint G[10000];int N,aux,poz,max,sortat;



Ana Intuneric

Ana Întuneric26

int main(){

fin >> N;int i, j;for ( i = 1; i <=N; i++ ){

f >> H[i]; G[i] = H[i];}

// se sorteaza G pentru a se obtine configuratia finala a sirului de copii

do{sortat=1;for( i = 1; i <=N - 1; i++ )

if ( G[i] > G[i+1]){

aux = G[i];G[i] = G[i+1];G[i+1]=aux;sortat=0;}

}while(!sortat);

max = 0;for (i = 1; i <=N; i++){ // Se cauta cel mai lung subsir din H

poz = i; // care are aceleasi elemente cu ale unei

// secvente consecutive de elemente din Gfor (j = 1; j <=N && poz<=N; j++)

if (H[j] == G[poz] ) poz++;if(poz - i > max ) max = poz - i;// max - numarul de copii care nu se muta

}g << N - max << '\n';g.close();f.close();return 0 ;

}

bal Un grup de fete şi băieţi participă la balul bobocilor. Ca să evite aglomeraţia de pe ringul de dans,organizatorii au realizat o programare în care fiecărui participant i se alocă o perioadă de timp în care se vaafla pe ringul de dans.Cerinţă Scrieţi un program care să determine numărul maxim de perechi, fată-băiat, care se pot forma cu persoaneleaflate pe ringul de dans la un moment dat.Date de intrareFişierul de intrare bal.in conţine pe prima linie numerele naturale n şi m reprezentând numărul de fete şinumărul de băieţi participanţi la bal. Pe următoarele n linii se găsesc câte două numere naturale xi yi,(1<=i<=n) separate printr-un spaţiu reprezentând intervalul închis de timp în care se va afla pe ring fiecarefată. Pe următoarele m linii se găsesc câte două numere naturale xj yj, (1<=j<=m) separate printr -un spaţiureprezentând intervalul închis de timp în care se va afla pe ring fiecare băiat. Date de ieşire Fişierul de ieşire bal.out va conţine o singura linie pe care va fi scris un singur număr natural reprezentând

numărul maxim de perechi determinat. Restricţii 1 <= n <= 100 000 1 <= m <= 100 000 1 <= xi <= yi <= 1 000 000 1 <= xj <= yj <= 1 000 000Exemple

bal.in bal.out

3 311 161 86 94 208 1713 18

2

Vom crea doi vectori (B – baieti si F – fete) astfel :pentru fiecare xi,yi (intervalul in care un copil sta pe scena ) B[xi]++,B[yi] –, respectiv F[xi]++,F[yi] – Cu ajutorul unei parcurgeri pana la 1000005 vom avea la fiecare moment numarul de baieti si fete de pescena (initial fiind 0, adaugam sau scadem in functie de B[pasi]/F[pasi].



Ana Intuneric

Ana Întuneric27

Avem astfel MAX(pasi) = MAX(MAX(pasi-1),MIN(B[pasi],F[pasi]));

#define MAX(a,b) (a) > (b) ? (a) : (b)#define MIN(a,b) (a) < (b) ? (a) : (b)int b[1000001],f[1000001];int n,m;int i,x,y;int maxP;int ft,bt;int main(){

f>>n>>m;for(i = 1; i <=n; i++){

f>>x>>y;b[x]++;b[y+1]--;

}for(i = 1; i<=m; i++){

f>>x>>y;f[x]++;f[y+1]--;}for(i=1;i<=1000000;i++){

if(f[i] || b[i]){

if(f[i]==1) ft++;if(b[i]==1) bt++; maxP = MAX(maxP,MIN(ft,bt));

}

if(f[i]==-1) ft--;if(b[i]==-1) bt--;}g<<maxP<<endl;f.close(); g.close();return 0;

}

CartiVasile se joaca un joc foarte interesant. El are un pachet de N carti de joc (numerotate distinct de la 1 la N).Cartile din pachet sunt amestecate. Vasile se uita la fiecare carte din pachet incepand cu prima, pana ajungela cartea cu numarul 1, pe care o scoate din pachet. Apoi cauta cartea cu numarul 2, cartea cu numarul 3,s.a.m.d. De fiecare data incepe cautarea de unde a ramas (de la cartea care urmeaza dupa ultima cartescoasa din pachet). De fiecare data cand ajunge la sfarsitul pachetului, Vasile bate din palme si continua

cautarea de la inceputul pachetului. Cand ultima carte din pachet este eliminata, jocul se termina.Cerinta Scrieti un program care sa determine de cate ori bate din palme Vasile in timpul unui joc.Date de intrare Prima linie a fisierului de intrare carti1.in contine un numar natural N, reprezentand numarulde carti din pachet. Urmatoarele N linii contin numerele cartilor de joc, in ordinea in care acestea se afla inpachet.Date de iesire Fisierul de iesire carti1.out contine o singura linie pe care se afla numarul cerut.Restrictii 1<=N <= 100000Exemplu carti1.in carti1.out32 1 3

2

73 6 7 1 5 4 2 3Vom construi un vector poz, pozitia initiala a fiecarei carti. Totul se reduce la numarul elemente careindeplinesc conditia poz[i]>poz[i+1].

int n,i,nrpalme,poz[20000],x;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21b 1 1 -1 -1 1 -1f 1 1 1 -1 -1 -1bt 1 2 1 0 1 0ft 1 2 3 2 1 0maxP 2

http://www.worldit.info/articole/algoritmica-articole/probleme/problema-carti/

http://www.worldit.info/articole/algoritmica-articole/probleme/problema-carti/



Ana Intuneric

Ana Întuneric28

int main(){

f>>n;for (i=1;i<=n;i++){f>>x; poz[x-1]=i;}for (i=1;i<=n-1;++i)if (poz[i]>poz[i+1]) nrpalme++;g<<nrpalme<<"\n";

f.close(); g.close(); return 0;}

bazeExistă numere care au proprietatea că se scriu, în două baze diferite, prin trei cifre identice. De exemplu,numărul 273(10) în baza 9 se scrie 333(9) şi în baza 16 se scrie 111(16).Cerinţă Concepeţi un program care să determine toate numerele mai mici ca N care au această proprietate. Date de intrareFişierul de intrare BAZE.IN va conţine pe prima linie numărul N. Date de ieşire În fişierul de ieşire BAZE.OUT se vor scrie numerele determinate, fiecare pe câte un rând. Pentru fiecarenumăr se vor scrie, separate prin câte un spaţiu, numărul în baza 10 şi cele 2 baze în care numărul respectivare proprietatea din enunţ. Restricţii 0<N<=32000 ExempluBAZE.IN BAZE.OUT300 273 9 16

int n, bmax, nr, NrBaze, b, Limita,baza[10];#define MIN(a,b) (a) < (b) ? (a) : (b)

int bazab(int nr, int b)//verifica daca nr in baza b are 3 cifre identice {

int c[100], i=0; while(nr){c[i]=nr%b;if((i)&&(c[i]!=c[i-1])) return 0;nr/=b;i++; if(i>3) return 0;

}if(i<3) return 0;if((c[0]==c[2])) return 1;return 0;

}

int main(){

f>>n;

// daca x este baza, atunci x*x+x+1<=n--

x^2+x-n+1<=0--

int((-1+sqrt(4*n-3))/2) bmax=(-1+sqrt(4*n-3))/2;

for(nr=7;nr<=n;nr++)//7 in baza 10 este 111 in baza 2 { NrBaze=0;Limita=MIN(bmax, nr);for(b=2; b<=Limita; b++)

if(bazab(nr,b)){ NrBaze++; baza[NrBaze]=b;

}if(NrBaze==2) g<<nr<<’ ‘<<baza[1]<<’ ‘<<baza[2];


}



Ana Intuneric

Ana Întuneric29

PanglicaGigel are o panglică alcătuită din benzi de 1 cm lăţime, colorate în diverse culori. Panglica are N benzicolorate cu C culori, culori pe care le vom numerota de la 1 la C. Gigel vrea ca la ambele capete ale pangliciisă aibă aceeaşi culoare, dar cum nu poate schimba culorile benzilor, singura posibilitate rămâne tăierea unorbucăţi de la capete.Cerinţă Scrieţi un program care să determine modul de tăiere a panglicii astfel încât la cele două capete să fie benzide aceeaşi culoare, iar lungimea panglicii obţinute să fie maximă. Date de intrareFişierul de intrare PANGLICA.IN conţine: – pe prima linie numerele naturale N şi C separate printr-un spaţiu; – pe următoarele N linii descrierea panglicii: pe fiecare linie un număr natural de la 1 la C, reprezentând înordine culorile fâşiilor ce alcătuiesc panglica. Date de ieşire Fişierul de ieşire PANGLICA.OUT va conţine următoarele 4 numere: – pe prima linie numărul de fâşii rămase; – pe linia a doua numărul culorii care se află la capete; – pe linia a treia câte fâşii trebuie tăiate de la începutul panglicii iniţiale; – pe linia a patra câte fâşii trebuie tăiate de la sfârşitul panglicii iniţiale.

Restricţii şi precizări

2

N

10000 1 C 200 Dacă există mai multe soluţii alegeţi pe cea în care se taie cât mai puţin din partea de început a panglicii. Exemplul 1 Exemplul 2PANGLICA.IN PANGLICA.OUT PANGLICA.IN PANGLICA.OUT

6 3 4 5 2 41 2 1 22 1 2 11 1 1 03 22 2

3Se citesc datele, se memoreaza pentru fiecare culoare pozitia (indicele) pe care apare prima data si ultimadata. Cautam apoi culoarea pentru care diferenta dintre prima si ultima aparitie este maxima. In acest fel esuficienta o singura parcurgere a sirului (doua "for"-uri pentru un sir de 10000 numere inseamna timp deexecutie prea mare). In plus, nu e nevoie nici de memorarea numerelor din sir.int n,c,i,k,max=0,cmax,pra[201],ulta[201];int main(){

//citiref>>n>>c;for(i=1;i<=n;i++){

f>>k;

if(pra[k]==0) pra[k]=i;//prima aparitie a culorii kulta[k]=i; //aici salvam, pe rand toate aparitiile culorii k, a.i. la urma

//ulta[k] va contine ultima aparitie}for(i=1;i<=c;i++)

if(ulta[i]-pra[i]+1>max){

max=ulta[i]-pra[i]+1; cmax=i;}

g<<max<<endl<<cmax<<endl<<pra[cmax]-1<<endl<<n-ulta[cmax]);f.close();g.close();return 0;

}

pluton În timpul acţiunii "Furtuna în deşert" din cauza unei furtuni de nisip, n soldaţi s-au rătăcit de plutoanele lor.După trecerea furtunii se pune problema regrupării acestora pe plutoane. Pentru aceasta se folosescplăcuţele de identificare pe care soldaţii le poartă la gât. Pe aceste plăcuţe sunt scrise numere care potidentifica fiecare soldat şi plutonul din care acesta face parte. Astfel, soldaţii din acelaşi pluton au numărul de



Ana Intuneric

Ana Întuneric30

identificare format din aceleaşi cifre, dispuse în altă ordine şi numerele de identificare sunt unice. Deexemplu, numerele de identificare 78003433, 83043073, 33347008 indică faptul ca cei trei soldaţi care lepoartă fac parte din acelaşi pluton. Cerinţă Fiind date cele n numere de pe plăcuţele de identificare, să se regrupeze cei n soldaţi pe plutoane,indicându-se numărul de plutoane găsite (un pluton refăcut trebuie să aibă minimum un soldat), numărul desoldaţi din cel mai numeros pluton, numărul de plutoane care au acest număr maxim de soldaţi precum şicomponenţa unui astfel de pluton (cu număr maxim de soldaţi regrupaţi).Date de intrareFişierul de intrare pluton.in conţine pe prima linie numărul n de soldaţi recuperaţi, iar pe fiecare dintreurmătoarele n linii câte un număr de identificare a celor n soldaţi.Date de ieşire Fişierul de ieşire pluton.out va conţine pe prima linie numărul de plutoane refăcute. Linia a doua va conţinenumărul de soldaţi din cel mai numeros pluton refăcut. Linia a treia va conţine numărul de plutoane care aunumărul maxim de soldaţi recuperaţi. Linia a patra va conţine componenţa unui astfel de pluton, cu numărmaxim de soldaţi recuperaţi, numerele de identificare ale soldaţilor din componenţă fiind scrise unul dupăaltul separate prin câte un spaţiu.Restricţii

0<n<=4000 0<număr de identificare <2000000000 Exemplu:

pluton.in pluton.out Explicaţii 101236663217890221331265510001322

632321 312 1231223

Au fost recuperaţi soldaţi din 6 plutoane distincte,cei mai mulţi soldaţi recuperaţi dintr -un plutonfiind în număr de 3. Există 2 plutoane cu numărmaxim de soldaţi recuperaţi (3), unul dintre elefiind format din soldaţii cu numerele 321 312 123.De remarcat că şi soluţia 1223 2213 1322 estecorectă.

s[k]=nr de identificare al soldatului kso[k]= nr de identificare al soldatului k cu cifrele ordonate descrescatorGr[]=grupelenrs[]=nr de soldati dintr-o grupa

int s[4001],so[4001],Gr[4001],nrs[4001];int n,nrp,maxi,nrmax;

int main(){long i,j,pmax,x;f>>n;for(i=1;i<=n;i++){

f>>s[i];Gr[i]=i;x=s[i];int fr[10]={0}; while(x>0){fr[x%10]++;x=x/10;}for(int c=9;c>=0;c--) while(fr[c]>0){ so[i]=so[i]*10+c;fr[c]--;}

}nrp=1;for(i=1;i<n;i++)if(Gr[i]>=i){

nrs[nrp]=1;for(j=i+1;j<=n;j++)

if(so[i]==so[j])

{Gr[j]=nrp;nrs[nrp]++;if(nrs[nrp]>maxi) {maxi=nrs[nrp];pmax=nrp;}}

Gr[i]=nrp;nrp++;

Nr 1223 123 666 321 7890 2213 312 655 1000 1322NrSort 3221 321 666 321 9870 3221 321 655 1000 3221Gr 1 2 3 4 5 6 7 8 9 10

nrs 1 2 3 2 4 1 2 5 6 1



Ana Intuneric

Ana Întuneric31

}nrp--;for(i=1;i<=nrp;i++)

if(maxi==nrs[i]) nrmax++;g<<nrp<<"\n"<<maxi<<"\n"<<nrmax<<"\n";for(i=1;i<=n;i++)

if(Gr[i]==pmax) g<<s[i]<<" ";g<<endl;f.close();g.close(); return 0;

}

bulineZaharel se plictisea la cursurile de la facultate si a inceput sa deseneze buline: a luat N bilete si pe fiecare adesenat un numar de buline, doar albe sau doar negre. A asezat cele N bilete in cerc si si-a pus urmatoareaintrebare: daca considera ca pe fiecare biletel este scris un numar intreg (x buline albe va reprezentanumarul x , iar x buline negre numarul -x) care este suma maxima a unei secvente de biletele aflate pe pozitiiconsecutive?Date de intrareFisierul de intrare buline.in va contine pe prima linie numarul natural N. Urmatoarele N linii vor contine catedoua numerele naturale , reprezetand numarul de buline de pe biletele si culoarea lor (0 pentru negrusi 1 pentru alb), in ordinea in care acestea au fost asezate.Date de iesireFisierul de iesire buline.out va contine trei numerele naturale: S P L cu semnificatia ca secventa de biletelede suma maxima are suma S, incepe pe pozitia P si are lungime L. Daca exista mai multe solutii se va afisacea cu pozitia P minima, iar daca exista mai multe solutii cu pozitia P minima se va afisa cea culungimea L minima.Restrictii si observatii 1 ≤ N ≤ 200.000 Numarul de buline de pe un biletel este cuprins in intervalul [0, 10.000] Biletele sunt numerotate cu numere de la 1 la N Avand in vedere ca biletele sunt asezate in cerc, dupa biletelul N urmeaza biletelul 1 Secventa aleasa trebuie sa fie formata din cel putin un biletel Pentru un test se va acorda 50% din punctaj pentru o solutie corecta, dar pentru care

valorile P sau L nu sunt minimeExemplubuline.in buline.out

51 02 14 03 15 1

9 4 4

ExplicatieCele 5 biletele, pe fiecare fiind trecut numarul sau si bulinele:

Problema este o variatie a unei probleme clasice: dandu-se un sir de N numere intregi sa se determine osecventa de suma maxima. Singura modificare este ca in aceasta problema sirul este circular. In prima partea solutiei nu vom lua in considerare faptul ca sirul este circular. Pentru a rezolva problema pentru un sirnormal exista o solutie clasica O(N). Se calculeaza pentru fiecare i secventa de suma maxima care setermina cu elementul i: este fie secventa de suma maxima care se termina la elementul i-1, la care seadauga elementul i, fie doar elementul i. O scurta descriere in pseudocod a acestui algoritm:

Vom trata acum si faptul ca sirul este circular. Astfel, trebuie verificate si secventele de forma i,i+1,...N-



Ana Intuneric

Ana Întuneric32

1,N,1,2,...j-1,j. Pentru a realiza acest lucru eficient precalculam un sir de sume partiale Si = A1 + A2 + ... + Ai = Si-1+Ai si un al doilea sir Smaxi = max(S1, S2,..., Si) = max(Smaxi-1, Si). Pentru un i fixat, cea mai bunasecventa de forma i,i+1,...N-1,N,1,2,...j-1,j se poate calcula in O(1) astfel: Smaxi-1+SN-Si-1.Un alt mod de a verifica secventele de forma i,i+1,...N-1,N,1,2,...j-1,j este daca observam ca suma acesteisecvente este de fapt suma tuturor elementelor din care se scade secventa j+1, j+2, ... i-2, i-1. Astfel neintereseaza o secventa de suma minima pe care sa o scadem din suma totala. Aceasta se poate determinacu o mica modificare a agloritmului pentru suma maxima sau inmultind elementele cu-1 si cautand osecventa de suma maxima.Complexitatea rezolvarii este O(N) doar cateva variabile aditionale pentru pozitie si lungime. , iar pentrureconstituirea solutiei sunt necesareint v[200001], sum[200001], smax[200001], ind[200001];int N, S, P, L;int main(){

int N, suma=0, st, x, i;f>>N;for (i = 1; i <= N; i++){

f>>v[i]>>x;if(x == 0) v[i] = -v[i];

}//calculam sumele partialefor(i = 1; i <= N; i++)

sum[i] = sum[i-1] + v[i];//determinam suma maxima care se termina pe pozitia ifor(i = 1; i <= N; i++)

if(smax[i-1] > sum[i]){

smax[i] = smax[i-1]; ind[i] = ind[i-1];}else {

smax[i] = sum[i]; ind[i] = i;}

for(i = 1; i <= N; i++){

if(suma <= 0){S = 0; st = i;}suma += v[i];if ( suma > S ){S = suma; P = st; L = i - st + 1;}

}

for( int i = 1; i <= N; i++ )if ( sum[N] - sum[i-1] + smax[i-1] > S ){

S = sum[N] - sum[i-1] + smax[i-1];P = i;L = N + ind[i-1] - i + 1;

}

g<<S<<' '<<P<<' '<<L;f.close();g.close(); return 0;

}

Numere mariVom considera ca numerele mari sunt vectori in care elementul de indice 0 indica lungimea numarului, iarcifrele sunt retinute in ordinea inversa decat cea a citirii.

Suma a doua numere marivoid add(int A[], int B[]){

int i, t = 0;for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)

A[i] = (t += A[i] + B[i]) % 10; A[0] = i - 1;

}



Ana Intuneric

Ana Întuneric33

Inmultirea unui numar mare cu un numar micvoid mul(int A[], int B){

int i, t = 0;for (i = 1; i <= A[0] || t; i++, t /= 10)

A[i] = (t += A[i] * B) % 10; A[0] = i - 1;

}

Inmultirea unui numar mare cu un numar marevoid mul(int A[], int B[]){

int i, j, t, C[NR_CIFRE]; memset(C, 0, sizeof(C));for (i = 1; i <= A[0]; i++){

for (t=0, j=1; j <= B[0] || t; j++, t/=10)C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;

if (i + j - 2 > C[0]) C[0] = i + j - 2;} memcpy(A, C, sizeof(C));

}

Scaderea a doua numere marivoid sub(int A[], int B[]){

int i, t = 0;for (i = 1; i <= A[0]; i++)

A[i] += (t = (A[i] -= ((i <= B[0]) ? B[i] : 0) + t) < 0) * 10;for (; A[0] > 1 && !A[A[0]]; A[0]--);

}

Impartirea unui numar mare la un numar micvoid div(int A[], int B)

{int i, t = 0;for (i = A[0]; i > 0; i--, t %= B)

A[i] = (t = t * 10 + A[i]) / B;for (; A[0] > 1 && !A[A[0]]; A[0]--);

}

Restul unui numar mare la un numar micint mod(int A[], int B){

int i, t = 0;for (i = A[0]; i > 0; i--)

t = (t * 10 + A[i]) % B;

return t;}

nextSe da un numar natural N. Sa gaseasca cel mai mic numar natural M mai mare sau egal cu N si divizibilcu D.Date de intrarePe prima linie din fisierul de intrare next.in se va gasi numarul N, iar pe a doua linie numarul D.Date de iesireIn fisierul de iesire next.out se va scrie pe prima linie numarul M.Restrictii 1 ≤ N < 101.000.000 2 ≤ D ≤ 1016 Pentru 50% din teste D ≤ 1.000.000

Exemplunext.in next.out



Ana Intuneric

Ana Întuneric34

4711

55

Folosind operatii pe numere mari se calculeaza restul lui N la numarul D. Fie R acest rest, se va aduna lanumarul N valoarea (D-R) mod D. Numarul astfel obtinut va reprezenta primul numar mai mare sau egaldecat N divizibil cu D. Complexitatea rezolvarii este O(lg N). int a[1000005], b[1000005];char s[1000005];

void add(int A[], int B[]){

int i,t = 0;for (i=1;i<=A[0]||i<=B[0]||t;i++){

t+=A[i]+B[i];//depasirea A[i]=t%10;t/=10;

} A[0]=i-1;//dimensiunea numarului suma o tin minte in A[0]

}

long long mod(int A[], long long B){

int i;long long t = 0;for (i = A[0]; i > 0; i--) t = (t * 10 + A[i]) % B;return t;

}

int main(){

long long d, r;int i;f.getline(s,1000005);for(i=0;i<strlen(s);i++)

a[++a[0]]=s[i]-'0';

reverse(a+1, a+a[0]+1);f>>d;r=mod(a, d);if(r>0) r=d-r; while(r){

b[++b[0]]=r%10;r/=10;

}add(a,b);for(i=a[0];i>0;i--) g<<a[i];f.close();g.close();return 0;

}

Idee

politic Î n Ţara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlamentdin care fac parte deputaţi cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prinnumere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic).Parlamentarii s-au asociat în partide politice în funcţie de doctrina fiecăruia. Oricare doi deputaţi ale cărordoctrine corespund unor numere consecutive fac parte din acelaşi partid. Prin ur mare, partidele vor fialcătuite din deputaţi ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputaţi, cu doctrinele 1,2,3,5 şi 6, atunci î nseamnă că aceştia sunt grupaţi în două partide: unul format din1,2 şi 3 şi altul din 5 şi 6.)Un guvern trebuie să beneficieze de susţinerea a mai mult de jumătate dintre parlamentari. De exemplu,dacă parlamentul este format din 7 deputaţi, atunci un guvern are nevoie de susţinerea a cel puţin 4 deputaţi. Pentru a putea guverna, partidele se pot grupa in coaliţii. Regula după care se asociază este urmatoarea:două partide A şi B, A având o doctrină mai de stânga, pot face parte din aceeaşi coaliţie doar dacă dincoaliţia respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A şi mai de



Ana Intuneric

Ana Întuneric35

stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputaţi cu orientările politice1,2,4,5,7 şi 8, atunci partidul format din 1 şi 2 nu se poate asocia cu partidul format din 7 şi 8 decât dacă dincoaliţia respectivă face parte şi partidul format din 4 şi 5.Cerinţă Fiind dat parlamentul din Ţara lui Papură Vodă printr -un şir ordonat strict crescător de numere naturalenenule, se cere să se stabilească numărul de partide parlamentare şi numărul variantelor de coaliţiemajoritară. Date de intrarePe prima linie a fişierului de intrare politic.in se află un număr natural nenul N, reprezentând numărul dedeputaţi din parlament. Pe a doua linie se află N numere naturale nenule separate prin câte un spaţiu, ordonate strict crescător,reprezentând doctrinele parlamentarilor.Date de ieşire Prima linie a fişierului politic.out va conţine un număr natural nenul X, reprezentând numărul de partide dinparlament, iar a doua linie va conţine un alt număr natural nenul Y, care reprezintă numărul de coaliţiimajoritare care se pot forma.Restricţii şi precizări 0 < N ≤ 20000 numerele din şir sunt mai mici sau egale cu 30000 pentru determinarea corectă a numărului de partide parlamentare se acordă 30%din punctaj, iar pentru

afişarea corectă a numărului de variante de coaliţie majoritară se acordă 70% din punctaj Exemplu

politic.in politic.out Explicaţie

101 2 3 5 6 8 10 11 14 15

54

Partidele parlamentare sunt:P1=(1,2,3),

P2=(5,6),P3=(8),P4=(10,11)şiP5=(14,15).Variantele de coaliţie majoritară sunt :P1+P2+P3, P1+P2+P3+P4, P2+P3+P4,

P2+P3+P4+P5.Se parcurge şirul de n numere reprezentând orientările politice ale deputaţilor şi se stabileşte m=numărul departide. În acelaşi timp se construieşte un vector v, cu m elemente, v[i]=numărul de deputaţi ai partidului i.Numărul de coaliţii majoritare se stabileşte în urma unei parcurgeri a vectorului v. Se folosesc două variabile,p şi u; p reprezintă numărul de ordine al celui mai de stânga partid dintr -o coaliţie majoritară, iar u va creştepână când partidele cu numere de ordine din intervalul [p,u] au suficienţi parlamentari încât să formeze ocoaliţie majoritară sau u depăşeşte m. Prin urmare, u reprezintă numărul de ordine al celui mai de stângapartid, cu proprietatea că secvenţa (p,p+1,…,u) este o coaliţie majoritară. Dacă partidele (p,p+1,…,u) potforma o coaliţie majoritară, atunci şi secvenţele (p,p+1,…,u,u+1), (p,p+1,…,u,u+1,u+2), … , (p,p+1,…,m) sunt coaliţii majoritare. Astfel se stabileşte numărul total de coaliţii majoritare având cel mai de stânga partidcu numărul de ordine p după formula m-u+1.În momentul în care u depăşeşte m, nu mai există coaliţiimajoritare având cel mai de stânga partid cu numărul de ordine p şi ne oprim. Algoritmul are complexitatea O(n), fiind necesare o parcurgere a şirului de parlamentari şi o parcurgere aşirului de partide (u va lua valori cuprinse între 1 şi m, fiecare valoare fiind luată o singură dată, iar m nupoate depăşi n).Un algoritm de complexitate O(n2) nu se încadrează în timp decât pentru o parte din teste. int p[15001],N,K,sum[14001];int main(){int N1,i,j,nr,xc,xp,coalitii;//citesc datele si formez coalitiile

f>>N>>xp;K = 0;nr = 1;for (i=1;i<N;i++)

{f>>xc;if(xc == xp+1) nr++;else

{ p[K++] = nr; nr = 1;

}xp = xc;

} p[K++] = nr;



Ana Intuneric

Ana Întuneric36

//Calculez numarul de coalitiisum[0] = 0;for (i=1;i<=K;i++) sum[i] = sum[i-1]+p[i-1];

coalitii = 0; N1 = N/2;for (i=1;i<K;i++)for (j=i+1;j<=K;j++)

if (sum[j]-sum[i-1] > N1) coalitii++;

g<<K <<’’<<coalitii<<endl;f.close();g.close();return 0;}

nasturiPresupunem că în fiecare pătrat al unei table de şah (3<n<31, n par) avem câte un nasture. Ştiind că luăm xnasturi de pe tablă scrieţi un program care să precizeze dacă putem face această operaţie astfel încât pefiecare linie şi coloană să rămână un număr par de nasturi.Exemplu:

n=4, x=4---------------o soluţie posibilă:

Observăm că avem 3 situaţii posibile: x≥n2-2 sau x≤2 Nu există soluţ iex=4k, caz în care formăm k grupe de câte 4pătrăţele, pe coloane, începând din colţul dinstânga sus

x=4k+2, caz în care putem considera că x=4k+6

şi formăm k grupe de câte 4 pătrăţele, pecoloane, începând din colţul din stânga sus, iar încolţul din dreapta jos luăm 6 nasturi ca în imagine

int a[32][32],x,n,i,s,j;int main(){

f>>n>>x;if(x>=n*n-2 || x<=2 || x%2==1)

g<<"Nu exista solutie!"<<'\n';

else{if(x%4==0)

for(j=1;j<=n;j=j+2)for(i=1;i<=n;i=i+2){

if(s>=x) break;a[i][j]=1;a[i+1][j]=1;a[i][j+1]=1;a[i+1][j+1]=1;s+=4;;//calculez cati nasturi iau in S

}else{

a[n-2][n-1]=1;a[n-2][n]=1;a[n-1][n-2]=1;a[n-1][n]=1;a[n][n-2]=1;a[n][n-1]=1;x-=6;for(j=1;j<=n && x;j=j+2)

for(i=1;i<=n && x;i=i+2){

a[i][j]=1;a[i+1][j]=1;a[i][j+1]=1;a[i+1][j+1]=1;



Ana Intuneric

Ana Întuneric37

x-=4; //scad din x cati nasturi iau}

}for(i=1;i<=n;i++){

for(j=1;j<=n;j++)if(a[i][j]==0)g<<’N;else g<<’ ‘;

g<<'\n';}

}

f.close();g.close();return 0;}

Generare tablou

Scrieti un program care sa genereze un tablou bidimensional cuproprietatile:-contine N linii si N coloane;-elementele sale sunt numere naturale nenule;-suma elementelor este egala cu numarul natural nenul S;-pe nici o linie si nici o coloana nu exista 2 elemente identice;-diferenta dintre cel mai mare si cel mai mic element al tabloului este

minima.Programul va citi numerele naturale nenule N si S si va afisa tabloul generat.

Idee: Pentru ca diferenţa dintre valoarea maximă şi cea minimă din tablou să fie minimă trebuie să avemvalori identice distribuite pe diagonale paralele cu diagonala principală în matricea extinsă (conmpletămmatricea cu n-1 linii). Aflăm valoarea cea mai mică pe care o distribuim pe diagonala principală ţinând contcă pe celelalte, în ordine, distribuim valori consecutive.

Ex: N=3, S=50 x=4 (S-S1)/n=1 (S-S1)%n=2Calculăm suma după prima distribuţie:

S1=n*x+n*(x+1)+…+n*(x+n -1)=n

2

*x+n

2

*(n-1)/2Dacă presupunem că S1 este egal cu S, aflămvaloarea lui x:x=(S- n2*(n-1)/2)/ n2

Diferenţa dintre S şi S1 se distribuie începând cuultima diagonală.Nr. de diagonale incrementate cu 1este:nrdt=(S-S1)/n, iar nrdr=(S-S1)%n reprezintănumărul de elemente incrementate pe ultimadiagonală, adică cea incompletă.

Soluţia fără matrice:x= (S/n-n*(n-1)/2)/n;

if(a>0) g<<0;else{

S1=n*n*x+n*(n-1)/2);nrdt=(S-S1)/n;//nr. de diagonale actualizate integralnrdr=(S-S1)%n;//nr. de elemente de actualizat de pe diagonala nrdt+1for(i=1;i<=n;i++){for(j=1;j<=n;j++){

d=(n+j-i)%n+1; //diagonala elementului i,jif(((d>n-nrdt)||(d==n-nrdt)&&(j<=nrdr))

g<<x+d<<' ';

else cout<<x+d-1<<' ';}g<<endl;

}}

N=3, S=512 dintre solutiile posibile:



Ana Intuneric

Ana Întuneric38

ParantezeDată o secvență de 0 și 1, unde 0 înseamnă paranteză deschisă '(', iar 1 înseamnă paranteză închisă ')',spuneți dacă secvența reprezintă o expresie corectă de paranteze și dacă da calculați numărul maxim deparanteze una într-alta. Exemplu: 0 1 0 0 1 0 1 1 este corectă și are factorul de imbricare de 2, pe cîndsecvența 0 0 0 1 1 1 0 este incorectă. Nu aveți voie să folosiți tablouri (vectori sau matrice).Putem rezolva problema observând următoarele reguli valabile pentru orice expresie corectă: oriunde "rupem" expresia, în partea stângă vom avea un număr de paranteze deschise mai mare sau egalcu cele închise la final numărul de paranteze închise trebuie să fie egal cu cele închiseDacă ambele condiții se îndeplinesc expresia e corectă. Prima condiție trebuie îndeplinită pentru fiecarepoziție de rupere. int n, a, i, sum, max;int main(){

f>>n; while (i<n && sum>=0){

if(sum>max) max=sum;f>>a;if(a==0)sum++;else sum--;

i++;}if(sum==0)

g<<"Parantezarea este corecta, avand factorul de imbricare "<<max;else g<<"Parantezarea este incorecta";f.close();g.close();return 0;

}

Selecție Dat un șir de n numere și o poziție k în acel șir să se spună ce element s -ar afla pe acea poziție dacă șirul arfi sortat.Solutie: ideea de rezolvare este să folosim primul pas al algoritmului quicksort și anume pivotarea. Prinpivotare înțelegem separarea vectorului original în două regiuni: cea din stînga cu numere mai mici sau

egale cu pivotul, iar cea din dreapta cu numere mai mari sau egale cu pivotul (nu este o greșeală, în ambelepărți putem avea numere egale cu pivotul). Pivotul poate fi ales la întîmplare, orice element din vector. Odatăce avem subșirurile v[1..i] și v[i+1..j] ne vom întreba în ce interval se află k și vom relua problema selecției înacel interval, mai mic. Acest algoritm duce la o complexitate medie liniară, O(n). Ca și quicksort, pe cazul celmai rău complexitatea este O(n2).Voi prezenta mai jos o implementare nestandard a pivotării, în care căutăm în paralel în stînga un elementmai mare, iar în dreapta unul mai mic, apoi le interschimbăm. Pivotul nu ajunge neapărat pe poziție. Iată oimplementare posibilă: int v[1000000];int main(){int n, k, i, begin, end, b, e, pivot, aux;

f>>n>>k;for ( i = 1; i <=n; i++ )f>>v[i];k--; begin = 1; end = n; while ( begin < end ){ b = begin; e = end; pivot = v[(begin + end) / 2]; // alegem un pivot la jumatea vectorului while ( b <= e ){ while ( v[b] < pivot ) b++; while ( v[e] > pivot ) e--;if ( b <= e )

{aux = v[b]; v[b] = v[e]; v[e] = aux; b++; e--;}}// acum [begin..e] sunt mai mici sau egale cu pivotul// si [b..end] sunt mai mari sau egale cu pivotul



Ana Intuneric

Ana Întuneric39

if( k <= e ) end = e;else if ( k >= b ) begin = b;else begin = end = k;}g<<v[k]<<’\n’;f.close();g.close();return 0;}

triunghi

Se consideră untriunghi

alcătuit din numere naturale scrise pe n linii ca în figuraalăturată. Liniile triunghiului sunt numerotate de la 1 la n, începând cu linia de labaza triunghiului (linia de jos), iar poziţiile pe linie sunt numerotate începând cu 1de la stânga la dreapta.Fiecare număr din triunghi, exceptând pe cele de pe linia1, este egal cu suma numerelor aflate imediat sub el, în stânga şi respectiv în dreapta lui.Cerinţă Cunoscând câte un număr de pe fiecare linie a triunghiului, determinaţi toatenumerele de pe linia 1.Date de intrareFişierul de intrare triunghi.in conţine pe prima linie numărul natural nreprezentând numărul de linii din triunghi. Pe următoarele n linii sunt descrise

informaţiile despre triunghi. Mai exact, pe linia i (1≤i≤n) dintre cele n se află două numere naturale separateprin spaţiu pi vi indicând poziţia şi respectiv valoarea numărului cunoscut de pe linia i a triunghiului.Date de ieşire Fişierul de ieşire triunghi.out va conţine o singură linie, pe care se găsesc n numere naturale separate princâte un spaţiu, reprezentând în ordinea de la stânga la dreapta numerele scrise pe linia 1 a triunghiului.Restricţii 1 n 1000 1 pi n+1-i, pentru 1≤i≤n Toate numerele din triunghi sunt numere naturale cu cel mult 18 cifre. Pentru elevii care implementează în C: când utilizaţi MINGW, dacă citiţi/afişati valori de tip long long intfolosind scanf(), respectiv printf() utilizaţi specificatorul de format %I64d.Exemplu

triunghi.in triunghi.out Explicaţii 54 42 53 132 251 45

1 2 3 4 2 Triunghiul este:45

20 258 12 133 5 7 6

1 2 3 4 2unsigned long long val[1001],l1[1001],l2[1001];int poz[1001],n;

void citire(){

f>>n; unsigned int i;for(i=n;i>=1;i--)f>>poz[i]>>val[i];

}

void sol(){

unsigned long long v;int p,i,j;l1[poz[1]]=val[1];for(i=2;i<=n;i++){

p=poz[i]; v=val[i];l2[p]=v;

for(j=p+1;j<=i;j++) l2[j]=l1[j-1]-l2[j-1];for(j=p-1;j>=1;j--) l2[j]=l1[j]-l2[j+1];for(j=1;j<=i;j++) l1[j]=l2[j];

}}

1 2 3 4 51 452 20 253 8 12 134 55 4Cu galben sunt valorile initiale.Reconstituirea o fac de sus in jos.Reconstruirea o fac in 2 vectori l1 si l2.

L1 45L2 20 25

L1 20 25L2 8 12 13...



Ana Intuneric

Ana Întuneric40

void afis(){

int i;for(i=1;i<=n;i++) g<<l1[i]<<" ";g<<endl;

}

int main(){

citire();sol();afis();f.close();g.close();return 0;

}

expresie

Costel are de r ezolvat o temă grea la matematică: având la dispoziţie N numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi N-3 operaţii de adunare, astfel încât rezultatul calculelor să fie cel maimare posibil. Nu este permisă modificarea ordinii numerelor date.De exemplu, dacă N=5 şi numerele sunt 4, 7, 1, 5, 3, operaţiile pot fi aşezate 4 + 7 * 1 + 5 * 3, 4 * 7 *1 + 5 + 3e.t.cCerinţă Scrieţi un program care să aşeze două operaţii de înmulţire şi N-3 operaţii de adunare între cele N valori dateastfel încât valoarea expresiei obţinute să fie maximă.Date de intrareFişierul de intrare expresie.in are următoarea structură: Pe prima linie se află un număr natural N, reprezentând numărul elementelor date. Pe următoarele linii se află cele N numere naturale date, fiecare pe câte o linie.

Date de ieşire Fişierul de ieşire expresie.out va conţine, pe prima linie, valoarea maximă obţinută prin evaluarea expresiei. Restricţii şi precizări 4 <=N<= 1000Numerele date sunt numere naturale între 1 şi 10000 Exempluexpresie.in expresie.out Explicaţie 54715

3

44 Valoarea maximă se obţine prin aşezarea operaţiilor subforma:4 * 7 + 1 + 5*3

Memorăm cele N numere naturale date în tabloul unidimensional t. Calculăm suma celor N valori, deoarecepresupunem că, iniţial, avem în expresia noastră doar operaţii de adunare. Există două cazuri posibile pentru a introduce două operaţii de înmulţire în expresie: Cazul 1. Cele două înmulţiri sunt consecutive. Obţinem valoarea maximă a expresiei în variabila suma1, luândpe rand toate tripletele de numere consecutive t[i], t[i+1], t[i+2] şi alegând tripletul pentru care suma-t[i]-t[i+1]-t[i+2]+t[i]*t[i+1]*t[i+2] este maximă.Cazul 2. Cele două operaţii de înmulţire nu sunt aşezate consecutiv. Obţinem valoarea maximă a expresiei învariabila suma1, luând pe rand toate perechile (t[i], t[i+1]) şi (t[j], t[j+1]) şi alegând combinaţia pentru care suma-t[i]-t[i+1]-t[j]-t[j+1]+t[i]*t[i+1]+t[j]*t[j+1] este maxima.Deoarece numerele date sunt între 1 şi 10000, valoarea expresiei poate depăşi tipul de date int.Pentru exemplul din enunt, avem:T 1 2 3 4 5

4 7 1 5 3N=5Suma iniţială este suma=20.Cazul 1. Avem expresiile posibile:4*7*1+5+3 = 364+7*1*5+3 = 424+7+1*5*3 = 26deci valoarea maximă de până acum este 42 Cazul 2. Avem expresiile posibile:

4*7+1*5+3 = 28+5+3 = 364*7+1+5*3 = 28+1+15= 444+7*1+5*3 = 4+7+15=26deci valoarea maximă este 44



Ana Intuneric

Ana Întuneric41

int N,v[1001],i,j;long long S1,S,Smax;int main(){

//citiref>>N;for(i=1;i<=N;i++){f>>v[i];S=S+v[i];}//*** cazul 1for(i=1;i<=N-2;i++)

{S1=S+v[i]*v[i+1]*v[i+2]-v[i]-v[i+1]-v[i+2];if(S1>Smax)Smax=S1;

}//*+* cazul 2for(i=1;i<=N-3;i++)

for(j=i+2;j<=N-1;j++){

S1=S+v[i]*v[i+1]+v[j]*v[j+1]-v[i]-v[i+1]-v[j]-v[j+1];if(S1>Smax)Smax=S1;

}//afisareg<<Smax<<endl;


Urmatoarea permutare lexicografica

int n,i,v[222],imax,maxi,j,aux,m,ok;int main(){

f>>n;for(i=1;i<=n;i++) f>>v[i];//cautam primul i de la dreapta la stanga cu pp cerutai=n; while(v[i]<v[i-1] && i>1) i--;//cautam cel mai mic element din stanga lui i mai mare ca elimax=i;maxi=n+1;for(j=i;j<=n;j++)

if(v[i-1]<v[j] && v[j]<maxi){maxi=v[j];imax=j;}//le interschimbamaux=v[i-1];v[i-1]=v[imax];v[imax]=aux;//sortam crescator elementele din dreapta sa m=n;do{

ok=1;for(j=i;j<n;j++)

if(v[j]>v[j+1]){aux=v[j];v[j]=v[j+1];v[j+1]=aux;ok=0;} m--;

}while(!ok);

for(i=1;i<=n;i++) g<<v[i]<<' ';f.close();g.close();return 0;

}



Ana Intuneric

Ana Întuneric42

Elementul majoritarDat un vector cu n elemente să se spună dacă conține un element majoritar. Un element majoritar este unelement care apare de cel puțin n/2 + 1 ori. Încercați să dați o soluție mai bună decît sortarea. Solutie: dacă există un element majoritar, maj, rezultă că fiecare din elementele vectorului diferite de maj poatefi cuplat cu un element egal cu maj astfel încît după ce toate cuplările au fost făcute să rămînă cel puțin unelement maj necuplat. Ideea de rezolvare este să simulăm această cuplare. Vom porni cu primul element alvectorului ca un candidat de element majoritar. Parcurgem elementele vectorului ținînd minte cîți candidaținecuplați avem. De fiecare dată cînd dăm peste un element egal cu candidatul incrementăm numărul de

elemente necuplate. Cînd dăm peste un element diferit scădem numărul de elemente necuplate. Dacă la unmoment dat vom avea zero candidați necuplați și mai vine un element diferit de candidat rezultă că am eliminatdin vector un număr egal de candidați și non-candidați, drept pentru care putem reporni problema pentruvectorul rămas: vom considera elementul curent drept candidat, cu o apariție. La final vom rămîne cu un candidat ce trebuie acum verificat: numărăm de cîte ori apare el in vector printr -oparcurgere. Dacă apare de măcar n/2+1 ori am găsit elementul majoritar, altfel el nu există. Complexitateaacestei soluții este liniară, O(n), algoritmul făcînd două parcurgeri prin vector. int v[3000000], n, i, nr, maj;int main(){f>>n;for ( i = 1; i <= n; i++ )f>>v[i];maj = v[1]; nr = 1; // cautam candidatul la element majoritarfor ( i = 2; i <=n; i++ )

if ( v[i] == maj ) nr++;// cita vreme avem maj incrementam numarul de maj gasiteelse {

nr--;// altfel decrementam numarul de majif ( nr < 0 )

{ // daca am scazut sub zero maj = v[i]; // alegem drept candidat elementul curentnr = 1; // care apare o data

}}

// verificare candidat la element majoritarnr = 0;for ( i = 1; i <=n; i++ ) // numaram de cit ori apare maj in vectorif ( v[i] == maj ) nr++;if(nr > n/2 ) // daca maj apare de mai mult de n/2 ori este majoritar

g<< maj<<’ ‘<<nr<<’\n’ ; else g<<"-1\n";f.close();g.close();return 0;}

maxpConsiderăm un şir de numere a1, a2, ..., aN. O secvenţă nevidă în acest şir este de forma ai, a i+1, ..., a j, unde i<= j. De exemplu, pentru N=4 şi şirul 2 3 4 3, secvenţele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3,3. Definim puterea unui element ai ca fiind numărul de secvenţe care-l conţin pe ai şi în care ai este strict maimare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul 2 3 4 3 puterea

elementului a1 este 1 (fiind maxim doar în secvenţa formată din el însuşi), a elementului a2 este 2 (a2 fiindmaxim în secvenţele 2 3 şi 3), a elementului a3 este 6 (fiind maxim în secvenţele 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 şi 43), iar a elementului a4 este 1.

Cerinţe Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul deelemente din şir care au cea mai mare putere.

Date de intrare Fişierul maxp.in conţine pe prima linie numărul natural N, iar pe a doua linie, în ordine, numerele naturale a 1,a2, ..., aN separate prin câte un spaţiu.

Date de iesire Fişierul maxp.out va conţine pe prima linie un număr natural ce reprezintă puterea cea mai mare a unuielement din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şircare au cea mai mare putere.



Ana Intuneric

Ana Întuneric43

Restricţii şi precizări: 2 <= N <= 200000 Elementele şirului sunt numere naturale şi au cel mult 6 cifre Se acordă 50% din punctaj pentru determinarea corectă a celei mai mari puteri a unui element din șir și 50% din

punctaj pentru determinarea numărului de elemente din şir care au cea mai mare putere.Exemplumaxp.in maxp.out Explicaţii

79 3 4 5 1 2 2

121

Elementul 5 de pe poziţia 4 este maxim în 12 secvenţe:3 4 5, 3 4 5 1, 3 4 5 1 2, 3 4 5 1 2 2, 4 5,4 5 1, 4 5 1 2, 4 5 1 2 2, 5, 5 1, 5 1 2,5 1 2 2, deci puterea lui este 12. Este singurul element care areaceastă putere, celelalte elemente având puteri mai mici.

maxp.in maxp.out Explicaţii 61 0 7 7 2 6

32

Elementele din poziţiile 3 şi 4 sunt maxime în 3 secvenţe, deci puterealor este 3. Celelalte elemente au puteri mai mici.

Solutie de complexitate O(n)Vom determina pentru fiecare element a[i] al şirului numărul p[i] de secvenţe în care a[i] este maxim. Pentru

aceasta, se construiesc doi vectori stşi dr de lungime n în care:

st[i] = numărul de valori mai mici ca a[i] aflate imediat în stânga poziţiei i. dr[i] = numărul de valori mai mici ca a[i] aflate imediat în dreapta poziţiei i. Construcţia vectorului st se poate realiza în O(n), ţinând cont de faptul că dacă un element a[i] este maxim însecvenţa a1, a2, ..., ai, atunci orice număr mai mare ca ai şi aflat în dreapta lui ai va fi automat mai mare ca toateelementele precedente. Asemănător se construieşte şi vectorul dr parcurgând de la dreapta la stângaelementele şirului a. Elementul a[i] va fi maxim într-un număr de secvenţe egal cu p[i] = (st[i] + 1) * (dr[i] + 1). Cunoscând valorile dinvectorul p, putem imediat determina valoarea maximă şi de câte ori apare.

int a[200001],st[200001], dr[200001];long long rez;int i,j,k,n,ct;long long pmax, putere;int main(){

//citiref >> n;

for(i=1;i<=n;i++) f>>a[i];//constructie vector st

a[n+1]=a[0]=2000000000;st[1]=0;dr[n]=0;for (i=1;i<=n;i++){j=i-1; while (a[j]<a[i])

j = j - st[j] - 1;st[i]=i-j-1;}

//constructie vector drfor (i=n;i>=1;i--){

j = i+1; while (a[j]<a[i])

j = j + dr[j] + 1;dr[i]=j-i-1;

}//calcul putere

for (i=1;i<=n;i++){

putere = st[i] + dr[i] + 1 + st[i]*dr[i];if (putere > pmax)



Ana Intuneric

Ana Întuneric44

{pmax = putere;ct=1;}

elseif (putere == pmax) ct++;}g<< pmax << "\n" << ct << "\n";f.close();g.close();return 0;

}

Matrice

Păianjen Să ne imaginăm o reţea planară, formată din noduri situate în punctele de coordonate întregi, fiecare nod fiindunit prin bare paralele cu axele de coordonate de cele 4 noduri vecine. Un păianjen este plasat iniţial în origineasistemului de coordonate. La fiecare secundă, păianjenul se poate deplasa din nodul în care se află în unul dinnodurile vecine.

Scrieţi un program care să determine în câte moduri se poate deplasa păianjenul din poziţia iniţială, într -opoziţie finală dată prin coordonatele ei x şi y, în timpul cel mai scurt. (ONIG 2001, VII-VIII)ExemplePentru x=1 şi y=2, numărul de moduri determinat va fi 3. Pentru x=2 şi y=3, numărul de moduri va fi 10. Soluţie Cum păianjenul se deplasează numai de-a lungul barelor, el poate să ajungă (în timpul cel mai scurt) în poziţia

(x, y) numai din poziţia (x-1, y) sau din poziţia (x, y-1). Dacă notăm cu nr(x,y) numărul de modalităţi prin carepăianjenul poate ajunge în timp minim în poziţia (x, y), atunci deducem că: nr(0,y)=nr(x,0)=1;nr(x,y)=nr(x-1,y)+nr(x,y-1), pentru orice x,y>0.

unsigned int nr[21][21];int main(){

int x, y;f>>x>>y;

for (int i=0; i<=x; i++) nr[i][0]=1;for (int j=0; j<=y; j++) nr[0][j]=1;for (i=1; i<=x; i++)

for (j=1; j<=y; j++)nr[i][j]=nr[i-1][j]+nr[i][j-1];g<<nr[x][y]<<endl;

f.close();g.close(); return 0;}

Maximum Sum. Se dă o matrice de dimensiuni NxN cu elemente întregi. Se cere determinarea unei submatricia carei elemente au suma maximă. N ≤100 si numerele din matrice€ [-127, 127].

De exemplu pentru matricea: submatricea de sumă maximă este următoarea:0 -2 -7 09 2 -6 2

-4 1 -4 1-1 8 0 -2

9 2-4 1

-1 8

Vom păstra în sum[i][j] suma tuturor elementerlor a[i1][j1] cu proprietatea că 1 <= i1 <= i, şi 1 <= j1 <= j. Aceste

X

Y

O



Ana Intuneric

Ana Întuneric45

sume vor fi calculate astfel: sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] – sum[i-1][j-1]. Acum pentru a calcula suma elementelor din matricea cu colţurile (i1, j1), (i2, j2) unde i1 <= i2 şi j1 <= j2 estesufficient să facem calculul sum[i2][j2]–sum[i1 –1][j2] –sum[i2][j1-1]+sum[i1-1][j1-1].

int a[101][101],i,j,n,i1,j11,i2,j2,i1max,j11max,i2max,j2max;long s[101][101],S,Smax;

int main(){

f>>n;for(i=1;i<=n;i++)

for(j=1;j<=n;j++){f>>a[i][j];s[i][j] = a[i][j] + s[i][j-1] + s[i-1][j] - s[i-1][j-1];}

for(i1=1;i1<=n;i1++)for(j11=1;j11<=n;j11++)

for(i2=i1;i2<=n;i2++)for(j2=j11;j2<=n;j2++){

S=s[i2][j2]-s[i1-1][j2]-s[i2][j11-1]+s[i1-1][j11-1];if(S>Smax){Smax=S;i1max=i1;i2max=i2;j11max=j11;j2max=j2;}

}for(i=i1max;i<=i2max;i++)

{for(j=j11max;j<=j2max;j++)g<<a[i][j]<<" ";g<<"\n";

}f.close(); g.close(); return 0;

}

cladiriInstitutul de Fizică a Pământului studiază efectele unui potenţial cutremur folosind simulări

computerizate. Harta plană a clădirilor de pe un teritoriu oarecare este reprezentată folosind coordonatele GPS în plan, longitudine şi latitudine, faţă de un reper considerat de coordonate (0,0), ca în figura de mai jos.

Fiecare dintre clădirile aflate pe hartă,au două coordonate GPS, (Longitudine,Latitudine) şi un Grad de rezistenţă lacutremure.

Un cutremur se poate produce în oricepunct de coordonate de pe hartă, numit centrulseismului şi are o anumită intensitate. Undade şoc se propagă sub forma unor pătrateconcentrice cu centrul seismului, numite nivele

(nivelul 0 reprezintă centrul seismului, nivelul 1primul pătrat concentric, nivelul 2 al doileapătrat concentric şi aşa mai departe).

Intensitatea slăbeşte la fiecare pătratconcentric cu centrul seismului cu câte ounitate. Clădirile sunt afectate de cutremurdoar dacă gradul lor de rezistenţă la cutremureste mai mic sau egal cu intensitateacutremurului în poziţia clădirii.Cerinţă Scrieţi un program care să citească coordonatele centrului seismului şi intensitatea sa în acel punct, precum şicoordonatele clădirilor şi gradul lor de rezistenţă la cutremur, şi apoi să determine: a) numărul N total de clădiri afectate; b) numărul M maxim de clădiri afectate pe un nivel;c) numerele nivelelor cu M clădiri afectate, în ordinea crescătoare a numerelor acestor nivele. Date de intrareFişierul de intrare cladiri.in conţine: pe prima linie, trei numere naturale Long Lat Intensitate, separate prin câte un spaţiu, reprezentând



Ana Intuneric

Ana Întuneric46

coordonatele centrului seismului şi respectiv intensitatea sa; pe fiecare dintre următoarele linii, până la sfârşitul fişierului, câte trei numere naturale Long Lat Grad,separate prin câte un spaţiu, reprezentând coordonatele unei clădiri, respectiv gradul de rezistenţă la cutremur. Date de ieşire Fişierul de ieşire cladiri.out va conţine trei linii: pe prima linie se va scrie numărul natural N reprezentând numărul total de clădiri afectate; pe a doua linie se va scrie numărul natural M reprezentând numărul maxim de clădiri afectate pe unnivel; pe a treia linie se vor scrie numerele nivelelor cu M clădiri afectate, în ordinea crescătoare a numereloracestor nivele.Restricţii şi precizări 0 Long, Lat, Grad, Intensitate 10000; 0 < număr clădiri 100000; în centrul seismului se pot afla clădiri; nu există mai multe clădiri cu aceleaşi coordonate; 52% din punctaj se poate obţine pe teste de intrare cu 0 Long, Lat, Grad, Intensitate 100 se acordă punctaje parţiale din punctajul acordat pe fiecare test, astfel: 25% pentru cerinţa a), 25%pentru cerinţa b), respectiv 50% pentru cerinţa c).

Exemple:

cladiri.in cladiri.out Explicaţii 12 7 1110 9 210 7 313 5 18 11 48 7 615 4 315 9 1013 10 116 8 4

832 4

Numărul N total al clădirilor afectate este 8. Numărul M maxim de clădiri afectate pe acelaşi nivel este 3 şi esteatins pe nivelele 2 şi 4.

3 3 3

1 3 52 4 73 2 9

0

0

Intensitatea cutremurului este 3 şi nu poate afecta cele 3 clădiri, deci

avem N=0 clădiri afectate, iar maximul clădirilor afectate pe un niveleste, evident, M=0.

Timp maxim de executare/test: 1 secundă

Soluţia problemei constă în crearea unui vector al nivelelor, care va păstra numarul cladirilor de pe acel nivelcare sunt afectate de cutremur (gradul de rezistenţă mai mic sau egal cu intensitatea cutremurului în acel loc).Identificarea nivelului pe care se găseşte o clădire se realizează prin calculul expresiei max(xc-x,yc-y), unde(xc,yc) – coordonatele clădirii si (x, y) – coordonatele epicentrului cutremurului. Odata creat vectorul nivelelor,se identifică elementul maxim şi care dintre nivele au număr maxim de cladiri afectate.

ifstream f("cladiri.in");ofstream g("cladiri.out");int x,y,ic,nivel[10001],nivmax;

// testam daca o cladire rezista cutremurului void test(int xf,int yf,int grf){

int mx=abs(xf-x),my=abs(yf-y),niv=max(mx,my);if (niv>nivmax) nivmax=niv;if (grf<=ic-niv) nivel[niv]++;

}

// calculam numarul total de cladiri distruse int total(vector v,int n)

{int s=0,i;for(i=0;i<=n;i++)s=s+v[i];return s;



Ana Intuneric

Ana Întuneric47

}

// determinam nivelul pe care se gasesc cele mai multe cladiri distruseint maxim(int v[],int n){

int Max=v[0],i;for(i=1;i<=n;i++)

if (v[i]>Max) Max=v[i];return Max;

}

int main(){

int xc,yc,gr,i,m,c=0;f>>x>>y>>ic;// citesc succesiv datele cladirilor while (f>>xc>>yc>>gr){

test(xc,yc,gr);c++;}g<<total(nivel,nivmax)<<"\n"; m=maxim(nivel,nivmax);g<<m<<"\n";

// determin nivelele cu cele mai multe cladiri distruseif (m)for(i=0;i<=nivmax;i++)

if (nivel[i]==m) g<<i<<" ";g<<"\n";f.close();g.close();return 0;

}

Altă rezolvare (de 100 de puncte) int xc,yc,pas;int main(){

int Int,x1,y1,z1,M=0,N=0,nivel[10001]={0},i,nrp,dif1,dif2;

f>>xc>>yc>>Int; while(f>>x1>>y1>>z1){

dif1=abs(yc-y1); dif2=abs(xc-x1);if(dif1>=dif2) nrp=dif1;else nrp=dif2;if(z1<=Int-nrp) {N++;nivel[nrp]++;}

}//a)

g<<N<<'\n';//b)

M=nivel[0];for(i=1;i<=Int;i++)

if(nivel[i]>M) M=nivel[i];g<<M<<'\n';//c)

for(i=0;i<=Int;i++)if(nivel[i]==M) g<<i<<' ';

g<<'\n';f.close();g.close();return 0;

}

cartele În sediul unei firme se intră doar cu ajutorul cartelelor magnetice. De câte ori se schimbă codurile de acces,cartelele trebuie formatate. Formatarea presupune imprimarea unui model prin magnetizare. Dispozitivul în carese introduc cartelele, numit cititor de cartele, verifică acest model. Toate cartelele au aceleaşi 51ensiuni,suprafaţa pătrată şi grosimea neglijabilă. Cele două feţe plane ale unei cartele se împart fiecare în NxN celulepătrate, identice ca 51ensiuni. Prin formatare unele celule, marcate cu negru în exemplu, se magnetizeazăpermiţând radiaţiei infraroşii să treacă dintr -o parte în cealaltă a cartelei. În interiorul cititorului de cartele se



Ana Intuneric

Ana Întuneric48

iluminează uniform una dintre feţele cartelei. De cealaltă parte fasciculele de lumină care străbat cartela suntanalizate electronic. Pentru a permite accesul în clădire modelul imprimat pe cartelă trebuie să coincidă exactcu modelul şablonului care memorează codul de intrare. Prin fanta dispozitivului nu se pot introduce mai multecartele deodată. Cartela se poate introduce prin fantă cu oricare dintre muchii spre deschizătura fantei şi cuoricare dintre cele două feţe orientate către şablon. După introducere cartela se dispune în plan paralel cuşablonul, lipit de acesta, astfel încât cele patru colţuri ale cartelei se suprapun exact cu colţurile şablonului.Modelele imprimate pe cele două feţe ale unei cartele sunt identice. Unei celule magnetizate îi corespunde pefaţa opusă tot o celulă magnetizată, iar unei celule nemagnetizate îi corespunde una nemagnetizată. O celulă

magnetizată este transparentă pentru radiaţia infraroşie indiferent de faţa care se iluminează. Un angajat al firmei are mai multe cartele. Pe unele dintre acestea a fost imprimat noul cod de intrare, iar pealtele sunt coduri mai vechi. Pentru a afla care sunt cartelele care-i permit accesul în sediul firmei angajatul estenevoit să le verifice pe toate, introducându-le pe rând, în toate modurile pe care le consideră necesare, în fantacititorului de cartele.

Cerinţă Scrieţi un program care determină care dintre cartele permite accesul în sediul firmei. Date de intrareFişierul de intrare cartele.in conţine pe prima linie două numere naturale N şi C despărţite printr -un spaţiu. Neste 51ensiunea tablourilor care reprezintă modelul şablon şi modelele cartelelelor. C reprezintă numărul decartele. Urmează C+1 blocuri de câte N linii fiecare. Primul bloc de N linii codifică şablonul. Următoarele Cblocuri de câte N linii codifică fiecare câte o cartelă. Pe fiecare linie sunt câte N valori întregi, despărţite printr -un singur spaţiu. Celulelor magnetizate le corespunde valoarea 1, iar celorlalte, valoarea 0. Date de ieşire În fişierul de ieşire cartele.out se vor scrie C linii, câte o valoare pe linie. Pe linia i se va scrie valoarea 1 dacăcartela i permite accesul în clădire şi valoarea 0 în caz contrar.Restricţii şi precizări 1 <N, C <= 50Exemplu

cartele.in cartele.out Explicaţie 3 20 1 00 0 11 0 01 0 00 0 1

0 1 00 0 10 0 10 1 0

10

Datele de intrare corespund situaţiei din figură. Cartela 1 se potriveşteperfect şablonului, dacă se roteşte în sens trigonometric cu 90 de grade.Cartela 2 nu se potriveşte şablonului, indiferent de modul în care seintroduce în fantă.

Pentru fiecare cartela, se compara element cu element, matricea care reprezinta sablonul, cu urmatoareletablouri:1. Cartela2. Cartela rotita cu 90 grade3. Cartela rotita cu 180 grade4. Cartela rotita cu 270 grade

Daca nu s-a gasit o coincidenta, se intoarce cartela, printr-o operatie de oglindire fata de linia i = n / 2, (sau fata

de coloana j = n / 2), dupa care se compara sablonul cu urmatoarele tablouri:5. Cartela oglindita6. Cartela oglindita rotita cu 90 grade7. Cartela oglindita rotita cu 180 grade

Cartela 2ablon Cartela 1



Ana Intuneric

Ana Întuneric49

8. Cartela oglindita rotita cu 270 gradeRotirile se pot face in sens trigonometric sau orar. Daca s-a gasit o coincidenta la oricare dintre pasii de maisus, se opreste cautarea, se afiseaza 1 si se trece la prelucrarea urmatoarei cartele.Daca nici dupa pasul 8 nu s-a gasit o potrivire exacta, se afiseaza 0 si se trece la prelucrarea urmatoareicartele.int a[51][51], b[51][51]; // sablonul, cartelaint aux[51][51];int n, C;int Egale(){

for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)

if ( a[i][j] != b[i][j] ) return 0;return 1;

}void Inverseaza()// intoarce cartela pe partea cealalta (oglindire fata de linia i = n/2){

int i, j, aux1;for (i = 1; i <= n / 2; i++)

for (j = 1; j <= n; j++){aux1 = b[i][j]; b[i][j] = b[n-i+1][j]; b[n-i+1][j] = aux1;}

}void Roteste() // rotire 90 grade in sens trigonometric {

int i, j;for (i = 1; i <= n; i++)

for (j = 1; j<= n; j++) aux[n-j+1][i] = b[i][j];for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++) b[i][j] = aux[i][j];}void Rezolva(){

f >> n >> C;int i, j, r;int identice = 1;for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++) f>>a[i][j];for (int k = 1; k <= C; k++)

{identice = 1;for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++){

f >> b[i][j]; if ( b[i][j] != a[i][j] ) identice = 0;}

for (int fata = 1; fata <= 2 && !identice; fata++) // pentru fata 1 si 2 {

for (r = 1; r <= 4 && !identice; r++) // la a patra rotatie se revine la matricea initiala{

Roteste(); // cu 90 in sens trigonometric if ( Egale() ) identice = 1;

}if ( !identice ) Inverseaza();

}if ( identice ) g<< 1 << '\n';else g << 0 << '\n';

}}int main(){ Rezolva();f.close();g.close();return 0;}



Ana Intuneric

Ana Întuneric50

Tehnica Greedy

Algoritmii greedy (greedy = lacom) sunt în general simpli şi sunt folosiţi la probleme de optimizare, cum ar fi: săse găsească cea mai bună ordine de executare a unor lucrări pe calculator, să se găsească cel mai scurt drum într-un graf etc. In cele mai multe situaţii de acest fel avem:

1. o mulţime de elemente (lucrări de executat, vârfuri ale grafului etc) 2. o funcţie care verifică dacă o anumită mulţime de candidaţi constituie o soluţie posibilă, nu neapărat optimă,a problemei3. o funcţie care verifică dacă pentru o mulţime de candidaţi este posibil să o completăm astfel încât să obţinemo soluţie posibilă, nu neapărat optimă, a problemei 4. o funcţie de selecţie care alege la orice moment cel mai potrivit element, încă nefolosit 5. o funcţie soluţie care spune când s-a ajuns la soluţie.

Pentru a rezolva o anumită problemă, un algoritm greedy construieşte soluţia pas cu pas. Iniţial, mulţimeacandidaţilor selectaţi este vidă. La fiecare pas, încercăm să adăugăm acestei mulţimi cel mai potrivit element,conform funcţiei de selecţie. Dacă, după o astfel de adăugare, mulţimea de elemente obţinută nu mai poateduce la soluţie, se elimină ultimul element adăugat; acesta nu va mai fi niciodată considerat. Dacă, dupăadăugare, mulţimea de elemente selectate poate duce la soluţie, ultimul element adăugat va rămâne de acum

încolo în ea. De fiecare dată când lărgim mulţimea elementelor selectate, verificăm dacă această mulţime nuconstituie o soluţie posibilă a problemei noastre. Dacă algoritmul Greedy funcţionează corect, prima soluţie găsită va fi totodată o soluţie optimă a problemei. O întrebare firească este aceea dacă algoritmul Greedy duce totdeauna la soluţie optimă? Evident că nu. Suntsituaţii când soluţia găsită nu este optimă. Mai mult, pentru cele mai multe din probleme nu se cunosc algoritmiGreedy de rezolvare. Spre deosebire de Backtracking, algoritmul Greedy nu permite atunci când s-a observatcă nu se poate ajunge la soluţie pentru o anumită secvenţă de elemente, revenirea înapoi, pe niveleleanterioare.Pentru problemele care nu duc la soluţia optimă este necesar să se caute soluţii, chiar dacă nu optime, dar câtmai apropiate de acestea.

Problema spectacolelor_1

Managerul artistic al unui festival trebuie să selecteze o mulŢime cât mai amplă de spectacole ce pot fi jucate însingura sală pe care o are la dispoziţie. Stiind că i s-au propus n≤100 spectacole si pentru fiecare spectacol i i-afost anunţat intervalul în care se poate desfăşura [si, fi) (si reprezintă ora şi minutul de început, iar fi ora şiminutul de final al spectacolului i) scrieţi un program care să permită spectatorilor vizionarea unui număr cât maimare de spectacole. De exemplu, dacă vom citi n=5 şi următorii timpi: 12 30 16 3015 0 18 010 0 18 3018 0 20 4512 15 13 0spectacolele selectate sunt: 5 2 4.Soluţie

Ordonăm spectacolele crescător după ora de final. Selectăm iniţial primul spectacol (deci cel care se terminăcel mai devreme). La fiecare pas selectăm primul spectacol neselectat, care nu se suprapune cu cele dejaselectate (deci careîncepe după ce se termină ultimul spectacol selectat).

int inceput[100], sfarsit[100], nr[100];int n, i, h, m, n1,ok, ultim, aux;int main(){f >> n; //citirefor (i=1; i<=n; i++){

nr[i]=i; //transformam timpul in minutef>>h>>m; inceput[i]=h*60+m;

f>>h>>m; sfarsit[i]=h*60+m;}//ordonam spectacolele crescator dupa ora de finaln1=n;



Ana Intuneric

Ana Întuneric51

do{

ok=1;for (i=1; i<m; i++)

if (sfarsit[nr[i]]>sfarsit[nr[i+1]]){aux=nr[i];nr[i]=nr[i+1];nr[i+1]=aux; ok=0;}

m--;} while (!ok);

for (ultim=1, i=1; i<=n; i++)if (inceput[nr[i]]>=sfarsit[nr[ultim]])

{g<<nr[i]<<' '; ultim=i;}g<<endl;f.close();g.close();return 0;}

Problema programarii spectacolelor_2Intr-o sala de spectacol trebuie planificate n spectacole intr-o zi. Pentru fiecare spectacol se cunosc ora deinceput si ora de terminare (numere intregi). Sa se planifice un numar maxim de spectacole astfel inct sa nu fiedoua spectacole care sa se suprapuna.Exemplu:truct spectacol{int s,d;}sp[101],salese[101];int n,k;

void citire(){

fin>>n;for(int i=1;i<=n;i++) f>>sp[i].s>>sp[i].d;

}

void ordonare(){

int i,j,m=n,ok;spectacol aux;do{

ok=1;for(i=1;i<m;i++)if(sp[i].d>sp[i+1].d){

aux=sp[i]; sp[i]=sp[i+1];sp[i+1]=aux;ok=0;

} m--;

}while(!ok);}

void afisare(){

for(int i=1;i<=k;i++)g<<salese[i].s<<","<<salese[i].d<<" ";

}

void greedy(){

int i;k=1;salse[1]=sp[1];for(i=2;i<=n;i++)

if(salese[k].d<sp[i].s) salese[++k]=sp[i];}

int main(){

citire();ordonare();greedy();afisare();f.close();g.close();return 0;

date.in date.out:72 4

8 115 65 83 77 89 12

2,4 5,6 7,8 9,12



Ana Intuneric

Ana Întuneric52

}

reactivi Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele saudeprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecarereactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura destocare a acestuia.Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura

(constantă) care va fi in interiorul acelui frigider (exprimată într -un număr întreg de grade Celsius). Cerinţă Scrieţi un program care să determine numărul minim de frigidere necesare pentru stocarea reactivilor chimici.Date de intrareFişierul de intrare react.in conţine: – pe prima linie numărul natural N, care reprezintă numărul de reactivi; – pe fiecare dintre următoarele N linii se află min max (două numere întregi separate printr-un spaţiu);numerele de pe linia x+1 reprezintă temperatura minimă, respectiv temperatura maximă de stocare a reactivuluix.Date de ieşire Fişierul de ieşire react.out va conţine o singură linie pe care este scris numărul minim de frigidere necesar.Restricţii

1 <=N <= 8000 -100 <= minx<= maxx<= 100 (numere întregi, reprezentând grade Celsius), pentru orice x de la 1 la N un frigider poate conţine un număr nelimitat de reactivi

Exemplereact.in react.out react.in react.out react.in react.out3-10 10-2 520 50

2 42 55 710 2030 40

3 5-10 1010 12-20 107 107 8

2

Soluţie Intervalele de temperatură pot fi considerate segmente de dreaptă. Problema cere, de fapt, determinarea unuinumăr minim de puncte astfel încât orice segment să conţină cel puţin unul dintre punctele determinate. Vom sorta în primul rând intervalele de temperatură crescător după temperatura minimă si descrescător dupătemperatura maximă. Deschidem un frigider si plasăm primul reactiv în acest frigider. Pentru frigiderul curent reţinem temperaturaminimă şi temperatura maximă (intervalul de temperatură în care poate fi setat). Parcurg succesiv reactivii (în ordine) si pentru fiecare reactiv verificăm dacă el poate fi plasat în frigiderul curent(pentru aceasta, trebuie ca intersecţia dintre intervalul de temperatură al frigiderului şi intervalul de temperaturăal reactivuluisă fie nevidă). Dacă da, plasăm acest reactiv în frigiderul curent (actualizând corespunzător intervalul de

temperatură al frigiderului). În caz contrar, deschidem un nou frigider (intervalul de temperatură al acestuifrigider va fi intervalul reactivului plasat în el).

int N;int ti[8000], tf[8000];/*ti[i]=temperatura minima pentru reactivul itf[i]=temperatura maxima pentru reactivul i */

int main (){int nf, poz, miny, maxx, aux, i, j, icx, icy,N1;//citire

f>>N;

for (i=1;i<=N;i++) f>>ti[i]>>tf[i];//sortare N1=N;do{



Ana Intuneric

Ana Întuneric53

ok=1;for (i=1; i<N1; i++)

if(ti[i]>ti[i+1] ||ti[i]==ti[i+1] && tf[i]<tf[i+1]){aux=ti[i];ti[i]=ti[i+1]; ti[i+1]=aux;aux=tf[i];tf[i]=tf[i+1]; tf[i+1]=aux;ok=0;}

N1--;}while(!ok);

/* deschidem un frigider si plasam primul reactiv

icx=temperatura minima de functionare a frigiderului curenticy=temperatura maxima de functionare a frigiderului curentnf=numarul de frigidere deschise */

nf=1; icx=ti[1];icy=tf[1];//parcurgem ceilalti reactivi in ordinefor (i=2; i<=N; i++){

// verific daca intervalul curent icx, icy se intersecteaza cu intervalul de temperatura al reactivului i miny=icy;if (miny>tf[i]) miny=tf[i]; maxx=icx;if (maxx<ti[i]) maxx=ti[i];if (maxx <= miny) //actualizam intervalul de temperatura

{icx=maxx;icy=miny;}else //deschid un nou frigider

{nf++;icx=ti[i];icy=tf[i];

}}g<<nf<<'\n';f.close();g.close();return 0;}

BereN prieteni, numerotaţi de la 1 la N , beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşteC i – costul berii lui preferate. Din când în când, câte un prieten, fie el k , cumpără câte o bere pentru o secvenţăde prieteni aflaţi pe poziţii consecutive la masă, incepand cu el, în sensul acelor de ceasornic. El este dispus săcheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni. Cerinţă Se cere numărul de beri pe care le va cumpăra fiecare prieten k în limita sumei x de bani de care dispune. Încaz că x este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim N beri.Date de intrarePrima linie a fişierului de intrare br.in conţine două numere naturale N şi T separate printr-un spaţiureprezentând numărul de prieteni şi respectiv numărul de prieteni care doresc să facă cinste prietenilor săi. A doua linie a fişierului de intrare conţine N numere naturale C 1, C 2 … C N , separate prin câte un spaţiu,reprezentând costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul Ci.Fiecare din următoarele T linii conţine câte două numere separate printr-un spaţiu: k 1 x 1 k 2 x 2

… k T x T precizând indicele câte unui prieten care face cinste şi respectiv suma de bani de care acesta dispune.. Date de ieșire Fișierul de ieșire br.out va conţine T linii, fiecare cu un singur număr Di reprezentând numărul de beri pe care leva cumpăra prietenul k i cu suma de bani x i in condiţiile problemei. Restricții 1 ≤ N ≤ 15.000 1 ≤ T ≤ 10.000 1 ≤ Ci ≤ 100 1 ≤ ki ≤ N 1 ≤ xi ≤ 3.000.000

Un program corect, care se încadrează în timp pentru T ≤ 4000 , va obţine cel puţin 30 de puncte Un program corect, care se încadrează în timp pentru N ≤ 2000 , va obţine cel puţin 60 de puncte Prietenii beau numai berea lor preferată.Exemplu



Ana Intuneric

Ana Întuneric54

br.in br.out Explicație

5 410 5 15 22 131 324 501 94 200

3405

Prietenul 1 cumpără câte o bere pentru el şi pentru prietenii 2 , 3. Costul celor 3 berieste 30 .Prietenul 4 cumpără 4 beri: câte una pentru el şi pentru prietenii 5 , 1, 2 . Costul celor4 beri este 50 .Cu 9 bani prietenul 1 nu poate cumpăra nici măcar berea lui. Prietenul 4 cumpără 5 beri. Costul celor 5 beri este sub limita de cost 200 .

1. Citim initial intr-un vector pret, reprezentand costul berilor celor N prieteni si calculam si suma totala acosturilor berilor.2. Pentru fiecare i de la 1 la T verificam daca suma totala este depasita de suma prietenului i, atunciafisam valoarea N, daca valoarea este mai mica decat a primului prieten , iar in caz contrar scadem si nedeplasam la urmatorul prieten

Soluţie de 70 de puncte #include<fstream.h>int n,t,st;char pret[15001];ifstream f("br.in");

ofstream g("br.out");

int main(){

f>>n>>t;for(int i = 1; i <= n; i++)

{f>>pret[i]);st=st+pret[i];}int i,pr,s,total;for(i = 1; i <= t; i++){

f>>pr>>s;

if(st <= s) g<<n<<”\n”; else if(s < pret[pr]) g<<"0\n";

else{total = 0; while(s >= pret[pr]){

s = s-pret[pr++];if(pr == n+1) pr = 1;total++;

}g<<total<<”\n”;

}}f.close(); g.close();return 0;}



Ana Intuneric

Ana Întuneric55

DepozitConsiderăm un depozit cu n (n≤1000) camere, care conţin respectiv cantităţilede marfă C1, C2, …, Cn,(numere naturale). Scrieţi un program care să determineun grup de camere cu proprietatea că sumacantităţilor de marfă pe care le conţin sepoate împărţ i exact la cele n camioane care o transportă. SoluţieProblema solicită determinarea unei submulţ imi a unei mulţimicu n elemente, divizibilă tot cu n. Vomconstrui sumele S1, S2, ..., Sn şi resturilepe care acestea le dau prin împărţ ire la n astfel:

S1=C1 ⇒ R1=S1 % nS2=C1+C2 ⇒ R2=S2 % n...Si=C1+C2+...+Ci ⇒ Ri=Si % n...Sn=C1+C2+...+Cn⇒ Rn=Sn % n

Cazul I: Există un rest Ri=0. În acest caz suma Si este divizibilă cu n, prinurmare camerele solicitate sunt1, 2, ..., i.Cazul II: Toate resturile sunt diferite de 0. Prin urmare R1, R2, ..., Rn sunt nresturi care iau valori înmulţiimea {1, 2, ..., n-1}. În mod obligatoriu există celpuţin două resturi egale: Ri=Rj (i<j), adică Si ş i Sj

produc acelasi rest laîmpărţ irea cu n ⇒ suma Sj-Si este divizibilă cu n, deci camerele solicitate sunt i+1, i+2, ..., j.Observaţ ii1. Soluţia nu este unică. Procedeul prezentat produce o soluţie posibilă. 2. Rezolvarea se bazează pe Principiul cutiei al lui Dirichlet .

int SR[100], n, i, j, k, c;int main(){

f>>n; //calculez sumele de la citirefor (i=1; i<=n; i++)

{ f>>c;SR[i]=SR[i-1]+c;}

for (i=1; i<=n; i++) SR[i]%=n; //calculez resturile for (i=1; i<=n; i++) //caut un rest = 0

if (SR[i]==0){for(k=1;k<=i; k++) g<<k<<' '; f.close();g.close();return 0;} //cazul II, caut doua resturi egale for (i=1; i<n; i++)

for (j=i+1; j<=n; j++)if (SR[i]==SR[j]){for(k=i+1;k<=j;k++) g<<k<<' ';


Şiruri de caractere

TEXTVasile lucrează intens la un editor de texte. Un text este format din unu l sau mai multe paragrafe. Oriceparagraf se termină cu Enter şi oricare două cuvinte consecutive din acelaşi paragraf sunt separate prinspaţii (unul sau mai multe). În funcţie de modul de setare a paginii, numărul maxim de caractere care încap în pagină pe o linie este unic determinat (Max).Funcţia pe care Vasile trebuie să o implementeze acum este alinierea în pagină a fiecărui paragraf din textla stânga şi la dreapta. Pentru aceasta el va trebui să împartă fiecare paragraf în linii separate de lungime Max (fiecare linie terminată cu Enter). Împărţirea se realizează punând numărul maxim posibil de cuvintepe fiecare linie, fără împărţirea cuvintelor în silabe. Pentru aliniere stânga-dreapta, el trebuie să repartizezespaţii în mod uniform între cuvintele de pe fiecare linie, astfel încât ultimul caracter de pe linie să fie diferitde spaţiu, iar numărul total de caractere de pe linie să fie egal cu Max. Excepţie face numai ultima linie din



Ana Intuneric

Ana Întuneric56

paragraf, care rămâne aliniată la stânga (cuvintele fiind separate printr-un singur spaţiu, chiar dacă linia nueste plină). În general, este puţin probabil ca alinierea să fie realizabilă prin plasarea aceluiaşi număr de spaţii întreoricare două cuvinte consecutive de pe linie. Vasile consideră că este mai elegant ca, dacă între unelecuvinte consecutive trebuie plasat un spaţiu în plus faţă de alte perechi de cuvinte consecutive, acestea săfie plasate la începutul liniei.Cerinţă Scrieţi un program care să citească lungimea unei linii şi textul dat şi care să alinieze textul la stânga şi la

dreapta.Date de intrareFişierul de intrare text.in conţine pe prima linie Max, lungimea maximă a unui rând. Pe următoarele linii este scris textul. Date de ieşire Fişierul de ieşire text.out conţine textul aliniat stânga-dreapta.Restricţii

2<=Max<=1000 Lungimea maximă a oricărui cuvânt din text este 25 caractere şi nu depăşeşte Max. Lungimea unui paragraf nu depăşeşte 1000 de caractere. Soluţia este unică.

Exemple

text.in text.out Explicaţie 20Vasile are multe bomboane bune.

Vasile are multebomboane bune.

Pe prima linie au fost plasate câte3 spaţii între cuvinteleconsecutive.

text.in text.out Explicaţie 20Ana are mere.Ion are multe pere galbene?

Ana are mere.Ion are multe peregalbene?

Între Ion şi are există 2 spaţii, între are şi multe- 2 spaţii, iar între multe şi pere- 1 spaţiu.

Observaţi că paragraful Ana are mere. (care are lungimea mai mică decât 20) a rămas aliniat la stânga, iarultima linie din fiecare paragraf rămâne aliniată la stânga, cuvintele consecutive fiind separate printr-unsingur spaţiu.

#include <fstream>#include <string.h>using namespace std;ifstream f("text.in");ofstream g("text.out");char prg[1001];//memorez paragraful curentchar cuv[1001][26];//memorez cuvintele liniei curenteint Max,nrl,LgLinie;

void afiseaza_linie(int u){

int i, j, cate, rest, nrsp;if(u!=0)//ultima liniefor(i=0;i<nrl-1;i++) g<<cuv[i]<<' ';

else{

cate=Max-LgLinie; rest=cate%(nrl-1); nrsp=cate/(nrl-1);for(i=0;i<nrl-1;i++){

g<<cuv[i];for(j=0;j<=nrsp;j++) g<<' ';if(rest>0){g<<' ';rest--;}

}}

if(nrl>0)g<<cuv[nrl-1]<<endl;else g<<endl;}

void afiseaza_paragraf(){



Ana Intuneric

Ana Întuneric57

char *p;int LgCuv;LgLinie=-1; nrl=0; p=strtok(prg," ");//decupez primul cuvant while(p)

{LgCuv=strlen(p);//p=cuvantul curentif (LgLinie+LgCuv+1<=Max){strcpy(cuv[nrl],p); nrl++; LgLinie+=LgCuv+1;}else

{afiseaza_linie(0); //afisez linia curentanrl=1; LgLinie=LgCuv; strcpy(cuv[0],p);//trec la linia urmatoare

} p=strtok(NULL," ");//decupez urmatorul cuvant

}afiseaza_linie(1);//afisez cuvintele paragrafului

}

int main(){

f>>Max; f.get();//golesc buffer-ul de citire//citesc paragraf cu paragraf while(f.getline(prg,1001))

afiseaza_paragraf();f.close(); g.close();return 0;}

compLocuitorii planetei Eudora folosesc o reprezentare mai ciudată a numerelor naturale, astfel că orice numărnatural va fi scris notând câte mii, sute, zeci, respectiv unităţi conţine acesta. De exemplu, numărul 3207 sepoate reprezenta în mai multe moduri echivalente: 3m2s7u (3 mii 2 sute şi 7 unităţi), 32s0z7u (32 sute 0zeci şi 7 unităţi), 32s7u, 3207u, etc.Pentru a compara două numere naturale, eudorienii folosesc semnele < şi >, acestea având semnificaţiacunoscută şi pe Terra, iar pentru a calcula suma a două numere naturale utilizează semnul +. Pentru a testa abilităţile pământenilor în privinţa lucrului cu numere naturale, eudorienii au trimis pe Terra

un fişier text ce conţine N linii, fiecare linie fiind o comparaţie de forma: expresie1>expresie2sau

expresie1<expresie2Observaţi că o comparaţie este constituită din două expresii separate prin semnul < s au prin semnul >.O expresie este compusă dintr -un număr natural sau dintr -o sumă de două sau mai multe numere naturale,toate scrise în forma eudoriană. Fişierul nu conţine caractere spaţiu.

Cerinţă Scrieţi un program care determină câte dintre comparaţiile date utilizează semnul <, precum şi valoarea deadevăr a fiecărei comparaţii dintre cele N date (afişând 0 dacă acea comparaţie e falsă, respectiv 1 dacăacea comparaţie e adevărată).

Date de intrareFişierul comp.in conţine pe prima linie numărul natural nenul N, reprezentând numărul de comparaţii, iar pefiecare dintre următoarele N linii câte un şir de caractere corespunzător unei comparaţii.

Date de ieşire Fişierul comp.out va conţine pe prima linie un număr natural reprezentând numărul de comparaţii în care seutilizează semnul <. Urmează N linii, fiecare linie conţinând doar valoarea 0 sau valoarea 1. Valoarea de pea i-a linie dintre cele N este 0, dacă cea de-a i-a comparaţie din fişierul de intrare este falsă, respectiv 1 încaz contrar.

Restricţii 0 < N ≤1000 Numerele din fişier nu depăşesc în valoare numărul eudorian 1000m1000s1000z1000u. Lungimea fiecărei linii din fişier este cel mult 250. Punctaj . Dacă numărul de comparaţii care utilizează semnul < este corect se va acorda 20% din



Ana Intuneric

Ana Întuneric58

puncta jul pe test. Punctajul integral se acordă pentru rezolvarea corectă a ambelor cerinţe.

Exemplucomp.in comp.out Explicaţii 2120u+7z13u>2s13u1m11s+2z+1u<2m1s2z5u+0u

101

O comparaţie foloseşte semnul <. Prima comparaţie e falsă (203>213). A doua compar aţie e adevărată (2121<2125).

Timp maxim de execuţie/test: 1 secundă

int n,nr;char s[251]; bool v[1001];

int transformare(char *p)//transformare numar eudorian in numar zecimal {

int nr=0,x=0;for(int i=0;i<strlen(p);i++)

if(p[i]>='0' && p[i]<='9') //daca p[i] e cifrax=x*10+(p[i]-'0');

else{

if(p[i]=='m') x*=1000;else if(p[i]=='s') x*=100;

else if(p[i]=='z')x*=10;else x*=1;

nr+=x;x=0;}

return nr;}

int prelucrare(char s[]){

bool semn=1;int e1=0; int e2=0;

if(strchr(s,'<')) semn=0;char *p1=strtok(s,"<>");//prima expresie char *p2=strtok(NULL,"<>");//a doua expresie char *p11=strtok(p1,"+"); while(p11){

e1+=transformare(p11); p11=strtok(NULL,"+");

}char *p22=strtok(p2,"+"); while(p22){

e2+=transformare(p22);

p22=strtok(NULL,"+");}if(semn && e1<=e2) return 0;if(semn==0 && e1>=e2) return 0;return 1;

}

int main(){

f.getline(s,251); int i;//citire n ca sirfor(i=0;i<strlen(s);i++)

n=n*10+(s[i]-'0');for(i=1;i<=n;i++)

{f.getline(s,251);if(strchr(s,'<')) nr++;if(prelucrare(s)) v[i]=1;



Ana Intuneric

else v[i]=0;}g<<nr<<'\n';for(i=1;i<=n;i++) g<<v[i]<<'\n';f.close(); g.close();return 0;

}

Manual Facultate Informatica 08.07.2015

Documents

Transcript of Manual Facultate Informatica 08.07.2015