Pregătire cu un profesor

UNIVERSITATEA DE VEST TIMIS, OARA
FACULTATEA DE MATEMATIC ˘A S, I INFORMATIC ˘A
Concurs FMI ed. a VII-a, 2022
Subiecte Proba II - 10.04.2022
Informatic˘a
SUBIECTUL I
Un turneu este o form˘a de competit, ie ˆın mai multe runde, ˆın fiecare rund˘a
fiind eliminat, i jum˘atate din participant, ii r˘amas, i, cealalt˘a jum˘atate avansˆand
ˆın faza urm˘atoare. Vom folosi mai departe cazul unui turneu de s, ah.
Consideram c˘a ˆın fiecare runda meciurile vor fi planificate aleator, alegˆand
din participant, ii r˘amas, i ˆın competit, ie. Atunci cˆand r˘amˆan 4 participant, i,
cˆas, tig˘atorii celor dou˘a meciuri vor concura pentru locurile 1 s, i 2, iar cei
ˆınvins, i nu vor fi eliminat, i, ci vor concura pentru locurile 3 s, i 4.
Sarcina este s˘a scriet, i un program care cites, te lista de participant, i, apoi
cites, te toate meciurile. La finalul execut, iei, programul va afis, a clasamentul
cu numele primilor 3 clasat, i. Propunet, i o solut, ie cˆat mai eficient˘a.
Datele de intrare sunt structurate astfel:
• pe prima linie se g˘ases, te num˘arul de participant, i, N , (N este o putere
a lui 2);
• pe urm˘atoarele N linii se vor g˘asi indicativul s, i numele participant, ilor;
• pe urm˘atoarele N/2 linii se vor g˘asi rezultatele primei runde, ca triplete
de numere, reprezentˆand indicativele concurent, ilor s, i indicativul con-
curentului cˆas, tig˘ator;
• pe restul liniilor se vor g˘asi rezultatele urm˘atoarelor runde, ˆıns˘a in-
dicativul nu va reprezenta concurentul, ci num˘arul meciului din runda
anterioar˘a;
• ˆın cazul ultimelor dou˘a meciuri, meciul pentru locurile 3 s, i 4 va fi
primul.
Observat, ie: 4 ≤ N ≤ 1024
Exemplu date intrare (simbolul // este urmat de un comentariu care nu
va ap˘area ˆın setul de date propriu-zis):
1

Subiect și barem · pagina 2

8 // num˘arul de concurent, i
1 Adrian
2 Kuzmin
3 Ivan
4 Katerina
5 George
6 Volodymir
7 Vlad
8 Peter
1 3 1 // Adrian vs. Ivan, c^as, tig˘ator Adrian
2 6 6 // Kuzmin vs. Volodymir, c. Volodymir
4 8 8 // Katerina vs Peter, c. Peter
5 7 5 // George vs Vlad, c. George
1 3 3 // meci 1 vs meci 3: Adrian vs. Peter
2 4 2 // meci 2 vs meci 4: Volodymir vs George
1 2 1 // finala mica: Adrian vs. George
1 2 2 // finala mare: Peter vs. Volodymir
Rezultat:
1 Volodymir
2 Peter
3 Adrian
SUBIECTUL II
Se consider˘a c˘a ˆıntr-o sect, ie de product, ie pot fi realizate mai multe pro-
duse folosind o mas, ina pe care pot fi executate diferite tipuri de operat, ii.
Fiecare produs se obt, ine aplicˆand o secvent, ˘a de cel put, in 2 operat, ii s, i se
consider˘a c˘a mult, imile de operat, ii aferente unor produse diferite sunt dis-
juncte. Informat, iile despre procesul de product, ie sunt stocate ˆıntr-o matrice
de precedent, ˘a P de dimensiune N × N , N fiind num˘arul total de operat, ii
care pot fi executate pe mas, in˘a. Elementele lui P sunt valori din mult, imea
{0, 1} s, i sunt completate astfel ˆıncˆat Pij = 1 dac˘a s, i numai dac˘a operat, iile
i s, i j sunt implicate ˆın realizarea aceluias, i produs, iar operat, ia i trebuie
executata imediat ˆınainte de operat, ia j. O operat, ie care este precedat˘a de
o alt˘a operat, ie dar pentru care nu exist˘a operat, ie care sa o succead˘a este
asociata cu un produs. Durata fiec˘arei operat, ii este 1, iar costul operat, iei i
este Ci
Observat, ie: Indicii ˆıncep de la 1.
2

