Page 31 - MATINF Nr.2

Vectori de frecvent , e 31

Intrare

2382364

Ies , ire

2 3 4 6 8
Solut , ie

I. Max = 9 s , i astfel M = {0, 1, . . . , 9}.

II. Scoatem cifrele din k ˆın variabila i s , i de fiecare dat˘a frecvent , a lui i cres , te cu 1 (f[i] =
f[i] + 1).
III. Afis , ˘am cifrele lui k astfel: pentru orice i din mult , imea M, afis , ˘am i dac˘a f[i] > 0.

Pentru exemplul considerat: Max = 9, f x [2] = 2, f x [3] = 2, f x [4] = 1, f x [6] = 1, f x [8] = 1,
iar celelalte componente ale lui f x sunt 0. Astfel, se afis , eaz˘a 2 3 4 6 8.

Probleme propuse spre rezolvare cu vectori de frecvent˘a
,

15
1. Pentru un num˘ar natural n din intervalul [1, 10 ] se cere s˘a se afis , eze cel mai mare s , i cel
mai mic num˘ar, care se pot forma cu cifrele sale.

Exemplu
Intrare: 200217

Ies , ite: 722100 100227

2. Un s , ir de numere este o progresie aritmetic˘a de rat , ie r dac˘a oricare termen al s˘au, cu
except , ia primului, se obt , ine din cel care ˆıl precede, prin adunarea la acesta a num˘arului r.
Exemplu: s , irul 12, 14, 16, 18, 20 este o progresie de rat , ie 2. Fis , ierul bac.in cont , ine un s , ir de
cel mult 106 numere naturale din intervalul [0,103], separate prin cˆate un spat , iu. Se cere s˘a se
verifice dac˘a exist˘a un num˘ar natural r, astfel ˆıncˆat toate numerele distincte din s , ir s˘a poat˘a fi
rearanjate pentru a forma o progresie aritmetic˘a de rat , ie r. Se afis , eaz˘a pe ecran num˘arul r, sau
mesajul NU, dac˘a nu exist˘a un astfel de num˘ar. Proiectat , i un algoritm eficient din punctul de
vedere al timpului de executare.

Exemplu

Intrare: 180 30 80 280 130 330 230 30 30 330 80

Ies , ire: 50

Bacalaureat, sesiunea august-septembrie, 2017

3. Fis , ierul bac.txt cont , ine un s , ir de cel mult un milion de numere naturale din intervalul
[0,102], separate prin cˆate un spat , iu. Se cere s˘a se determine toate perechile distincte formate
din termeni ai s , irului aflat ˆın fis , ier, x s , i y (y − x ≥ 2), astfel ˆıncˆat s˘a nu existe niciun termen al
s , irului care s˘a apart , in˘a intervalului (x, y). Numerele din fiecare pereche sunt afis , ate pe cˆate
o linie a ecranului, ˆın ordine strict cresc˘atoare, separate printr-un spat , iu, iar dac˘a nu exist˘a