Despre acest subiect
Subiect și barem
Sursa documentelor: Facultatea de Informatică UVT – Concursul FI. Verifică răspunsurile cu baremul după ce rezolvi subiectul.
Se încarcă profesorii disponibili…
Subiect și barem
Sursa: Facultatea de Informatică UVT – Concursul FI
Subiectul și răspunsurile sunt în același PDF. Afișăm documentul complet, cu toate paginile.
Subiectul și baremul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect și barem · 18 pagini
Subiect și barem · pagina 1
Concursul FMI, Edi¸tia a X-a, Varianta 2 Facultatea de Matematic˘a s, i Informatic˘a Universitatea de Vest din Timis, oara 12 Aprilie, 2025 1. Timp total de lucru: 3 ore 2. Toate subiectele sunt obligatorii! 3. Citit, i cu atent, ie informat, iile legate de tipurile de întreb˘ari, prezentate mai jos. Tipuri de întreb˘ari Pe foaia de concurs vet, i întâlni trei tipuri de întreb˘ari. Pentru a le recunoas, te mai us, or, în partea dreapt˘a vet, i reg˘asi un s, ablon pentru r˘aspunsuri, cu indicat, ii legate de tipul de întrebare. Tipul 1 Pentru întreb˘arile de acest tip vet, i marca pe foaia de concurs MODEL, marcat, i exact un r˘aspuns: 1 2 3 4un singur r˘aspuns corect. Le vet, i recunoas, te dup˘a modelul indicat în partea dreapt˘a a acestui rând. Punctaj pe întrebare: 2p (standard)+1p (bonus pentru r˘aspuns complet). Tipul 2 Pentru întreb˘arile de acest tip vet, i marca pe foaia de concurs MODEL, marcat, i 1-2 r˘aspunsuri: 1 2 3 4 5fie un singur r˘aspuns corect, fie dou˘a r˘aspunsuri corecte. Le vet, i recunoas, te dup˘a modelul indicat în partea dreapt˘a a acestui rând. Punctaj maxim pe întrebare: 2p (standard)+1p (bonus pentru r˘aspuns complet) sau 2x2p (standard, pe variant˘a)+1p (bonus pentru r˘aspuns complet). Tipul 3 Pentru întreb˘arile de acest tip vet, i marca pe foaia de concurs MODEL, marcat, i 1-3 r˘aspunsuri: 1 2 3 4 5fie un singur r˘aspuns corect, fie dou˘a r˘aspunsuri corecte, fie trei r˘aspunsuri corecte. Le vet, i recunoas, te dup˘a modelul indicat în partea dreapt˘a a acestui rând. Punctaj maxim pe întrebare: 2p (standard)+1p (bonus pentru r˘aspuns complet) sau 2x2p/2x3p (stan- dard, pe variant˘a)+1p (bonus pentru r˘aspuns complet). Punctaj Fiecare variant˘a de r˘aspuns corect˘a valoreaz˘a exact 2 puncte. Dac˘a r˘aspunsul oferit identific˘a toate vari- antele corecte de r˘aspuns, la punctajul întreb˘arii se adaug˘a un bonus pentru r˘aspuns complet de 1 punct. Orice r˘aspuns gres, it anuleaz˘a întregul punctaj al întreb˘arii respective, indiferent de num˘arul de r˘aspunsuri corecte. La punctajul obt, inut se adaug˘a 10 puncte, pentru start. Pentru nota 5 sunt necesare 40 de puncte, inclusiv punctele de start, pentru nota 10 sunt necesare cel put, in 80 de puncte, inclusiv punctele de start.
Subiect și barem · pagina 2
2 Terminologie s, i convent, ii Tipuri de date int − num˘ar întreg real − num˘ar real boolean − valoare logic˘a Operat, ii s, i simboluri a DIV b − calculeaz˘a câtul împ˘art, irii întregi (cu rest) a lui a la b a MOD b − calculeaz˘a restul împ˘art, irii întregi a lui a la b a AND b − conjunct, ia logic˘a a OR b − disjunct, ia logic˘a NOT a − negarea logic˘a a = 2 − operat, ia de atribuire a valorii 2 pentru variabila a a == 2 − verificarea egalit˘at, ii variabilei a cu valoarea 2 a̸ = 2 − verificarea inegalit˘at, ii variabilei a cu valoarea 2
Subiect și barem · pagina 3
concursul fmi, 12 aprilie 2025 3
Partea I
Problema 1: Cel mai mare num˘ar posibil
Consider˘am numere naturale cu proprietatea urm˘atoare: începând cu cea de-a treia cifr˘a, fiecare cifr˘a
folosit˘a în scrierea lui n este egal˘a cu suma celor dou˘a cifre care o preced. De exemplu, 31459 are aceast˘a
proprietate: 4 = 3 + 1, 5 = 1 + 4, 9 = 4 + 5. Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4Care este num˘arul maxim de cifre al unui astfel de num˘ar?
1 6 2 7 3 8 " 4 9
Explicat, ii
n trebuie s˘a aib˘a num˘arul maxim posibil de cifre, care se ob¸tine incepând cu cele mai
mici valori posibile pentru primele 2 cifre. Prima cifr˘a nu poate fi 0, deci trebuie s˘a fie 1.
A doua cifr˘a, minim posibil˘a este 0. Cel mai mare num˘ar care începe cu 10 ¸si are propri-
etatea indicat˘a este 10112358. Deci n are 8 cifre.
Problema 2: ¸Siruri speciale
Câte ¸siruri de 5 caractere, nu neap˘arat distincte, din mul¸timea {a, b, c, d, e, f} se pot alc˘atui, care s˘a satisfa-
c˘a condi¸tia urm˘atoare: caracterele a ¸si c apar în ¸sir o singur˘a dat˘a, separate de un singur alt caracter.
Exemple de astfel de ¸siruri sunt: ffabc ¸si dcfae. Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 10 2 64 3 192 4 384 "
Explicat, ii
Vom num˘ara în câte feluri putem completa cele 5 pozi¸tii din ¸sir cu caractere din mul¸ti-
mea {a, b, c, d, e}, ¸si s˘a respect˘am constrângerile problemei.
Fie pa ¸si pc pozi¸tiile unde pot ap˘area a ¸si c în ¸sir. Sunt 3 posibilit˘a¸ti pentru {pa, pc}:
{1, 3}, {2, 4}, {3, 5}, deci 2 · 3 = 6 posibilit˘a¸ti s˘a fix˘am pozi¸tiile pa pentru a ¸si pc pentru
c. Celelalte 3 pozi¸tii r˘amase trebuiesc completate cu caractere din mul¸timea {b, d, e, f}, ¸si
sunt 43 = 64 posibilit˘a¸ti. În concluzie, exist˘a 6 · 64 = 384 astfel de ¸siruri.
Problema 3: Determina¸ti jetonul
Pe o mas˘a sunt puse, cu fa¸ta în jos, trei jetoane pe fa¸ta c˘arora sunt scrise în ordine cresc˘atoare de la stânga
la dreapta, trei numere naturale nenule ¸si distincte, cu suma 13. Horia ridic˘a jetonul din stânga, Maria pe
cel din dreapta, iar Cosmin pe cel din mijloc. Dup˘a ce fiecare cite¸ste num˘arul de pe jetonul ridicat, cei trei
discut˘a între ei ¸si fac urm˘atoarele afirma¸tii:
Horia: Nu am suficiente date pentru a ¸sti celelalte numere.
Maria: Nu pot ¸sti celelalte numere.
Cosmin: Nu pot ¸sti numerele extrase de c˘atre Horia ¸si Maria.Subiect și barem · pagina 4
4 Totu¸si, se poate determina num˘arul de pe jetonul extras de Cosmin. Ciorn˘a, marcat, i exact un r˘aspuns: 1 2 3 4Care este acesta? 1 3 2 4 " 3 5 4 2 Explicat, ii Din datele problemei deducem c˘a sunt 8 posibilit˘a¸ti de a marca jetoanele în ordine cresc˘atoare cu 3 numere distincte a c˘aror sum˘a s˘a fie 13: (1, 2, 10) (2, 3, 8) (3, 4, 6) (1, 3, 9) (2, 4, 7) (1, 4, 8) (2, 5, 6) (1, 5, 7) Horia nu ridic˘a jetonul 3 fiindc˘a altfel ar ¸sti c˘a secven¸ta este (3, 4, 5). Dup˘a afirma¸tia lui Horia, Maria ¸si Cosmin afl˘a c˘a (3, 4, 6) nu este secven¸ta de numere de pe jetoane. Maria nu ridic˘a jetonul 6, 9 sau 10, fiindc˘a altfel ar ¸sti care este secven¸ta de numere. Dup˘a afir- ma¸tia Mariei, ¸stim c˘a secven¸tele posibile r˘amase sunt (1, 4, 8), (1, 5, 7), (2, 3, 8) ¸si (2, 4, 7). Dac˘a Cosmin ar ridica jetonul cu num˘arul 3 sau 5, ar ¸sti care sunt celelate dou˘a numere. Dac˘a ridic˘a jetonul 4, ar fi dou˘a posibilit˘a¸ti r˘amase: (1, 4, 8) ¸si (2, 4, 7). Deci num˘arul de pe jetonul ridicat de Cosmin trebuie s˘a fie 4. Problema 4: Lumea animalelor Pe o insul˘a locuiesc numai arici, s, erpi s, i vulpi. Fiecare animal m˘anânc˘a doar o dat˘a pe zi, astfel încât fiecare arici m˘anânc˘a la micul dejun câte un ¸sarpe; fiecare vulpe m˘anânc˘a la prânz câte un arici; ¸si fiecare ¸sarpe m˘anânc˘a la cin˘a câte o vulpe. Se ¸stie c˘a miercuri seara, dup˘a ce s-a servit cina, pe insul˘a a r˘amas un singur animal. Câte animale vii erau pe insul˘a luni, înainte de micul dejun? Ciorn˘a, marcat, i exact un r˘aspuns: 1 2 3 4 1 10 2 81 3 41 " 4 54
Subiect și barem · pagina 5
concursul fmi, 12 aprilie 2025 5 Explicat, ii Fie A num˘arul de arici, S num˘arul de ¸serpi, ¸si V num˘arul de vulpi. De luni diminea¸ta pân˘a miercuri seara s-au servit 9 mese. ¸Stim c˘a ultima mas˘a a fost cina, când un ¸sarpe a mâncat o vulpe. Deducem c˘a: • S = 1, V = 0, A = 0 miercuri dup˘a cin˘a. S = 1, V = 1, A = 0 miercuri înainte de cin˘a. S = 1, V = 1, A = 1 miercuri înainte de prânz. S = 2, V = 1, A = 1 miercuri înainte de micul dejun. S = 2, V = 3, A = 1 mar¸ti înainte de cin˘a. S = 2, V = 3, A = 4 mar¸ti înainte de prânz. S = 6, V = 3, A = 4 mar¸ti înainte de micul dejun. S = 6, V = 9, A = 4 luni înainte de cin˘a. S = 6, V = 9, A = 13 luni înainte de prânz. S = 19, V = 9, A = 13 luni înainte de micul dejun. Rezult˘a c˘a luni înainte de prânz pe insul˘a erau 19 + 9 + 13 = 41 animale. Partea a II-a Problema 5: Pavaje Pentru pavarea unui trotuar dreptunghiular 2 × n se folosesc dou˘a tipuri de dale: sau Fie an num˘arul de pav˘ari posibile al unui trotuar 2 × n cu dale de acest fel. De pild˘a, a2 = 5 pentru c˘a sunt posibile 5 pav˘ari ale unui trotuar 2 × 2: Care din afirma¸tiile urm˘atoare sunt adev˘arate? Marca¸ti-le pe toate Ciorn˘a, marcat, i 1-2 r˘aspunsuri: 1 2 3 4 5care sunt corecte. 1 a0 = a1 = 1 ¸si an = an−1 + 4 an−2 dac˘a n ≥ 2. 2 a0 = a1 = 1, a2 = 3 ¸si an = an−1 + 4 an−2 + an−3 dac˘a n ≥ 3. 3 a0 = a1 = 1, a2 = 5 ¸si an = an−1 + 4 an−2 + 2 an−3 dac˘a n ≥ 3." 4 a4 = 31. 5 Nici o afirma¸tie.
Subiect și barem · pagina 6
6 Explicat, ii Observ˘am c˘a a0 = a1 = 1 ¸si a2 = 5. Pentru n > 2 gândim recursiv cum putem pava trotu- arul pornind din col¸tul stânga-sus: 1. Pav˘am col¸tul stânga-sus cu . În acest caz putem continua pavarea col¸tului stânga- jos în doar dou˘a feluri: (a) ¸si r˘amân an−1 posibilit˘a¸ti de pavat restul 2 × (n − 1) de trotuar. (b) ¸si r˘amân an−2 posibilit˘a¸ti de pavat restul 2 × (n − 2) de trotuar. 2. Pav˘am col¸tul stânga sus cu . În acest caz putem continua pavarea p˘atr˘a¸telului din dreapta col¸tului stânga-sus în doar dou˘a feluri: (a) ¸si r˘amân an−2 posibilit˘a¸ti de pavat restul 2 × (n − 2) de trotuar. (b) ¸si r˘amân an−3 posibilit˘a¸ti de pavat restul 2 × (n − 3) de trotuar. 3. Pav˘am col¸tul stânga-sus cu . În acest caz avem o singur˘a posibilitate de pavat col¸tul stânga-jos: ¸si r˘amân an−2 posibilit˘a¸ti de pavat restul 2 × (n − 2) de trotuar. 4. Pav˘am col¸tul-stânga sus cu . În cazul acesta putem continua pavarea p˘atr˘a¸telului din dreapta col¸tului stânga-jos în doar 2 feluri: (a) ¸si r˘amân an−2 posibilit˘a¸ti de pavat restul 2 × (n − 2) de trotuar. (b) ¸si r˘amân an−3 posibilit˘a¸ti de pavat restul 2 × (n − 3) de trotuar. În concluzie: a0 = a1 = 1, a2 = 5 ¸si an = an−1 + 4 an−2 + 2 an−3 dac˘a n ≥ 3. Deducem c˘a singurul r˘aspuns corect este 3 . Problema 6: ¸Sir inversat Presupunem c˘a a[1..n] este un tablou care re¸tine caracterele distincte ale unui alfabet. Orice ¸sir c1c2 . . . cm de caractere din a poate fi reprezentat ca un tablou s[1..m], astfel încât (1) a[s[i]] = ci pentru to¸ti 1 ≤ i ≤ m ¸si (2) s[m + 1] = 0. De exemplu, dac˘a a[1..26] re¸tine caracterele latine de la a la z, atunci ¸sirul abac este reprezentat de tabloul s[1..5] = [1, 2, 1, 3, 0] iar ¸sirul vid este reprezentat de tabloul s[1..1] = [0]. Se pune problema modific˘arii tabloului s[1..m + 1] pentru ¸sirul c1c2 . . . cm, astfel încât s˘a reprezinte ¸sirul inversat cm . . . c2c1. De exemplu, modificarea tabloului s[1..5] = [1, 2, 1, 3, 0] pentru ¸sirul abac trebuie s˘a produc˘a s[1..5] = [3, 1, 2, 1, 0] pentru ¸sirul caba. Care dintre algoritmii de mai jos produce modificarea dorit˘a? Marca¸ti toate r˘aspunsurile corecte. Ciorn˘a, marcat, i 1-2 r˘aspunsuri: 1 2 3 4 51 Nici unul din cei patru algoritmi.
Subiect și barem · pagina 7
concursul fmi, 12 aprilie 2025 7 2 procedura inverseaza(int m) int i, tmp pentru i = 1 to m execut˘a tmp = s[i] s[i] = s[m + 1 − i] s[m + 1 − i] = tmp 3 procedura inverseaza(int m) int i, tmp pentru i = 1 to m execut˘a tmp = s[i] s[m + 1 − i] = s[i] s[i] = tmp aa 4 procedura inverseaza(int m) " int i, tmp pentru i = 1 to (m DIV 2) execut˘a tmp = s[i] s[i] = s[m + 1 − i] s[m + 1 − i] = tmp 5 procedura inverseaza(int m)" int i pentru i = 1 to (m DIV 2) execut˘a s[m + 1] = s[i] s[i] = s[m + 1 − i] s[m + 1 − i] = s[m + 1] s[m + 1] = 0 Explicat, ii R˘aspunsurile corecte sunt 4 ¸si 5 . Problema 7: Robotul energetic Un robot colector de energie se poate deplasa într-o gril˘a 5 × 5 pornind de la o celul˘a de pe prima coloan˘a a grilei, trecând într-una din cele maxim trei celule învecinate de pe coloana urm˘atoare (linia curent˘a, linia anterioar˘a, linia urm˘atoare) ¸si oprindu-se într-o celul˘a de pe ultima coloan˘a. La trecerea printr-o celul˘a, acumulatorul robotului se încarc˘a cu o anumit˘a cantitate de energie. Ne intereseaz˘a s˘a identific˘am traseul/traseele care pornesc de pe prima coloan˘a a grilei ¸si ajung pe ultima coloan˘a astfel încåt robo- tul s˘a colecteze cât mai mult˘a energie. Consider˘am c˘a valorile de energie corespunz˘atoare celulelor sunt specificate în matricea G din figura (a), iar figura (b) indic˘a un drum de-a lungul c˘aruia robotul colecteaz˘a cantitatea 17 de energie: G = 1 3 2 2 5 2 5 4 1 4 3 4 5 3 3 4 1 3 4 2 5 2 1 5 1 (a) 3 4 4 2 4 1 3 2 5 2 5 1 5 3 3 4 1 3 2 4 5 2 1 5 1 (b) Care dintre punctele de start ¸si de stop ale robotului apar¸tin unor trasee care permit colectarea cantit˘a¸tii maxime de energie? Ciorn˘a, marcat, i 1-2 r˘aspunsuri: 1 2 3 4 5 1 Start: G[2, 1], Stop: G[4, 5]. 2 Start: G[3, 1], Stop: G[1, 5]. 3 Start: G[3, 1], Stop: G[2, 5]. " 4 Start: G[4, 1], Stop: G[2, 5]. " 5 Start: G[5, 1], Stop: G[4, 5].
Subiect și barem · pagina 8
8
Explicat, ii
Valoarea maxim˘a a energiei colectate de c˘atre robot când se afl˘a în celula de pe linia i,
coloana j se poate calcula folosind rela¸tia de recuren¸t˘a:
E[i, j] =
G[i, j] dac˘a j = 1,
max{E[i, j − 1], E[i + 1, j − 1]} + G[i, j] dac˘a i = 1, j > 1,
max{E[i, j − 1], E[i − 1, j − 1]} + G[i, j] dac˘a i = 5, j > 1,
max{E[i − 1, j − 1], E[i, j − 1], E[i + 1, j − 1]} + G[i, j] în celelalte cazuri.
Folosind aceast˘a rela¸tie de recuren¸t˘a se completeaz˘a matricea E:
E =
1 5 10 14 19
2 8 12 14 20
3 8 13 16 20
4 6 11 17 19
5 7 8 16 18
Valorile de pe ultima coloan˘a indic˘a energia colectat˘a la finalul traseului. Se observ˘a c˘a
sunt dou˘a pozi¸tii finale care conduc la valoarea maxim˘a a energiei (E[2, 5] = 20, E[3, 5] =
20). Prin urmare pot fi r˘aspunsuri corecte doar 3 ¸si 4 . Pentru a verifica c˘a exist˘a trasee
corespunz˘atoare celor dou˘a puncte extreme pornim de la pozi¸tiile de stop, înapoi c˘atre
pozi¸tiile de start folosind deciziile luate la construirea matricii E. Pornind de la pozi¸tia
(2, 5) unul din traseele care rezult˘a este: (2, 5) → (3, 4) → (3, 3) → (2, 2) → (3, 1). Se ob-
serv˘a c˘a din pozi¸tia (3, 3) se poate trece în pozi¸tia (3, 2) iar de acolo se ajunge în pozi¸tia
(4, 1). Deci atåt 3 cât ¸si 4 sunt r˘aspunsuri corecte.
Problema 8: Proprietate ¸sir de caractere
Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
Se consider˘a funct, ia ord() care întoarce codul ASCII al unui caracter.
funct, ia proprietate_sir_caractere(caracter s[1..n]): boolean
int i = 2, j = n − 1
cât timp i < n AND j > 0 execut˘a
dac˘a |ord(s[i]) − ord(s[i − 1])|̸ = |ord(s[j]) − ord(s[j + 1])| atunci
întoarce f alse
i = i + 1, j = j − 1
întoarce true
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate despre funct, ia proprietate_sir_caractere()?
1 Funct, ia întoarce true doar dac˘a s este palindrom, adic˘a s[i] == s[n + 1 − i] pentru to¸ti 1 ≤ i ≤ n.
2 Dac˘a se înlocuies, te condit, ia ciclului cât timp cu i ≤ j comportamentul algoritmului este acelas, i, dar în
unele cazuri se execut˘a mai put, ine comparat, ii. "
3 Dac˘a se înlocuies, te condit, ia ciclului cât timp cu i ≤ j comportamentul funct, iei este diferit.
4 Din lista [’Miss’, ’Arora’, ’teaches’, ’us’, ’malayalam’, ’bdwy’], trei cuvinte îndeplinesc proprietatea verifi-
cat˘a de funct, ia proprietate_sir_caractere(). "Subiect și barem · pagina 9
concursul fmi, 12 aprilie 2025 9
5 Din lista [’Miss’, ’Arora’, ’teaches’, ’us’, ’malayalam’, ’bdwy’], patru cuvinte îndeplinesc proprietatea
verificat˘a de funct, ia proprietate_sir_caractere().
Explicat, ii
Variantele corecte sunt 2 s, i 4 pentru c˘a sub-algoritmul verific˘a dac˘a s, irul s are propri-
etatea |ord(si) − ord(si−1)| = |ord(sn−i) − ord(sn−i+1)|.
Problema 9: Secven¸t˘a ADN
O secven¸t˘a ADN este un ¸sir de elemente din alfabetul {A, C, G, T}, iar un k-mer este o subsecven¸t˘a de k
elemente consecutive. Consider˘am c˘a o secven¸t˘a ADN este AT-dominant˘a dac˘a fiecare 4-mer din secven¸t˘a
con¸tine exact o pereche de elemente consecutive de tip AT.
De exemplu, ATCATAATGATTATGA, CATGATTATAATGATG ¸si AGATTATGATAATCAT sunt secven¸te
AT-dominante, iar ATGAATTACCATATGG nu este secven¸t˘a AT-dominant˘a. Câte secven¸te AT-dominante
de lungime 64 exist˘a? Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
1 432.
2 264.
3 15 · 420 + 16 · 420 + 15 · 420. "
4 420 + 421 + 422.
5 23 · 241. "Subiect și barem · pagina 10
10
Explicat, ii
O secven¸t˘a AT-dominant˘a poate fi, în partea de început de unul dintre urm˘atoarele
tipuri:
1. Tip 1: AT_AT_AT_ ..._AT_ _
2. Tip 2: _AT_AT_AT_ ..._AT_
3. Tip 3: _ _AT_AT_AT_ ..._AT
Simbolul _ corespunde oric˘arui element din {A,C,G,T}. In cazul unei secven¸te de lungime
n = 64 num˘arul de variante de fiecare tip se poate calcula dup˘a cum urmeaz˘a:
1. Secven¸ta este de forma AT _AT_AT. . . _AT
| {z }
20×3 simboluri
xy cu xy̸ = AT, iar fiecare din cele 20 sim-
boluri _ poate fi înlocuit independent cu orice element din {A, C, G, T}, iar pentru xy
sunt 16 − 1 = 15 variante. Prin urmare sunt 15 · 420 secven¸te de acest fel.
2. Secven¸ta este de forma _ AT_AT. . . _AT_
| {z }
21×3 simboluri
, cu 22 simboluri _ ce pot fi înlocuite indepen-
dent cu orice element din {A, C, G, T}. Sunt 422 secven¸te de acest fel.
3. Secven¸ta este de forma xy AT_AT. . . _AT_
| {z }
20×3 simboluri
AT unde xy̸ = AT, iar fiecare din cele 20
simboluri _ poate fi înlocuit independent cu orice element din {A, C, G, T}, iar pentru
xy sunt 16 − 1 = 15 variante. Prin urmare sunt 15 · 420 secven¸te de acest fel.
În total sunt 15 · 420 + 422 + 15 · 420 = 46 · 420 secven¸te AT-dominante. R˘aspunsurile corecte
sunt 3 ¸si 5 .
Problema 10: Scurt˘aturi
G este un graf orientat cu n noduri numerotate de la 1 la n. Alex trebuie s˘a g˘aseasc˘a mul¸timea S a no-
durilor la care exist˘a un drum la nodul n ¸si, pentru fiecare nod i ∈ S, câte un drum cât mai scurt de la
nodul n la nodul i. Drumurile de la un nod la el însus, i sunt considerate de lungime 0. Alex observ˘a c˘a
poate g˘asi un arbore T în care a mul¸timea de noduri este S, nodul r˘ad˘acin˘a este n, ¸si, pentru to¸ti i ∈ S,
drumul elementar de la r˘ad˘acina n la nodul i coincide cu un drum de lungime minim˘a de la n la i în G.
De asemenea, el observ˘a c˘a este util s˘a ia în considerare nodurile intermediare prin care are voie s˘a treac˘a
un drum în G: dac˘a pentru orice 1 ≤ i, j ≤ n, pk
ij este drum elementar de lungime minim˘a dk
ij de la i la j
constrâns s˘a treac˘a prin noduri intermediare din mul¸timea {1, . . . , k}, atunci (1) dk+1
ij = min(dk
ik + dk
kj, dk
ij), ¸si
(2) putem presupune c˘a dac˘a dk+1
ij < dk
ij atunci pk+1
ij este rezultatul concaten˘arii drumului pk
ik cu pk
kj; altfel,
pk+1
ij coincide cu pk
ij.
Ca s˘a-¸si u¸sureze acest mod de gândire, Alex î¸si define¸ste algoritmii de mai jos, în care variabilele P, D, T1, T2
sunt globale de tip tablou de întregi de dimensiune n × n:Subiect și barem · pagina 11
concursul fmi, 12 aprilie 2025 11
procedura initializeaz ˘a()
int i, j
pentru i = 1 to n execut˘a
pentru j = 1 to n execut˘a
dac˘a i == j atunci
P[i][j] = 0, D[i][j] = 0
altfel
dac˘a (i, j) este arc în G atunci
P[i][j] = i, D[i][j] = 1
altfel
P[i][j] = 0, D[i][j] = n
procedura copiaz ˘a()
int i, j
pentru i = 1 to n execut˘a
pentru j = 1 to n execut˘a
D[i][j] = T1[i][j]
P[i][j] = T2[i][j]
procedura caut ˘a(int m)
int i, j, k
initializeaz ˘a()
pentru k = 1 to m execut˘a
pentru i = 1 to m execut˘a
pentru j = 1 to m execut˘a
T1[i][j] = min(D[i][k] + D[k][j], D[i][j])
dac˘a T1[i][j] < D[i][j] atunci
T2[i][j] = P[k][j]
altfel
T2[i][j] = P[i][j]
copiaz ˘a()
procedura drum(int i, int j)
dac˘a j̸ = i AND P[i][j] == 0 atunci
afis, eaz˘a "Nu exist˘a drum de la i la j"
altfel
int k = j
cât timp k > 0 execut˘a
afis, eaz˘a k
k = P[i][k]
Care din afirma¸tiile urm˘atoare sunt adev˘arate imediat dup˘a execu¸tia Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5algoritmului caut˘a(n − 1)? Marca¸ti toate variantele corecte.
1 Pentru orice noduri i, j ∈ S, drum(i, j) afi¸seaz˘a un drum de lungime minim˘a de la i la j.
2 Dac˘a i ∈ S atunci D[n][i] este lungimea minim˘a a unui drum de la n la i în G. "
3 S coincide cu mul¸timea nodurilor {i | 1 ≤ i ≤ n ¸si P[n][i]̸ = 0}.
4 T poate fi arborele cu r˘ad˘acina n în care p˘arintele oric˘arui nod i ∈ S − {n} este P[i][n].
5 Dac˘a P[n][i]̸ = 0 atunci i ∈ S."Subiect și barem · pagina 12
12
Explicat, ii
Acesta este algoritmul lui Roy-Floyd adaptat la cazul special când nodul surs˘a trebuie s˘a
fie n, ¸si fiecare arc are ponderea 1. Dup˘a rularea algoritmului caut˘a(n − 1), tabloul T ne
permite identificarea arborelui T c˘autat de Alex: S = {n} ∪ {i | P[n][i]̸ = 0} ¸si P[n][i]
este p˘arintele fiec˘arui nod i ∈ S diferit de nodul r˘ad˘acin˘a n. Mai mult, pentru to¸ti i ∈ S,
D[n][i] este lungimea minim˘a unui drum de la n la i în G.
1 este fals˘a pentru cazul în care i, j < n iar drumul cel mai scurt de la nodul i la j trece
prin nodul intermediar n.
2 este adev˘arat˘a: dup˘a execu¸tia lui caut˘a(n − 1), pentru orice nod i ∈ S avem c˘a: D[n][i]
este lungimea cea mai mic˘a a unui drum de la n la i, iar drum(n, i) afi¸seaz˘a nodurile
unui drum de lungime minim˘a de la n la i în G.
3 este fals˘a pentru c˘a n ∈ S dar P[n][n] = 0. În schimb, este adev˘arat˘a afirma¸tia
"S = {n} ∪ {i | 1 ≤ i ≤ n ¸si P[n][i]̸ = 0}".
4 este fals˘a iar 5 este adev˘arat˘a.
Problema 11: Afis, are modular˘a
Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
Fie sub-algoritmul foo() care primes, te ca parametri un s, ir de numere
întregi sir[1..n], lungimea s, irului (n) s, i dou˘a numere k s, i h (k, h ∈ N∗):
procedura foo(int sir[1..n], int n, int k, int h)
dac˘a n̸ = 0 atunci
dac˘a NOT (sir[n] MOD k == 0 AND sir[n] MOD h == 0) atunci
afis, eaz˘a sir[n]
foo(sir, n − 1, k, h)
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate?
1 Apelul foo([24, 25, 49, 28, 56, 14], 6, 4, 7) va afis, a 14 49 25 24 "
2 Apelul foo([24, 25, 49, 28, 56, 14], 6, 4, 7) va afis, a 24 25 49 14
3 Condit, ia din instruct, iunea dac˘a este echivalent˘a cu sir[n] MOD k̸ = 0 OR sir[n] MOD h̸ = 0 "
4 Condit, ia din instruct, iunea dac˘a este echivalent˘a cu sir[n] MOD k̸ = 0 AND sir[n] MOD h̸ = 0
5 Condit, ia din instruct, iunea dac˘a este echivalent˘a cu NOT sir[n] MOD cmmdc(k, h) == 0Subiect și barem · pagina 13
concursul fmi, 12 aprilie 2025 13 Explicat, ii Acest sub-algoritm afis, eaz˘a numerele din s, ir care nu sunt divizibile în aceleas, i timp cu k s, i h în ordine invers˘a a aparit, iei lor în s, ir. Deci 1 este corect˘a s, i 2 este incorect˘a. Varianta 3 este corect˘a pentru c˘a NOT (A AND B) = ( NOT A) OR ( NOT B). Varianta 4 este incorect˘a pentru c˘a NOT (A AND B)̸ = ( NOT A) AND ( NOT B). Se ¸stie c˘a k | n ¸si h | n dac˘a ¸si numai dac˘a cmmmc(k, h) | n. Prin urmare, condi¸tia din intruc¸tiunea dac˘a este echivalent˘a cu NOT sir[n] MOD cmmmc(k, h) = 0. Îns˘a aceasta nu este echivalent˘a cu NOT sir[n] MOD cmmdc(k, h) = 0, deci 5 incorect˘a. Deci singurele variante corecte sunt 1 s, i 3 .
Subiect și barem · pagina 14
14 Partea a III-a Problema 12: Afi¸sare-era¸sifA Se d˘a un tablou de numere a. S˘a se identifice algoritmul/algoritmii care populeaz˘a o matrice Bn×m cu elemente astfel: pe durata travers˘arii matricii B, linie dup˘a linie, de la stânga la dreapta, se completeaz˘a B cu elementele lui a, apoi cu elementele lui a în ordine invers˘a, dup˘a care procesul se repet˘a. De exemplu, dac˘a a = [1, 2, 3] ¸si n = 3, m = 4, va rezulta matricea B = 1 2 3 3 2 1 1 2 3 3 2 1 procedura completare1(int a[1..k], int n, int m) int B[1..n][1..m] int i, j, h = 1, d = 1 pentru i = 1 to n execut˘a pentru j = 1 to m execut˘a B[i][j] = a[h] h = h + d dac˘a h == k OR h == 1 atunci d = −d procedura completare3(int a[1..k], int n, int m) int B[1..n][1..m] int i, j, h, d = −1 pentru i = 1 to n execut˘a pentru j = 1 to m execut˘a dac˘a ((i − 1) ∗ m + j − 1) MOD k == 0 atunci d = −d dac˘a d == 1 atunci h = 1 altfel h = k B[i][j] = a[h] h = h + d procedura completare2(int a[1..k], int n, int m) int B[1..n][1..m] int i, j, h = 1, d = −1 pentru i = 1 to n execut˘a pentru j = 1 to m execut˘a dac˘a h == k OR h == 1 atunci d = −d B[i][j] = a[h] h = h + d procedura completare4(int a[1..k], int n, int m) int B[1..n][1..m] int i, j, h = 0, d = −1 pentru i = 1 to n execut˘a pentru j = 1 to m execut˘a dac˘a h == 0 atunci h = 1 d = −d altfel dac˘a h == k + 1 atunci h = k d = −d B[i][j] = a[h] h = h + d Ciorn˘a, marcat, i 1-3 r˘aspunsuri: 1 2 3 4 5Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? 1 Toate variantele conduc la aceeas, i matrice B 2 Variantele completare1() s, i completare2() completeaz˘a matricea B cu aceleas, i elemente " 3 Variantele completare1() s, i completare3() respect˘a regula enunt, at˘a 4 Variantele completare2() s, i completare4() respect˘a regula enunt, at˘a
Subiect și barem · pagina 15
concursul fmi, 12 aprilie 2025 15 5 Variantele completare3() s, i completare4() respect˘a regula enunt, at˘a " Explicat, ii Variantele corecte sunt 2 s, i 5 . Problema 13: Interschimb˘ari repetate Se consider˘a un tablou a de n > 1 numere întregi indexate de la 1 la n, ¸si sub-algoritmul Foo(a, n) care modific˘a tabloul a ¸si returneaz˘a un num˘ar întreg. procedura Foo(int a[1..n], int n): int int tmp, i = 1, j = n + 1 boolean ok = true cât timp ok execut˘a i = i + 1 cât timp a[i] < a[1] AND (i̸ = n) execut˘a i = i + 1 j = j − 1 cât timp a[1] < a[j] AND (j̸ = 1) execut˘a j = j − 1 dac˘a i ≥ j atunci ok = f alse altfel tmp = a[i]; a[i] = a[j]; a[j] = tmp tmp = a[1]; a[1] = a[j]; a[j] = tmp întoarce j Deasemenea, se consider˘a c˘a b este un tablou de aceea¸si dimensiune cu a, care con¸tine elementele lui a în ordine cresc˘atoare, ¸si c˘a valoarea returnat˘a de Foo(a, n) este j. Precizat, i care din afirma¸tiile urm˘atoare sunt adev˘arate dup˘a execu¸tia Ciorn˘a, marcat, i 1-3 r˘aspunsuri: 1 2 3 4 5sub-algoritmului Foo(a, n). Marca¸ti toate variantele corecte. 1 a[1] = b[j] 2 a[j] = b[j] " 3 a[1] = b[1]. 4 a[i] ≤ a[j] pentru to¸ti 1 ≤ i < j" 5 a[i] ≥ a[j] pentru to¸ti j < i ≤ n" Explicat, ii Acest sub-algoritm st˘a la baza algoritmului de sortare quicksort, ¸si rearanjeaz˘a elemen- tele tabloului a astfel încât dup˘a execu¸tia lui: (1) a[j] con¸tine valoarea ini¸tial˘a a lui a[1], ¸si (2) a[i] ≤ a[j] pentru to¸ti 1 ≤ i < j ¸si a[j] ≤ a[i] pentru to¸ti j < i ≤ n. Din proprietatea (2) deducem c˘a variantele corecte sunt 2 , 3 ¸si 4 .
Subiect și barem · pagina 16
16 Problema 14: La fel sau nu? Se presupune c˘a T[1..n] este un tablou global de numere întregi de dimensiune 25, ¸si se consider˘a func¸tiile definite în felul urm˘ator: funct, ia Foo1(int n): int dac˘a n ≤ 2 atunci întoarce 1 altfel întoarce 2 ∗ Foo1(n − 1) + Foo1(n − 2) funct, ia Foo2(int n): int int i T[1] = 1, T[2] = 1 pentru i = 3 to 25 execut˘a T[i] = 0 întoarce Bar(n) funct, ia Bar(int n): int dac˘a T[n] > 0 atunci întoarce T[n] altfel int i pentru i = n − 2 to n − 1 execut˘a dac˘a T[i] == 0 atunci T[i] = Bar(i) T[n] = 2 ∗ T[n − 1] + T[n − 2] întoarce T[n] Care din afirma¸tiile urm˘atoare sunt adev˘arate pentru n = 7? Marca¸ti toate variantele corecte. Ciorn˘a, marcat, i 1-3 r˘aspunsuri: 1 2 3 4 5 1 Calculul lui Foo1(n) apeleaz˘a func¸tia Foo1 de 99 ori. 2 Calculul lui Foo1(n) apeleaz˘a func¸tia Foo1 de 25 ori." 3 Calculul lui Foo2(n) apeleaz˘a func¸tia Bar de 7 ori. 4 Calculul lui Foo2(n) apeleaz˘a func¸tia Bar de 5 ori." 5 Foo1(n) ¸si Foo2(n) returneaz˘a acela¸si rezultat. " Explicat, ii Ambele func¸tii, Foo1(n) ¸si Foo2(n), calculeaz˘a acela¸si num˘ar: valoarea lui an care are defini¸tia recursiv˘a a1 = a2 = 1 ¸si an = 2 an−1 + an−2 dac˘a n ≥ 3. Se observ˘a c˘a an > 0 pentru to¸ti n ≥ 1. Dac˘a not˘am cu xn (resp. yn) num˘arul de apeluri ale lui Foo1 (sep. Bar) pe durata calcu- lui lui Foo1(n) (resp. Foo2(n)), atunci • x1 = x2 = 1, xn = 1 + xn−1 + xn−2 dac˘a n > 2. Pentru n = 7 ob¸tinem x7 = 25. • Dac˘a n > 2 atunci Foo2(n) apeleaz˘a Bar(n). Acest apel necesit˘a calculul apelurilor re- cursive Bar(i) pentru 3 ≤ i ≤ n. Fiecare apel recursiv Bar(i) se calculeaz˘a o singur˘a dat˘a pentru c˘a valoarea lui se re¸tine în T[i]. Deci yn = n − 2 pentru c˘a Bar se apleaz˘a de n − 2 ori: Bar(i) pentru 3 ≤ i ≤ n. În particular, y7 = 5. Prin urmare, r˘aspunsurile corecte sunt 2 , 4 ¸si 5 .
Subiect și barem · pagina 17
concursul fmi, 12 aprilie 2025 17 Problema 15: Mozaic Un hol are lungimea L ¸si l˘a¸timea w (L > w). Ambele sunt numere naturale, iar w este o putere a lui 2. Se dore¸ste placarea holului cu piese de mozaic de form˘a p˘atrat˘a. Piesele de mozaic au laturi de diferite dimensiuni: w, w/2, w/4, . . ., 2, 1. Exist˘a suficiente piese pentru oricare dimensiune aleas˘a, dar se dore¸ste utilizarea unui num˘ar total de piese cât mai mic. În scopul determin˘arii num˘arului minim de piese, au fost scrise urm˘atoarele func¸tii: funct, ia mozaic1(int w, int L): int int nr = 0, d = 1 cât timp L > 0 execut˘a nr = nr + d ∗ (L DIV w) L = L MOD w w = w DIV 2 d = 2 ∗ d întoarce nr funct, ia mozaic2(int w, int L): int int nr = 0, d = 1 cât timp L > 0 execut˘a nr = nr + d ∗ (L MOD w) L = L DIV w w = w DIV 2 d = 2 ∗ d întoarce nr funct, ia mozaic3(int w, int L): int int nr = L DIV w int r = L MOD w int d = w cât timp r > 0 execut˘a nr = nr + d ∗ (r MOD 2) d = d DIV 2 r = r DIV 2 întoarce nr funct, ia mozaic4(int d, int w, int L): int dac˘a d == 1 atunci întoarce w ∗ L întoarce (w DIV d) ∗ (L DIV d) + mozaic4(d DIV 2, w, L MOD d) Care dintre apelurile de func¸tii indicate mai jos determin˘a num˘arul Ciorn˘a, marcat, i 1-3 r˘aspunsuri: 1 2 3 4 5minim de piese necesare pentru placarea holului? Marca¸ti toate r˘aspunsurile corecte. 1 "mozaic1(w, L) 2 mozaic2(w, L) 3 "mozaic3(w, L) 4 "mozaic4(w, w, L) 5 niciunul dintre apelurile men¸tionate anterior.
Subiect și barem · pagina 18
18
Explicat, ii
Num˘arul de piese folosite este cu atât mai mic cu cåt se folosesc cåt mai multe piese de
dimensiune mare. Se parcurg piesele în ordinea descresc˘atoare a laturii ¸si se determin˘a
cåtul împ˘ar¸tirii întregi a lungimii zonei de placat la dimensiunea piesei curente. Num˘arul
de piese de dimensiunea curent˘a se ob¸tine înmul¸tind acest cât cu raportul dintre l˘a¸timea
holului ¸si dimensiunea piesei. Restul împ˘ar¸tirii indic˘a lungimea por¸tiunii r˘amase de pla-
cat, iar pentru aceasta se continu˘a cu analiza urm˘atoarei dimensiuni de plac˘a (jum˘atate
din cea curent˘a). Aceast˘a idee este implementat˘a în algoritmul mozaic1.
De¸si are aceea¸si structur˘a, algoritmul mozaic2 este eronat întrucât, la actualizarea
num˘arului de piese folosite, se utilizeaz˘a restul împ˘ar¸tirii lui L la w în loc s˘a se utilizeze
câtul împ˘ar¸tirii lui L la w.
Algoritmul mozaic3 se bazeaz˘a pe observa¸tia c˘a pentru a ob¸tine un num˘ar cât mai mic
de piese, cu excep¸tia piesei de dimensiunea cea mai mare, celelalte piese vor putea fi
folosite pentru a acoperi o lungime de hol cel mult egal˘a cu dimensiunea lor. Aceasta
înseamn˘a c˘a dac˘a w = 2k atunci restul primei împ˘ar¸tiri a lui L la w poate fi scris în baza
2 ca r = bk−1 · 2k−1 + bk−2 · 2k−2 + . . . b1 · 2 + b0, iar bi ∈ {0, 1} indic˘a dac˘a piesa de latur˘a
2i este utilizat˘a sau nu. Prin urmare este suficient s˘a se determine cifrele reprezent˘arii în
baza 2 a restului împ˘ar¸tirii lui L la w. Num˘arul de piese de un anumit tip utilizate este
gestionat prin variabila d, care con¸tine ini¸tial num˘arul necesar de piese de latura 1 (adic˘a
w) iar la fiecare etap˘a se înjum˘at˘a¸te¸ste (întrucât dimensiunea piesei se dubleaz˘a).
Pentru algoritmul mozaic4 ra¸tionamentul este descris în continuare. Fie N(d, w, L)
num˘arul minim de piese de dimensiune cel mult d pentru placarea unui hol w × L.
Gândim recursiv, dup˘a d. Dac˘a d = 1 atunci N(1, w, L) = w ∗ L. Dac˘a d > 1, plac˘am cât
se poate cu piese de dimensiune d, ¸si restul cu piese de dimensiune cel mult d/2. Putem
placa por¸tiunea w × (L DIV d) cu (w/d) ∗ (L DIV d) piese de dimensiune d, ¸si por¸tiunea
r˘amas˘a w × (L MOD d) cu N(d/2, w, L MOD d) piese. Deci
N(d, w, L) =
(
w ∗ L dac˘a d = 1,
(w/d) ∗ (L DIV d) + N(d/2, w, L MOD d) în caz contrar.
Apelul mozaic4(d, w, L) calculeaz˘a N(d, w, L), num˘arul minim de piese de dimensiune
cel mult d necesare pentru placarea unui hol de dimensiune w × L.
Prin urmare variantele corecte de algoritm sunt mozaic1, mozaic3 ¸si mozaic4.Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Concurs de pregătire · 2025Matematică · Clasa a XI-aDeschide fișa Concurs de pregătire · 2025Matematică · Clasa a XII-aDeschide fișa Examen de admitere · 2025Informatică · Subiect și barem în același documentDeschide fișa Examen de admitere · 2025Matematică și Informatică · Broșura oficială – varianta 1Deschide fișa Examen de admitere · 2025Matematică · Subiect și barem în același documentDeschide fișa Examen de admitere · 2025Matematică și Informatică · Broșura oficială – varianta 1 cu baremDeschide fișa
Răspunsuri directe
Ce trebuie să știi despre acest subiect?
Ce document de admitere este acesta?
Pagina prezintă concurs de pregătire din 2025 pentru Informatică, la Facultatea de Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.
Există și barem sau răspunsuri pentru acest subiect?
Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.
Cum folosesc acest subiect în pregătirea pentru admitere?
Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.