Subiect și barem · pagina 3

Partea I
(i) S˘a se determine num˘arul de produse distincte c˘arora le corespund informat, iile
din matricea P .
(ii) S˘a se determine duratele s, i costurile de product, ie ale produselor ale
c˘aror secvente de operat, ii sunt specificate ˆın P . Produsele se vor afis, a
ˆın ordinea cresc˘atoare a identificatorului produsului.
Date de intrare:
• pe prima linie se g˘ases, te N , dimensiunea matricii;
• pe a doua linie se g˘asesc costurile pentru fiecare operat, ie (N numere
ˆıntregi).
• urmeaz˘a maxim N linii reprezentˆand indicii i, j din P pentru care
Pi,j = 1.
Date de ies, ire:
• pe prima linie se scrie num˘arul de produse identificate
• pe urm˘atoarele linii vor fi afis, ate triplete P T C: unde P este num˘arul
produsului, T este durata s, i C este costul tuturor operat, iilor pentru
produsul P ; tripletele vor fi afis, ate ˆın ordinea cresc˘atoare a lui P .
Partea II - (doar pentru clasa XII-a)
Considerˆand c˘a toate produsele au acelas, i pret, de vˆanzare P r, s˘a se de-
termine care dintre produse ar putea fi realizate ˆıntr-un interval de timp
[0, T ] astfel ˆıncˆat profitul total (diferent, a dintre pret, ul de vˆanzare al tuturor
produselor realizate s, i costul total) s˘a fie cˆat mai mare.
Date de intrare:
• pe prima linie se g˘ases, te N (dimensiunea matricii), T (timpul maxim
de product, ie) s, i P r (pret, ul fiec˘arui produs, toate au acelas, i pret, );
• pe a doua linie se g˘asesc costurile pentru fiecare operat, ie (N numere
ˆıntregi);
• urmeaz˘a maxim N linii reprezentˆand perechi de indicii i, j din matricea
P pentru care Pi,j = 1.
3

Subiect și barem · pagina 4

Date de ies, ire:
• vor fi afis, ate pe o singur˘a linie produsele selectate, ˆın ordine cresc˘atoare
a indicilor
Exemplu Fie N = 10, P este specificata prin perechile de indici core-
spunz˘atoare elementelor egale cu 1: (2, 5), (8, 2), (10, 1), (7, 4), (6, 7), (3, 6),
costurile operat, iilor sunt C = {3, 4, 4, 1, 2, 2, 3, 5, 3, 2}, T = 5, iar pret, ul de
vˆanzare este P r = 50. Pentru acest exemplu se obt, in:
• (Partea I) num˘arul de produse este 3;
• (Partea I) duratele s, i costurile produselor sunt: produsul 1 are costul 5
s, i durata 2, produsul 4 are costul 10 s, i durata 4, produsul 5 are costul
11 s, i durata 3;
• (Partea II) grupul de produse realizat ˆın intervalul [0, 5] cu profit
maxim este 1 s, i 5.
4

Subiect și barem · pagina 5

UNIVERSITATEA DE VEST TIMIS, OARA
FACULTATEA DE MATEMATIC ˘A S, I INFORMATIC ˘A
Concurs FMI ed. a VII-a, 2022
Barem Proba II - 10.04.2022
Informatic˘a
SUBIECTUL I - 100 pct.
Testare automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 pct.
Test 1 (vizibil) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct.
Test 2 (caz extrem) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Test 3 (caz general) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Evaluare oral˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 pct.
Prezentarea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Eficient, a solut, iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Claritatea solut, iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 pct.
SUBIECTUL II (Partea I) - 100 pct.
Testare automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 pct.
Test 1 (vizibil) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct.
Test 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Test 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Evaluare oral˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 pct.
Prezentarea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Folosirea structurilor de date . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Claritatea solut, iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 pct.
SUBIECTUL II (Partea a II-a) 100 pct.
Testare automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 pct.
Test 1 (vizibil) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 pct.
Test 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Test 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Evaluare oral˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 pct.
1

Subiect și barem · pagina 6

Prezentarea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 pct.
Argumentarea obt, inerii solut, iei optime . . . . . . . . . . . . . . . . . . . . . 20 pct.
Claritatea solut, iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 pct.
Exemple implementare ˆın limbajul C++
Subiectul I
#i n c l u d e <i o s t r e a m >
u s i n g namespace s t d ;
i n t main ( ) {
i n t N, l o c 1 , l o c 2 , l o c 3 , i , j , x ;
c h a r nume [ 6 5 ] [ 1 0 0 ] ;
i n t m e c i u r i [ 6 5 ] , m e c i u r i n o i [ 6 5 ] ;
// c i t i r e a n u m e l o r c o n c u r e n t i l o r
c i n >> N ;
f o r ( i n t k = 0 ; k < N ; k++){
c i n >> i ;
c i n >> nume [ i ] ;
}
// i n p r i m a r u n d a c a s t i g a t o r u l m e c i u l u i a r e c h i a r i n d i c a t i v u l n u m e l u i
// s e c i t e s c N/2 m e c i u r i , s e c l a s e a z a pe p r i m e l e N/2 p o z i t i i c a s t i g a t o r i i .
// c o n c u r e n t i i i n v i n s i s u n t c l a s a t i i n a doua j u m a t a t e ;
// p t N = 4 , c e i i n v i n s i v o r j u c a f i n a l a mica .
f o r ( i n t k = 0 ; k < N/ 2 ; k++) {
c i n >> i >> j >> x ;
i f ( i == x ) {
m e c i u r i [ k ] = i ;
m e c i u r i [ k+N/ 2 ] = j ;
} e l s e {
m e c i u r i [ k ] = j ;
m e c i u r i [ k+N/ 2 ] = i ;
}
}
N = N / 2 ;
// s e c i t e s c r e s t u l l i n i i l o r , s e c l a s e a z a l a f e l ca mai s u s
// e s t e n e v o i e de un t a b l o u s u p l i m e n t a r p e n t r u a nu s u p r a s c r i e v a l o r i
w h i l e (N > 2 ) {
f o r ( i n t k = 0 ; k < N/ 2 ; k++) {
c i n >> i >> j >> x ;
i f ( i == x ) {
m e c i u r i n o i [ k ] = m e c i u r i [ i − 1 ] ;
m e c i u r i n o i [ k+N/ 2 ] = m e c i u r i [ j − 1 ] ;
} e l s e {
2

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Concurs de pregătire · 2022Informatică · Etapa 1Deschide fișa Concurs de pregătire · 2022Matematică · Clasa a XI-a, etapa 1Deschide fișa Concurs de pregătire · 2022Matematică · Clasa a XI-a, etapa 2Deschide fișa Concurs de pregătire · 2022Matematică · Clasa a XII-a, etapa 1Deschide fișa Concurs de pregătire · 2022Matematică · Clasa a XII-a, etapa 2Deschide fișa Examen de admitere · 2022Informatică · Sesiunea iulie; subiect oficialDeschide 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 2022 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.

Pregătire cu un profesor

Subiect și barem

Concurs de pregătire · Informatică · 2022

Despre acest subiect

Subiectul și baremul în format text

Subiect și barem · pagina 1