Model de pregătire · Informatică · 2025

Subiect și barem · pagina 1

Concursul MateInfoUB
Sect, iunea Informatic˘a
Problemele rezolvate din edit, iile 2021-2024

Subiect și barem · pagina 2

Copyright © 2025 Facultatea de Matematică s, i Informatică, Universitatea din Bucures, ti
Publicat în format PDF
github.com/MateInfo-UB
Licensed under the Creative Commons Attribution-NonCommercial 4.0 License (the
“License”). You may not use this file except in compliance with the License. You may
obtain a copy of the License at https://creativecommons.org/licenses/by-nc-sa/4.0.
Unless required by applicable law or agreed to in writing, software distributed under the
License is distributed on an “as is” basis, without warranties or conditions of any kind,
either express or implied. See the License for the specific language governing permissions
and limitations under the License.
Prima edit, ie, 2025

Subiect și barem · pagina 3

Introducere
Concursul MateInfoUB este un concurs multi-disciplinar anual, având o sect, iune de
Matematică s, i una de Informatică, organizat de Facultatea de Matematică s, i Informatică
din cadrul Universită t, ii din Bucure s, ti. Pot participa elevii claselor a XII-a sau orice
absolvent de liceu cu diplomă de bacalaureat.
Concursul are două etape: prima etapă se desfă s, oară online, iar a doua etapă se
desfăs, oară cu prezen t, ă fizică în Facultatea de Matematică s, i Informatică. Pe lângă bucuria
participării la un concurs în care î s, i pot testa cuno s, tint, ele, concurent, ii au posibilitatea de a
ob t, ine puncte bonus pentru examenul de admitere. Mai mult, concuren t, ii cu rezultate
deosebite pot fi admis, i fără examen, conform metodologiei proprii. Metodologia de ad-
mitere postată la adresa https://fmi.unibuc.ro/admitere/ detaliază toate aceste lucruri.
În această culegere putet, i regăsi toate problemele date de-a lungul celor 4 edit, ii (2021-
2024) de până acum ale concursului la sect, iunea de Informatică precum s, i rezolvările lor.
Prima edit, ie a concursului a avut loc în anul 2021 s, i a stabilit formatul competit, iei pentru
sect, iunea Informatică:
• O etapă online de două ore deschisă tuturor celor înscri s, i, cu 20 de probleme de tip
grilă. Problemele sunt împăr t, ite în 10 probleme de dificultate scăzută, 6 probleme de
dificultate medie s, i 4 probleme de dificultate crescută. Problemele rezolvate corect
valorează 2, 3 respectiv 5 puncte, în funct, ie de dificultatea lor.
• O etapă fizică desfă s, urată în Facultatea de Matematică-Informatică, la care sunt
invita t, i primii aproximativ 150-200 de elevi, conform clasamentului primei etape, cu
4 sau 5 probleme de natură algoritmică, care necesită scrierea unei solut, ii în C/C++.
O bună parte din rezolvările cuprinse în această carte au fost realizate de către
studen t, i din anul 3 ai facultă t, ii de la domeniul Informatică sub atenta îndrumare a
membrilor comisiei. De asemenea, am creat s, i o platformă online, accesibilă la adresa
https://mateinfo-ub.github.io/, unde putet, i simula etapa întâi a concursului. Pentru
întrebări sau sugestii ne putet, i contacta la adresa intrebari.mateinfo@g.unibuc.ro.
Comisia concursului MateInfoUB, Sect, iunea Informatică
3

Subiect și barem · pagina 4

Pagina nu conține text selectabil. Consultă PDF-ul pentru imagini și cerințe.

Subiect și barem · pagina 5

Cuprins
I Probleme din etapa întâi
1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Probleme de dificultate sc˘azut˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Probleme de dificultate medie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4 Probleme de dificultate crescut˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.1 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
II Probleme din etapa a doua
5 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.1 Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.2 Kscale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.3 Secretariat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.4 Grile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5

Subiect și barem · pagina 6

CUPRINS
6 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.1 Cazane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2 Felinare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.3 Tren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.4 Vopsesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.1 Bebelus, i Plâng˘acios, i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.2 Cadouri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.3 Fork Bomb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.4 Agar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
8.1 Râme pane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
8.2 Pr˘ajitur˘a cu mujdei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.3 R˘acituri cu pireu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.4 Cornis, oni afumat, i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6

Subiect și barem · pagina 7

IProbleme din etapa întâi
1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Probleme de dificultate sc˘azut˘a . . . . . . 11
2.1 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Probleme de dificultate medie . . . . . . . 53
3.1 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4 Probleme de dificultate crescut˘a . . . . . 85
4.1 Din anul 2021 . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2 Din anul 2022 . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3 Din anul 2023 . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4 Din anul 2024 . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7

Subiect și barem · pagina 8

Pagina nu conține text selectabil. Consultă PDF-ul pentru imagini și cerințe.

Subiect și barem · pagina 9

1. Introducere
Etapa I a concursului se desfăs, oară online. Participant, ii sunt rugat, i să se conecteze la
platforma de concurs, s, i, după începerea concursului au două ore să rezolve cât mai multe
întrebări de tip grilă.
Concursul cont, ine 20 de probleme, ordonate crescător după dificultate:
• 10 probleme de dificultate scăzută, care valorează câte 2 puncte.
• 6 probleme de dificultate medie, care valorează câte 3 puncte.
• 4 probleme de dificultate crescută, care valorează câte 5 puncte.
Nu există penalizări pentru răspunsuri gres, ite, deci concurent, ii sunt încurajat, i să
răspundă la toate problemele.
Problemele pot fi rezolvate de studen t, i cum î s, i doresc, dar tipic se împart în 3 categorii:
• Probleme care se pot rezolva pe foaie, i.e. probleme de logică, observat, ie, calcule
simple, etc.
• Probleme care se pot rezolva manual sau cu ajutorul unui program: unele probleme
pot fi rezolvate prin crearea unui algoritm, dar datele de intrare sunt suficient de
mici pentru a permite rezolvarea acestuia pe foaie.
• Probleme care nu se pot rezolva decât prin implementarea unui program.
9

Subiect și barem · pagina 10

Pagina nu conține text selectabil. Consultă PDF-ul pentru imagini și cerințe.

Subiect și barem · pagina 11

2. Probleme de dificultate sc˘azut˘a
2.1 Din anul 2021
Problema 1
Care este ultima cifră a celui mai mare număr de 7 cifre, divizibil cu 7, care cont, ine în
Fcomponenta sa doar cifre strict mai mici decât 7?
A. 0 (CORECT) B. 2 C. 3 D. 5 E. 6
Explicat, ie:
Cele mai mari numere de 7 cifre care nu con t, in decât cifre strict mai mici decât 7 sunt
6666666, 6666665, 6666664 . . .
Observăm că 666666 ≡ 6(mod 7). As, adar, cel mai mare număr care este divizibil cu 7 s, i
respectă condit, ia din enunt, este 6666660.
Problema 2
Care expresie implementează corect ⌈ n
k ⌉ pentru toate perechile n, k de numere naturale
nenule? (⌈a⌉ reprezintă partea întreagă superioară a numărului real a, spre exemplu
⌈2.8⌉ = 3, n/k reprezintă câtul împăr t, irii lui n la k s, i n%k reprezintă restul împărt, irii lui n la
k).
A. n/k B. (n + k)/k C. (n + k − 1)/k (CORECT) D. n/(k − 1) E. (n/k) + (n%k)
Explicat, ie:
Operatorul ’/’ pe numere naturale din C/C++ întoarce partea întreagă rotunjită în jos.
As, adar, există două cazuri:
1. n este divizibil cu k =⇒ (n + k − 1)/k = n/k = ⌈ n
k ⌉.
2. n nu este divizibil cu k =⇒ (n + k − 1)/k = n/k + 1 = ⌈ n
k ⌉.
Problema 3
Considerăm următorul cod scris în limbajul C++:
int f(int t[10000], int n) {
int i = 0, s = 0;
while (i < n) {
int j = i + 1;
while (j < n && t[i] == t[j])
j += 1;
11

Subiect și barem · pagina 12

Probleme de dificultate sc˘azut˘a
s += 1;
i = j;
}
return s;
}
Defini t, ie: O subsecven t, ă a lui t este o listă de valori aflate pe pozit, ii consecutive crescătoare,
de e.g., [t[3], t[4], t[5]]. Un sub s, ir al lui t este o listă de valori aflate pe pozi t, ii ordonate
crescător (nu neapărat consecutive), de e.g., [t[3], t[5], t[9]].
Presupunând că tabloul t este format din n numere ordonate crescător, preciza t, i ce
returnează f (t, n)?
A. numărul valorilor distincte din tabloul t (CORECT)
B. lungimea maximă a unei subsecvenţe din tabloul t formată din valori egale
C. numărul subsecvenţelor strict crescătoare din tabloul t
D. lungimea maximă a unui subs, ir din tabloul t format din valori egale
E. numărul valorilor care se repetă de cel put, in două ori din tabloul t
Explicat, ie:
Analizând codul putem observa că valoarea lui s este incrementată de fiecare dată când
j ajunge pe o pozit, ie pentru care t[i]̸ = t[ j] sau ajunge la valoarea n. Prin urmare, f (t, n)
pentru un tablou t este format din n numere ordonate crescător calculează numărul de
valori distincte din tablou.
Problema 4
Într-o sală de conferin t, e se află mai multe persoane, fiecare având un număr suficient
de mare de căr t, i de vizită. Se s, tie că oricare două persoane pot face schimb de cărt, i de
vizită cel mult o singură dată. Dacă s-au efectuat în total 23052021 de schimburi, care este
numărul minim de persoane prezente în sală?
A. 4801 B. 4802 C. 4803 D. 6790 E. 6791 (CORECT)
Explicat, ie:
Pentru a putea determina răspunsul la întrebare trebuie să ne dăm seama cum aflăm dacă
pentru un număr dat se poate realiza numărul acela de schimburi. Pentru un număr dat
n, numărul maxim de schimburi posibile este: (n−1)·n
2 , deoarece prima persoană poate
schimba cu celelalte n − 1, a doua cu restul de n − 2 (deoarece cu prima a schimbat deja)
s, .a.m.d., iar persoana n − 1 va putea să mai schimbe cu persoana n. Mai mult, pentru n
persoane, se poate realiza orice număr de schimburi între 1 s, i (n−1)·n
2 .
A s, adar, pentru a afla răspunsul, vom calcula pentru fiecare număr dat dacă numărul
23052021 este mai mic decât numărul maxim de schimburi. Observăm că doar 6791
respectă această condit, ie.
Problema 5
Pentru un graf G, un arbore par t, ial este un graf conex, fără cicluri, con t, inând acela s, i număr
de noduri ca G s, i doar muchii din G (dar nu neapărat toate).
Numărul de arbori part, iali ai grafului de mai jos este egal cu:
12

Subiect și barem · pagina 13

Concursul MateInfoUB, Sect, iunea Informatic˘a
A. 12 B. 11 (CORECT) C. 9 D. 15 E. 16
Explicat, ie:
Un mod de abordare al acestei probleme ar fi să observăm că pentru a ajunge la un arbore
part, ial putem elimina pe rând câte o muchie din fiecare ciclu.
În cazul de fat, ă graful are 3 ciclii: 1 − 3 − 2 − 0 − 4, 1 − 3 − 2 − 4 s, i 2 − 0 − 4. Putem
începe cu oricare ciclu vrem, fără a fi nevoie după aceea să începem s, i cu ceilalt, i pentru că
am număra arborii de mai multe ori (dacă scoatem aceleas, i muchii, ordinea scoaterii lor
este irelevantă, deoarece obt, inem acelas, i arbore).
Începem prin eliminarea unei muchii de pe primul ciclu ment, ionat anterior. Avem 5
posibilităt, i de alegere a acesteia. În urma eliminării muchiei alese, vom rămâne fie cu al
doilea ciclu, fie cu al treilea.
Dacă eliminăm una dintre muchiile (1, 3), (3, 2), (1, 4), graful va cont, ine doar ciclul
2 − 0 − 4. Pentru a scăpa s, i de acest ciclu trebuie să eliminăm una dintre cele 3 muchii ale
sale. Dacă procedăm astfel avem în total 3 · 3 = 9 arbori part, iali.
Dacă eliminăm una dintre muchiile (2, 0), (0, 4), graful va con t, ine doar ciclul 1−3−2−4.
Pentru a scăpa s, i de acest ciclu trebuie să eliminăm una dintre cele 4 muchii ale sale. Dintre
toate perechile posibile de alegere a celor 2 muchii, doar două dintre ele nu au apărut în
primul caz, anume perechile: (2, 0), (2, 4) s, i (2, 4), (4, 0).
As, adar, deoarece am considerat toate cazurile de formare a unui arbore part, ial, s, tim că
pentru arborele din enunt, sunt 11 arbori part, iali.
Observat, ie:
Putem rezolva problema folosind s, i o abordare teoretică, precum cea explicată aici.
Problema 6
Un număr natural se numes, te palindrom dacă se cites, te la fel de la stânga la dreapta s, i de la
dreapta la stânga. Spre exemplu, 13231 s, i 2662 sunt palindromuri, dar 145 sau 1234322 nu
sunt.
Un număr natural se numes, te pseudo-palindrom dacă cifrele sale pot fi reordonate astfel
încât să devină palindrom (în particular, orice palindrom este s, i pseudo-palindrom). Spre
exemplu, 13321 s, i 2626 sunt pseudo-palindromuri.
Fie X cel mai mare număr pseudo-palindrom mai mic sau egal cu 1000465. Care este restul
13

Subiect și barem · pagina 14

Probleme de dificultate sc˘azut˘a
lui X la împărt, irea cu 37?
A. 36 B. 4 C. 1 D. 35 (CORECT) E. 25
Explicat, ie:
Pentru ca un număr să fie pseudo-palindrom el trebuie să respecte una din următoarele două
condit, ii:
1. Numărul are o lungime pară s, i toate cifrele care apar în el au o frecvent, ă pară
2. Numărul are o lungime impară s, i toate cifrele care apar în el au o frecven t, ă pară, cu
except, ia uneia care apare de un număr impar de ori
Plecând de la numărul din enunt, 1000465 putem să vedem că lungimea lui este impară,
iar fiecare cifră apare de un număr impar de ori. Deoarece ne dorim să găsim cel mai mare
număr pseudo-palindrom mai mic decât acesta, vom vrea să lăsăm numărul de apari t, ii ale
lui 0 să fie impar s, i 1 s, i 4 să apară de un număr par de ori.
As, adar, numărul căutat este 1000441, iar restul lui la împărt, irea cu 37 este 35.
Problema 7
Se dă următoarea adunare: ERAM + MARE = MARET unde fiecare majusculă reprezintă
o cifră (nu neapărat distinctă de celelalte). Fiind primele cifre ale numerelor, cifrele
corespunzătoare lui M s, i E trebuie să fie diferite de 0.
Care este valoarea sumei M + A + R + E + T ?
A. 21 B. 7 C. 16 D. 18 (CORECT) E. 30
Explicat, ie:
Cel mai simplu mod de rezolvare al acestei probleme se bazează pe scrierea unui cod în
C + + în care să verificăm pentru fiecare număr de ERAM dacă adunat cu oglinditul său
MARE dă MARET . Din faptul că nu se precizează ce ar trebui să facem dacă sunt mai multe
perechi de numere de acest fel, putem deduce că există o singură pereche neordonată
de numere (ERAM, MARE) care satisface această proprietate. O implementare a solu t, iei
descrise mai sus în limbajul C++ este următoarea:
int oglindit(int n)
{
int ogl = 0;
while (n)
{
ogl = ogl * 10 + n % 10;
n /= 10;
}
return ogl;
}
int sum_cif(int n)
{
int sum = 0;
while (n)
{
sum += n % 10;
n /= 10;
}
return sum;
14

Subiect și barem · pagina 15

Concursul MateInfoUB, Sect, iunea Informatic˘a
}
int main()
{
for (int eram = 1000; eram <= 9999; eram++)
if (eram % 10 != 0 && eram / 100 != 0) // e!=0 && m!=0
{
int mare = oglindit(eram);
if ((eram + mare) / 10 == mare) //<=> eram + mare == maret
{
cout << sum_cif(eram + mare);
break; // nu vrem sa consideram si perechea (mare,eram)
}
}
return 0;
}
Problema 8
Ionel are 10 creioane. Lungimile fiecărui creion sunt:
4, 3, 7, 8, 7, 4, 5, 8, 13, 15
El î s, i dores, te să obt, ină creioane având doar două lungimi diferite. Pentru a realiza acest
lucru, el poate scurta (prin ascut, ire) unele creioane.
Care este suma maximă a lungimilor creioanelor pe care o poate obt, ine Ionel, după ce
efectuează operat, iile?
A. 46 B. 50 C. 54 (CORECT) D. 56 E. 62
Explicat, ie:
Cel mai simplu mod de rezolvare al acestei probleme se bazează pe scrierea unui cod în
C + +. Observăm că una dintre cele două lungimi alese va fi reprezentată de lungimea
minimă, iar pe cealaltă o fixăm pe rând, după care calculăm răspunsul s, i păstrăm lungimea
optimă. O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int main()
{
// tinem lungimile direct sortate
int v[] = {3, 4, 4, 5, 7, 7, 8, 8, 13, 15};
int maxx = 0;
for (int pos2 = 1; pos2 <= 9; pos2++)
{
int ans = 0;
// lungimile mai mici le reducem la v[0]
ans += v[0] * pos2;
// lungimile mai mari le reducem la v[pos2]
ans += v[pos2] * (9 - pos2 + 1);
15

Subiect și barem · pagina 16

Probleme de dificultate sc˘azut˘a
maxx = max(maxx, ans);
}
cout << maxx;
return 0;
}
Problema 9
O mul t, ime de numere naturale se numes, te 13-liberă dacă nu putem ob t, ine numărul 13 ca
sumă a unor elemente distincte din mult, ime. Spre exemplu, mul t, imea 1, 5, 7, 11 nu este
13-liberă fiindcă 1 + 5 + 7 = 13, dar mul t, imea 1, 5, 6 este 13-liberă (notându-se că desigur
1 + 6 + 6 = 13, condit, ia descrisă nu este încălcată, 6 fiind folosit de două ori).
Care este cardinalul maxim al unei submult, imi 13-libere a mult, imii 1, 2, 3, . . . , 10?
A. 5 (CORECT) B. 4 C. 3 D. 6 E. 8
Explicat, ie:
Putem rezolva problema matematic sau scriind un program cu un algoritm de tip
backtracking. Vom prezenta prima variantă, deoarece este considerabil mai rapidă.
Pentru a forma o mul t, ime cât mai mare trebuie să observăm care perechi de 2 numere
din mult, imea dată au suma 13. Acestea sunt: (3, 10), (4, 9), (5, 8) s, i (6, 7). Evident, la rândul
lor numerele din aceste perechi pot fi scrise ca sumă de alte 2 numere din mult, imea dată.
Nu vom enumera toate aceste perechi, deoarece sunt destul de multe.
Observăm că optim ar fi să adăugăm init, ial fie elemente cât mai mici, fie elemente cât
mai mari s, i că dacă am începe cu elemente cât mai mari este mai us, or să ne asigurăm că
submult, imea este 13-liberă.
Să spunem că init, ial îl selectăm pe 10. Vom putea să le selectăm s, i pe 9, 8, 7 păstrând
proprietatea submult, imii de a fi 13-libere. Însă acum observăm că nu putem adăuga niciun
element din mul t, imea 3, 4, 5, 6. Prin urmare, putem adăuga fie 1, fie 2. Pe oricare l-am
selecta, după nu vom mai putea extinde mul t, imea, deoarece fiecare element rămas ar face
ca proprietatea submult, imii să dispară.
Momentan nu am demonstrat că nu există o submul t, ime de cardinal mai mare ca 5
care să fie 13-liberă. Acest lucru se poate demonstra alegând toate submult, imile de cardinal
6 s, i arătând că niciuna nu este 13-liberă.
As, adar, cardinalul maxim al unei submult, imi 13-libere a mult, imii 1, 2, 3, . . . , 10 este 5.
Problema 10
Fie n cel mai mare număr natural prim de 5 cifre cu toate cifrele distincte.
Care este restul împărt, irii lui n la 37?
A. 27 B. 4 C. 11 D. 15 (CORECT) E. 31
Explicat, ie:
Pentru rezolvarea acestei probleme vom scrie un program C + + care să verifice pentru
fiecare număr de 5 cifre dacă are toate cifrele distincte s, i, în caz afimativ, dacă este prim.
Vom parcurge numerele în ordine descrescătoare pentru a ne opri după primul număr
care satisface această proprietate. O implementare a solut, iei descrise mai sus în limbajul
C++ este următoarea:
16

Subiect și barem · pagina 17

Concursul MateInfoUB, Sect, iunea Informatic˘a
bool cif_dist(int n)
{
int fr[10] = {};
// n are fix 5 cifre, deci cazul n=0 nu apare
while (n)
{
fr[n % 10]++;
n /= 10;
}
for (int i = 0; i <= 9; i++)
if (fr[i] >= 2)
return false;
return true;
}
bool prim(int n)
{
if (n < 2)
return false;
if (n == 2)
return true;
if (n % 2 == 0)
return false;
for (int d = 3; d * d <= n; d += 2)
if (n % d == 0)
return false;
return true;
}
int main()
{
for (int i = 99999; i >= 10000; i--)
if (cif_dist(i) && prim(i))
{
cout << i % 37;
break;
}
return 0;
}
2.2 Din anul 2022
Problema 1
Cel mai mare exponent k astfel încât 12k divide numărul 100! este ?
A. 8 B. 25 C. 33 D. 48 (CORECT) E. 97
Explicat, ie:
Fie mult, imea factorilor primi ai unui număr natural n, ea este de forma
{(x1, p1), (x2, p2), . . . , (xk, pk)} unde xi reprezintă un factor prim, iar pi este puterea la care
17

Subiect și barem · pagina 18

Probleme de dificultate sc˘azut˘a
acesta este prezent. Ca un număr natural a să fie divizibil cu un alt număr natural b,
este necesar ca, pentru fiecare factor prim din mul t, imea lui a, acesta să fie prezent în
mul t, imea lui b, iar puterea sa să fie mai mare sau egală cu puterea respectivului factor din a.
Mul t, imea factorilor primi ai numărului 12 este {(2, 2), (3, 1)}. Când analizăm mul t, imea
factorilor primi ai lui 12k, aceasta devine {(2, 2 · k), (3, k)}. Prin urmare, trebuie să determi-
năm cea mai mare valoare k pentru care aces, ti factori primi sunt prezent, i la o putere mai
mare în 100!.
Pentru a determina puterea factorului 2 în 100!, aplicăm următoarea metodă de numărare:
mai întâi determinăm câte numere au cel pu t, in un factor de 2, numărul lor fiind ⌊ 100
2 ⌋,
unde ⌊n⌋ reprezintă partea întreagă a unui număr natural n. Apoi calculăm câte numere
au cel pu t, in 2 factori de 2, cu ⌊ 100
4 ⌋, s, i continuăm procesul până când rezultatul devine
0. La final, însumăm toate aceste valori. Aplicăm aceea s, i strategie s, i pentru factorul
3. Corectitudinea metodei derivă din faptul că, prin procesul iterativ, calculăm treptat
contribut, ia fiecărei puteri. Astfel obt, inem rezultatele:
• Puterea lui 2 în 100!: ⌊ 100
2 ⌋ + ⌊ 100
4 ⌋ + ⌊ 100
8 ⌋ + ⌊ 100
16 ⌋ + ⌊ 100
32 ⌋ + ⌊ 100
64 ⌋ = 50 + 25 + 12 + 6 +
3 + 1 = 97.
• Puterea lui 3 în 100!: ⌊ 100
3 ⌋ + ⌊ 100
9 ⌋ + ⌊ 100
27 ⌋ + ⌊ 100
81 ⌋ = 33 + 11 + 3 + 1 = 48.
Pentru a determina cel mai mare exponent k, ne interesează cea mai mare valoare k care
respectă condi t, iile: 2 · k ≤ 97 s, i k ≤ 48. Din prima condit, ie rezultă k < 48.5, iar din a doua
k ≤ 48. As, adar, valoarea maximă a lui k este k = 48.
O strategie alternativă este implementarea unui algoritm care să determine acest lucru.
Aceasta poate fi realizată fie printr-o metodă naivă, calculând pentru fiecare număr
descompunerea sa în factori primi, fie aplicând metoda descrisă mai sus. Ambele solut, ii
sunt eficiente. Iată o implementare naivă în limbajul C++:
int getAns() {
int p2 = 0, p3 = 0;
for(int i = 1; i <= 100; i++) {
int aux = i;
while(aux % 2 == 0) {
p2++;
aux /= 2;
}
while(aux % 3 == 0) {
p3++;
aux /= 3;
}
}
return min(p2 / 2, p3);
}
Această func t, ie returnează valoarea k = 48, care este s, i răspunsul corect. Prin urmare,
varianta D este corectă.
18

Subiect și barem · pagina 19

Concursul MateInfoUB, Sect, iunea Informatic˘a
Problema 2
Considerăm o matrice pătratică A de dimensiune 10 × 10, având liniile s, i coloanele indexate
de la 1. Orice element A[i][ j] al matricei este egal cu minimul dintre i s, i j (1 ≤ i, j ≤ 10).
Suma tuturor elementelor din matricea A este egală cu:
A. 285 B. 385 (CORECT) C. 500 D. 550 E. 715
Explicat, ie:
Pentru a afla suma elementelor matricei putem aplica următoarea strategie, vrem să vedem
câte elemente au valoare 1, pentru asta trebuie ca un element să se situeze ori pe prima
coloană, ori pe prima linie, prin urmare vom avea numărul de linii + numărul de coloane -
1 (există un element care se află s, i pe prima linie s, i pe prima coloană), deci vom avea de 19
ori valoarea 1, apoi pentru valoarea 2 vrem să vedem câte elemente se situează pe coloana
2 sau pe linia 2, s, i nu le-am numărat deja, vom avea tot 19 numere, dintre care 2 le-am
numărat deja (A[2][1] s, i A[1][2]), deci vom avea 17 valori de 2, putem continua procesul s, i
vom obt, ine 15 valori de 3, 13 valori de 4, 11 valori de 5, 9 valori de 6, 7 valori de 7, 5 valori
de 8, 3 valori de 9 s, i o valoare de 10, însumându-le pe toate vom obt, ine suma 385.
O altă variantă este să scriem un scurt program care să calculeze răspunsul. Pentru aceasta,
vom itera prin elementele matricei s, i vom calcula suma acestora. O implementare în
limbajul C++ este următoarea:
int getAns() {
int ans = 0;
for(int i = 1; i <= 10; i++)
for(int j = 1; j <= 10; j++)
ans += min(i, j);
return ans;
}
Funct, ia va întoarce valoarea 385, care este s, i răspunsul corect, prin urmare varianta B este
corectă.
Problema 3
Pentru numărul natural pozitiv n, definim funct, ia f (n) astfel:
• f (1) = 1,
• f (n) = 1 + f (n/2), dacă n este par,
• f (n) = 1 + f (3n + 1), dacă n este impar s, i diferit de 1.
Spre exemplu, f (10) = 1 + f (5) = 1 + 1 + f (16) = 1 + 1 + 1 + f (8) = · · · = 7.
Cu cât este egal f (2022)?
A. 64 (CORECT) B. 128 C. 256 D. 512 E. 1024
Explicat, ie:
O primă observa t, ie care facilitează o rezolvare rapidă este asemănarea func t, iei descrise
cu conjectura lui Collatz. La o analiză mai atentă, se poate observa că func t, ia numără
cât, i pas, i sunt necesari în conjectura lui Collatz. Putem folosi această observa t, ie pentru
a identifica o resursă online care să ne calculeze această valoare, cum ar fi aceasta. Cu
ment, iunea că, în resursa oferită, pas, ii sunt indexat, i de la 0, obt, inem valoarea 63, care de
fapt corespunde celui de-al 64-lea pas datorită indexării.
19

Subiect și barem · pagina 20

Probleme de dificultate sc˘azut˘a
Dacă nu observăm această legătură cu conjectura lui Collatz sau nu suntem familiariza t, i
cu aceasta, avem două opt, iuni:
• Să calculăm manual pas, ii, ceea ce nu este recomandat, deoarece din variantele de
răspuns este clar că numărul maxim de pas, i poate ajunge până la 1024.
• Să implementăm func t, ia într-un limbaj de programare. Această abordare este mult
mai rapidă, iar implementarea este simplă.
Iată un exemplu de implementare în limbajul C++:
int f(int n) {
if(n == 1) return 1;
if(n % 2 == 0) return 1 + f(n / 2);
return 1 + f(3 * n + 1);
}
Această func t, ie returnează valoarea 64, care reprezintă răspunsul corect. Prin urmare,
varianta A este corectă.
Problema 4
Numerele de la 1 la 20.000 sunt scrise în ordine într-o carte cu 100 de foi (200 de pagini),
câte 100 de numere pe pagină.
Mai exact, prima foaie, alcătuită din paginile 1 s, i 2, con t, ine pe prima pagină numerele
de la 1 la 100 s, i pe a doua pagină numerele de la 101 la 200. A doua foaie, compusă din
paginile 3 s, i 4, cont, ine numerele de la 201 la 400 etc.
Cineva dezleagă cartea, amestecă foile s, i o leagă la loc. Aten t, ie, foile nu sunt rotite sau
întoarse, ci doar permutate.
Care este probabilitatea ca numerele de la 1150 la 1250 să fie în continuare consecutive?
A. 1 B. 1/2 C. 1/99 D. 1/100 (CORECT) E. 99/10100
Explicat, ie:
O primă observa t, ie este faptul că, înainte de orice permutare, numerele de la 1150 la 1200
se află pe foaia 6, iar numerele de la 1201 la 1250 pe foaia 7, prin urmare, acestea se află pe
foi diferite. Noi suntem interesat, i doar de pozit, iile celor două foi.
Avem 100 de pozi t, ii în care putem plasa prima foaie, iar următoarea foaie are 99 de pozit, ii
disponibile în care poate fi plasată. Astfel, numărul cazurilor posibile este 100 · 99 = 9900.
Pe noi ne interesează să plasăm a doua foaie imediat după prima. Acest lucru se poate
întâmpla doar dacă prima foaie nu este ultima foaie plasată. În rest avem un caz favorabil
pentru fiecare din cele 99 de plasări posibile ale primei foi. Prin urmare, există 99 de cazuri
favorabile.
În concluzie probabilitatea este: 99
9900 = 1
100 . Astfel răspunsul corect este D.
Problema 5
Fie mul t, imea de numere reale A = {-3000, 3000, -2000, 2000, -1000, 1000, -13, 13, -7, 7, -5, 5,
-1.5, 1.5, -0.75, 0.75, -0.5, 0.5, 0}. Care este numărul de elemente al submult, imii de produs
maxim din A?
20

Subiect și barem · pagina 21

Concursul MateInfoUB, Sect, iunea Informatic˘a
A. 9 B. 13 C. 14 D. 15 (CORECT) E. 18
Explicat, ie:
Pentru început, vom considera valoarea absolută a produsului. Este evident că orice
număr cu valoarea absolută mai mare decât 1 va mări acest produs. Prin urmare, vom lua
în considerare toate valorile absolute mai mari decât 1. În total, există 14 astfel de valori.
A doua condit, ie pentru maximizarea produsului este să avem un număr par de valori
negative. Dintre cele 14 valori, 7 sunt negative, as, a că trebuie fie să eliminăm o valoare
negativă, fie să adăugăm o valoare negativă pentru a obt, ine un număr par. Putem să
eliminăm cea mai mică valoare negativă, care este −1.5 sau adăugăm cea mai mare valoare
negativă care nu se află deja între cele 14, aceasta fiind −0.75. Deoarece −1.5 · −0.75 = 1.125,
adăugarea lui −0.75 va conduce la un produs mai mare.
Prin urmare, produsul maxim cont, ine 15 valori. Răspunsul corect este D.
Problema 6
În t, ara fermecată, există 100 de oras, e, identificate cu numerele de la 0 la 99, s, i următoarele
drumuri bidirect, ionale:
• Autostrăzi între ora s, ele (0, 9), (10, 19), (20, 29), . . . , (90, 99), a căror traversare durează
4 ore;
• Drumuri comunale între ora s, ele (0, 1), (1, 2), . . . , (98, 99), a căror traversare durează 1
oră.
Cât durează cel mai rapid traseu de la oras, ul 12 la oras, ul 72?
A. 29 B. 30 C. 34 (CORECT) D. 35 E. 38
Explicat, ie:
Pentru început observăm că dorim să folosim autostrăzile cât mai mult posibil. Prin
urmare, în drumul de la 12 la 72, primul nod important este 20, deoarece acesta este
următorul punct care cont, ine o autostradă. Pentru a ajunge la 20, putem fie să luăm
drumul {12, 13, . . . , 20} cu costul 8, fie drumul {12, 11, 10, 19, 20} cu costul 7. Astfel, costul
minim pentru a ajunge la 20 este 7.
Apoi, dorim să ne mutăm la 70, deoarece acesta este cel mai apropiat punct cu autostradă
mai mic decât 72. De asemenea, vrem să folosim autostrăzile cât mai mult posibil. Prin
urmare, este evident că cel mai bun drum este {20, 29, 30, 39, 40, 49, 50, 59, 60, 69, 70}, cu un
cost de 25. În continuare, de la 70 la 72, cel mai bun drum este {70, 71, 72}. După adunarea
celor trei segmente, obt, inem un cost total de 7 + 25 + 2 = 34.
O altă opt, iune ar fi să construim graful s, i să rulăm algoritmul lui Dijkstra pe acesta pentru
a găsi cea mai scurtă rută de la nodul 12 la nodul 72. Un exemplu de implementare în
limbajul C++ este următorul:
int getAns() {
struct muchie{
int vecin, cost;
};
vector<muchie> adj[105];
21

Subiect și barem · pagina 22

Probleme de dificultate sc˘azut˘a
for(int i = 0; i < 99; i++) {
adj[i].push_back({i + 1, 1});
adj[i + 1].push_back({i, 1});
}
for(int i = 0; i < 99; i += 10) {
adj[i].push_back({i + 9, 4});
adj[i + 9].push_back({i, 4});
}
int d[105];
for(int i = 0; i <= 99; i++) {
d[i] = 1e9;
}
priority_queue<pair<int, int>> q;
d[12] = 0;
q.push({0, 12});
while(!q.empty()) {
auto aux = q.top();
q.pop();
if(aux.first != d[aux.second]) continue;
for(auto much: adj[aux.second]) {
int dist = aux.first + much.cost;
if(dist < d[much.vecin]) {
d[much.vecin] = dist;
q.push({dist, much.vecin});
}
}
}
return d[72];
}
Funct, ia ne întoarce valoarea 34 care este s, i răspunsul corect, prin urmare varianta corectă
este C.
Problema 7
Fie o matrice pătratică de dimensiune 2022 ce cont, ine valori de 1 s, i 0, astfel încât există
exact o valoare egală cu 1 pe fiecare linie s, i pe fiecare coloană. În matrice este permisă
interschimbarea a două valori din celule vecine pe verticală sau pe orizontală (considerăm
că două celule sunt vecine dacă au o latură comună). Considerând toate matricile cu o
asemenea proprietate, care este numărul minim de interschimbări necesare pentru a aduce
toate valorile de 1 pe aceeas, i linie sau pe aceeas, i coloană?
A. 2022 B. 511566 C. 510555 D. 1021110 E. 1022121 (CORECT)
22

Subiect și barem · pagina 23

Concursul MateInfoUB, Sect, iunea Informatic˘a
Explicat, ie:
Pentru început, vom considera o coloană C oarecare. Deoarece avem doar câte o valoare
pe fiecare linie, este evident că nu este necesar să schimbăm linia vreunui element. Prin
urmare, mutăm valorile doar între coloane. Mai mult, costul minim pentru a aduce toate
elementele de 1 pe coloana C este suma valorilor absolute ale diferent, elor dintre C s, i
coloana fiecărui element. Deoarece avem un element pe fiecare coloană, suma poate fi
scrisă astfel: 2022
∑
i=1
|i −C|,
unde |a| reprezintă valoarea absolută a lui a.
În acest punct, observăm două lucruri. Primul că este întotdeauna optim să alegem coloana
cea mai centrală pentru a minimiza suma. Al doilea este faptul că suma minimă obt, inută
pentru mutarea pe o coloană a tuturor elementelor este aceeas, i ca suma optimă pentru
mutarea pe o linie a tuturor elementelor. Prin urmare, suma optimă este dată de coloanele
1011 s, i 1012 sau liniile 1011 s, i 1012.
Înlocuind C în formulă cu 1011, obt, inem suma 1022121. Prin urmare, răspunsul corect
este E.
Problema 8
Ultima cifră a numărului 11 + 22 + 33 + · · · + 20222022 este:
A. 0 B. 1 C. 3 D. 5 E. 9 (CORECT)
Explicat, ie:
Pentru această problemă, este necesar să scriem cod pentru a determina ultima cifră a
sumei date. Observăm că este suficient să considerăm valorile modulo 10, deoarece ultima
cifră a unui număr corespunde restului împărt, irii acestuia la 10.
În ceea ce prives, te implementarea, putem opta pentru două abordări:
1. O implementare naivă, cu o complexitate temporală de O(n2), unde calculăm fiecare
termen s, i adunăm succesiv.
2. O solut, ie optimizată, bazată pe ridicarea la putere în timp logaritmic, cu o com-
plexitate temporală de O(n · log2(n)), unde n este valoarea până la care calculăm suma.
În continuare, vom considera următorul fragment de cod, care implementează cea de-a
doua variantă, mai eficientă, bazată pe ridicarea la putere în timp logaritmic în limbajul
C++:
int lgput(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = (res * a) % 10;
a = (a * a) % 10;
b >>= 1;
}
return res;
}
23

Subiect și barem · pagina 24

Probleme de dificultate sc˘azut˘a
int getAns() {
int sum = 0;
for (int i = 1; i <= 2022; i++) {
sum += lgput(i, i);
}
return sum % 10;
}
Ideea de bază a ridicării la putere în timp logaritmic constă în faptul că, atunci când avem
o valoare a s, i un exponent b, putem să calculăm puterea ab prin metoda exponent, ierii
succesive. Astfel, în loc să calculăm direct ab, se poate calcula a = a · a, iar exponentul b
este înjumătăt, it. În cazul în care b este impar, rezultatul se multiplică cu a. Astfel, putem
construi eficient puterea ab prin înmult, irea unor termeni corespunzători lui a ridicat la
puteri de 2.
Func t, ia returnează valoarea 9, care reprezintă s, i răspunsul corect. Prin urmare, varianta
corectă este E.
Problema 9
Câte numere Fibonacci sunt în intervalul închis [1234567890, 9876543210]?
A. 1 B. 2 C. 4 (CORECT) D. 8 E. 16
Explicat, ie:
Putem scrie un scurt fragment de cod pentru a rezolva această problemă, dar vom încerca
să o rezolvăm fără cod momentan. Notăm x = 1234567890.
Observăm că 8 · x < 9876543210 < 9 · x.
Vom încerca să stabilim o limită inferioară pentru numărul minim de numere Fibonacci
necesare. În acest sens, vom demonstra că în orice interval [y, 2y], există cel put, in un număr
Fibonacci. Vom presupune, pentru contradict, ie, că nu există niciun număr Fibonacci în
intervalul [y, 2y]. În acest caz, vom avea doi termeni Fibonacci consecutivi, b s, i c, astfel
încât b < y s, i c > 2y. (1)
Fie a, b, s, i c trei numere consecutive din s, irul Fibonacci, unde a ≤ b. Având în vedere că
c = a + b, este evident că c ≤ 2b. Astfel, b ≤ c ≤ 2b, ceea ce contrazice ipoteza formulată la
punctul (1). Prin urmare, în orice interval [y, 2y] există cel put, in un număr Fibonacci.
Acum s, tim că trebuie să avem, un număr în intervalul [x, 2x], unul în intervalul [2x, 4x], s, i
unul în intervalul [4x, 8x]. Prin urmare, vom avea minim 3 numere Fibonacci.
Cât despre o limită superioară, vom încerca să plasăm cât mai multe numere Fibonacci
în acest interval. Pentru a face acest lucru, dorim ca primele două numere Fibonacci din
interval să fie cât mai mici. Alegem aceste două numere ca fiind x s, i x, ob t, inând secven t, a
Fibonacci:
{x, x, 2x, 3x, 5x, 8x}.
Deja, 13 · x va depă s, i intervalul. Astfel, chiar s, i cu această logică optimistă, avem cel mult 6
numere Fibonacci în interval.
24

Subiect și barem · pagina 25

Concursul MateInfoUB, Sect, iunea Informatic˘a
Am demonstrat că răspunsul se află în intervalul [3, 6]. Singura variantă care poate fi
corectă este C.
O solut, ie eficientă, care nu necesită realizarea tuturor observat, iilor anterioare, constă
în generarea numerelor Fibonacci până când acestea depă s, esc valoarea superioară a
intervalului, urmată de verificarea câtorva dintre ele care se află în interval. Deoarece
există O(log2(n)) numere Fibonacci, acest tip de verificare poate fi realizat într-un timp
foarte rapid. O posibilă implementare a acestei solut, ii în limbajul C++ este următoarea:
int getAns() {
long long a = 0, b = 1;
long long minn = 1234567890, maxx = 9876543210;
int ans = 0;
while(b <= maxx) {
if(b >= minn) ans++;
long long c = a + b;
a = b;
b = c;
}
return ans;
}
Facem observa t, ia că tipul de date long long a fost utilizat pentru a preveni un eventual
overflow. Funct, ia returnează valoarea 4, astfel că răspunsul corect este C.
Problema 10
Fie graful neorientat G dat prin mult, imea nodurilor V = {1, 2, . . . , 1000} s, i mul t, imea
muchiilor E = {(i, j) | i + jeste număr prim, 1 ≤ i, j ≤ 1000}. Care este numărul ciclurilor
distincte de lungime 3 din graful G? (Două cicluri sunt considerate distincte dacă ele diferă
prin cel put, in o muchie.)
A. 0 (CORECT) B. 1 C. 27 D. 64 E. 125
Explicat, ie:
Fie un ciclu {a, b, c}. Pentru ca aceasta să fie un ciclu, este necesar ca toate numerele din
mul t, imea {a + b, a + c, b + c} să fie prime s, i, de asemenea, ca a, b, c să fie distincte. Prin
urmare, toate numerele din această mult, ime sunt mai mari sau egale cu 3.
În continuare, s, tim că două numere din mul t, imea {a, b, c} au aceeas, i paritate, deoarece
există 3 numere s, i doar 2 parită t, i, ceea ce înseamnă că o paritate trebuie să se repete
neapărat. Prin urmare, cel pu t, in un număr din mul t, imea {a + b, a + c, b + c} trebuie să
fie par s, i să fie mai mare sau egal cu 3. Deoarece un număr par mai mare sau egal cu 3
nu poate fi prim, cel put, in un număr din mul t, imea {a + b, a + c, b + c} nu este prim. În
concluzie, există 0 cicluri de lungime 3.
O altă metodă de rezolvare, în cazul în care nu identificăm observat, iile ment, ionate anterior,
este implementarea unui algoritm care verifică toate combinat, iile de trei noduri pentru a
determina dacă acestea formează un ciclu. Mai precis, verificăm dacă toate valorile din
25

Subiect și barem · pagina 26

Probleme de dificultate sc˘azut˘a
mult, imea {a + b, a + c, b + c} sunt numere prime.
Pentru a face acest lucru, putem calcula, ini t, ial, toate numerele prime mai mici decât
2000 utilizând fie algoritmul ciurului lui Eratostene, fie o metodă naivă. După generarea
numerelor prime, putem aplica o verificare naivă pentru fiecare triplet de noduri, cu o
complexitate de timpO(n3), unde n este numărul total de noduri ale grafului.
O implementare în limbajul C++ a acestui algoritm este prezentată mai jos:
int getAns() {
int notPrime[2005] = {0};
notPrime[1] = 1;
for(int i = 2; i <= 2000; i++) {
if(notPrime[i] == 0) {
for(int j = 2 * i; j <= 2000; j += i) {
notPrime[j] = 1;
}
}
}
int cnt = 0;
for(int i = 1; i <= 1000; i++) {
for(int j = i + 1; j <= 1000; j++) {
for(int k = j + 1; k <= 1000; k++) {
if(!(notPrime[i + j] || notPrime[j + k] || notPrime[i + k])) cnt++;
}
}
}
return cnt;
}
Funct, ia returnează valoarea 0, care este s, i răspunsul corect, prin urmare varianta corectă
este A
Problema 11
Matei are 5 cafele. Fiecare cafea are un volum (dat în ml) s, s, i o concentra t, ie dată în
procente. Matei poate amesteca două cafele. Dacă amestecă o cafea cu v1 ml s, i concentrat, ie
c1 cu una cu v2 ml s, i concentrat, ie c2, atunci el va obt, ine o cafea cu:
• volum v1 + v2
• concentrat, ie c1·v1+c2·v2
v1+v2
Satisfact, ia adusă lui Matei de o cafea cu volum v s, i concentrat, ie c este v · c.
S, tiind că Matei are:
• o cafea de 50 ml s, i concentrat, ie de 40% (c = 0.4),
• o cafea de 100 ml s, i concentrat, ie de 30% (c = 0.3),
• o cafea de 300 ml s, i concentrat, ie de 10% (c = 0.1),
• o cafea de 250 ml s, i concentrat, ie de 10% (c = 0.1),
• o cafea de 500 ml s, i concentrat, ie de 50% (c = 0.5),
care este cea mai mare satisfact, ie pe care o poate ob t, ine Matei amestecând optim cafelele?
A. 10 B. 355 (CORECT) C. 250 D. 40 E. 450
26

Subiect și barem · pagina 27

Concursul MateInfoUB, Sect, iunea Informatic˘a
Explicat, ie:
După o analiză a celor două formule, observăm că satisfac t, ia unei cafele obt, inute prin
combinarea a două alte cafele este dată de următoarea relat, ie:
c1 · v1 + c2 · v2
v1 + v2
· (v1 + v2) = c1 · v1 + c2 · v2.
De aici, putem deduce că satisfact, ia unei cafele rezultate din combinarea a două cafele
este egală cu suma satisfac t, iilor individuale ale acestora. Prin urmare, pentru a atinge
satisfac t, ia maximă, ar trebui să combinăm toate cafelele disponibile. Un alt mod de a
aborda problema este să observăm că satisfact, ia unei cafele este propor t, ională cu cantitatea
de cafeină pe care o cont, ine. Astfel, pentru a maximiza satisfac t, ia, trebuie să combinăm
toate cafelele pentru a obt, ine cantitatea maximă de cafeină.
50 · 0.4 + 100 · 0.3 + 300 · 0.1 + 250 · 0.1 + 500 · 0.5 = 355.
As, adar, răspunsul corect este B.
Problema 12
Se consideră o suprafat, ă (matrice) infinită în jos s, i în dreapta cu liniile numerotate de sus în
jos s, i coloanele de la stânga la dreapta. O furnică explorează această suprafat, ă pornind din
col t, ul stânga sus (1, 1). Deoarece furnica este prudentă s, i vrea să rămână mereu aproape
de zona explorată deja ( s, i marcată cu feromoni), explorarea se face extinzând succesiv
pătratul deja parcurs din colt, ul stânga sus.
Astfel La început furnica coboară în celula (2, 1), apoi merge în dreapta în celula (2, 2)
s, i apoi urcă în celula (1, 2), completând un pătrat 2 × 2. Pe acesta îl extinde mergând în
dreapta în celula (1, 3), apoi coboară în (2, 3) s, i (3, 3), după care se deplasează spre stânga
în celulele (3, 2) s, i (3, 1), completând un pătrat 3 × 3.
Pe acesta îl extinde coborând în (4, 1), mergând în dreapta până în (4, 4) s, i apoi urcând în
(1, 4). Continuând în acest fel, furnica poate explora o suprafat, ă oricât de mare. Mai jos se
pot vedea pa s, ii la care a fost vizitată fiecare celulă până când furnica explorează un pătrat
5 × 5:
1 4 5 16 17
2 3 6 15 18
9 8 7 14 19
10 11 12 13 20
25 24 23 22 21
Pe ce linie s, i pe ce coloană se va afla furnica la pasul 100001?
A. (144, 316) B. (145, 316) C. (145, 317) (CORECT) D. (316, 145) E. (317, 145)
Explicat, ie:
Vom nota n = 100001. Putem observa că 316 · 316 < n ≤ 317 · 317, prin urmare valoarea n se
va afla fie pe linia 317 s, i o coloană mai mică sau egală cu 317, fie pe coloana 317 s, i o linie
mai mică sau egală cu 317. De asemenea, se observă că bucă t, ile impare sunt numerotate
de sus, iar cele pare de la stânga. Prin urmare, valoarea 316·316+1 se află pe pozit, ia (1, 317).
27

Subiect și barem · pagina 28

Probleme de dificultate sc˘azut˘a
S, tim că n − 316 · 316 = 145. Folosind cele două observat, ii de mai devreme, putem deduce
că elementul 316 · 316 + 145 se va afla la pozit, ia (145, 317).
As, adar, răspunsul corect este C.
Problema 13
Matei are un PC nou, care rulează PearOS. Alex a reus, it să îi fure calculatorul s, i acum
încearcă să îi ghicească parola. Alex s, tie că Matei are o parolă de lungime 10 caractere,
formată din litere mici ale alfabetului englez. De asemenea, pentru o experient, ă mai plăcută
a utilizatorului, atunci când o parolă gre s, ită este introdusă, PearOS notifică utilizatorul
dacă parola adevărată este mai mică sau mai mare lexicografic decât cea introdusă.
Dacă Alex caută parola în mod optim, atunci numărul de încercări pe care le va efectua
este:
A. cuprins între 0 s, i 30
B. cuprins între 31 s, i 60 (CORECT)
C. cuprins între 61 s, i 90
D. cuprins între 91 s, i 120
E. mai mare sau egal cu 121
Explicat, ie:
Singura informat, ie pe care PearOS i-o oferă lui Alex este dacă parola introdusă este mai
mică sau mai mare din punct de vedere lexicografic fa t, ă de parola corectă. Alex trebuie să
minimizeze numărul de încercări folosindu-se de această informat, ie.
Această informa t, ie este extrem de utilă, deoarece îi permite lui Alex să construiască o
solu t, ie bazată pe căutare binară. S, tim că există 26 de litere mici în alfabetul englez, ceea ce
înseamnă că există 2610 parole posibile. Alex va introduce întotdeauna parola care se află
la mijloc din punct de vedere lexicografic în intervalul de căutare curent. În funct, ie de
răspunsul primit (dacă parola corectă este mai mare sau mai mică decât cea introdusă), el
poate înjumătă t, i intervalul de căutare. De exemplu, dacă parola corectă este mai mare
decât cea introdusă, căutarea se va concentra pe partea superioară a intervalului.
Repetând acest proces pe intervalele obt, inute succesiv, Alex va înjumătăt, i numărul de
parole posibile la fiecare pas. Prin urmare, numărul total de încercări necesare este dat de
log2(2610), care poate fi descompus astfel:
log2(2610) = 10 · log2(26).
Cum log2(26) este aproximativ 4.7, rezultă că Alex va avea nevoie de aproximativ 10·4.7 = 47
încercări. As, adar, răspunsul corect este B.
Problema 14
Alex a încercat să organizeze un concurs online, dar cu câteva minute înainte de începerea
sa, s, i-a dat seama că platforma nu este suficient de puternică pentru a găzdui to t, i candidat, ii
s, i riscă să pice în timpul probei.
La concurs participă 1000 de candidat, i s, i Alex dores, te să închirieze câteva servere. Un
server este caracterizat de pret, ul său (cât îl costă pe Alex să închirieze serverul pe durata
probei) s, i capacitatea sa (numărul de concurent, i pe care serverul îi poate servi).
Alex are de ales între următoarele opt, iuni de servere:
28

Subiect și barem · pagina 29

Concursul MateInfoUB, Sect, iunea Informatic˘a
• servere cu pret, ul 2 s, i capacitate 2;
• servere cu pret, ul 5 s, i capacitate 10;
• servere cu pret, ul 10 s, i capacitate 23.
De notat că Alex poate închiria oricâte servere, indiferent dacă sunt sau nu de acelas, i tip.
Care este costul minim cu care Alex poate închiria servere cu suma capacită t, ilor mai mare
sau egală cu 1000?
A. 500 B. 433 C. 440 D. 439 E. 437 (CORECT)
Explicat, ie:
Putem observa că un server cu o capacitate mai mare oferă întotdeauna un raport
capacitate/pre t, mai bun. Prin urmare, este evident că dorim să achizi t, ionăm cât mai multe
servere de capacitate mare. Pentru a acoperi capacitatea necesară de 1000, ar fi nevoie de
44 de servere de capacitate 23, ceea ce ar genera un cost total de 440.
A doua observa t, ie este că, în solut, ia optimă, nu vor exista mai mult de un server de
capacitate 10. Dacă ar exista două astfel de servere, ele ar putea fi înlocuite cu un
server de capacitate 23, oferind o capacitate mai mare fără a afecta costul. Similar, nu
putem avea mai mult de două servere de capacitate 2, deoarece trei astfel de servere
ar putea fi înlocuite cu un server de capacitate 10, la un cost mai mic s, i o capacitate mai mare.
T, inând cont de aceste observat, ii, putem îmbunătăt, i solut, ia init, ială renunt, ând la cel mult
un server de capacitate 23. Astfel, putem utiliza 43 de servere de capacitate 23, care oferă o
capacitate totală de 989. Pentru a completa diferen t, a de 11 unită t, i, achizi t, ionăm un server
de capacitate 10 s, i unul de capacitate 2. În acest mod, costul total devine 437, mai mic
decât cel obt, inut anterior. Aceasta este solut, ia optimă s, i răspunsul corect.
O a doua abordare constă în scrierea unui algoritm care să rezolve problema. Aceasta
poate fi modelată ca o problemă de programare dinamică. Definim func t, ia d p(i), unde
d p(i) reprezintă costul minim pentru a atinge suma i. Vom utiliza mult, imea de servere
S = {(2, 2), (5, 10), (10, 23)}. Ini t, ial, setăm d p(0) = 0, iar restul valorilor sunt init, ializate la
o valoare mare. Aplicăm următoarele tranzit, ii pentru fiecare element al mult, imii S:
d p(i) =
(
min(d p(i), d p(i − capacitate) + cost), dacă i ≥ capacitate,
d p(i), altfel.
Aici, min(x, y) este o func t, ie care returnează valoarea minimă dintre x s, i y, iar ’capacitate‘
s, i ’cost‘ reprezintă caracteristicile fiecărui server din mult, imea S.
Rezultatul dorit este minimul valorilor d p(i) pentru i ≥ 1000. De asemenea, solu t, ia optimă
se va afla la o valoare i < 1000 + capacitatea maximă, deoarece, în caz contrar, un server ar
putea fi eliminat pentru a îmbunătăt, i solu t, ia, men t, inând suma peste sau egală cu 1000. O
implementare în limbajul C++ este următoarea:
int getAns() {
int dp[1025] = {0};
for(int i = 1; i <= 1023; i++) {
dp[i] = 1e5;
}
int cost[] = {2, 5, 10}, capacitate[] = {2, 10, 23};
for(int i = 0; i < 3; i++) {
29

Subiect și barem · pagina 30

Probleme de dificultate sc˘azut˘a
for(int j = capacitate[i]; j < 1023; j++) {
dp[j] = min(dp[j], dp[j - capacitate[i]] + cost[i]);
}
}
int ans = 1e5;
for(int i = 1000; i < 1023; i++) {
ans = min(ans, dp[i]);
}
return ans;
}
Această funct, ie returnează valoarea 437, care reprezintă s, i răspunsul corect. În final,
ment, ionăm că, des, i solu t, iile bazate pe algoritmi greedy pot oferi răspunsuri optime pentru
anumite valori, există cazuri în care acestea nu vor produce solut, ia optimă.
În concluzie, răspunsul corect este E.
Problema 15
Matei are următoarea permutare:
9, 1, 2, 6, 5, 4, 3, 7, 10, 8
El are voie să efectueze cel mult 5 operat, ii de interschimbare a două elemente alăturate.
Care este cea mai mică permutare în ordine lexicografică pe care o poate obt, ine?
A. 1, 2, 5, 6, 9, 4, 3, 7, 10, 8
B. 1, 2, 4, 6, 9, 5, 3, 7, 10, 8
C. 1, 2, 6, 5, 4, 9, 3, 7, 10, 8
D. 1, 2, 4, 9, 6, 5, 3, 7, 10, 8 (CORECT)
E. 1, 2, 4, 9, 5, 6, 3, 7, 10, 8
Explicat, ie:
Pentru a obt, ine cea mai mică permutare din punct de vedere lexicografic, este necesar să
utilizăm operat, iile de interschimbare pentru a aduce elementele cât mai mici în fat, ă.
De asemenea, s, tim că primele pozit, ii ale unei permutări sunt cele mai valoroase în de-
terminarea ordinii lexicografice. Prin urmare, o strategie optimă constă în a începe cu
prima pozi t, ie, identificând cel mai mic element care poate fi adus în fa t, ă utilizând un
număr maxim de 5 opera t, ii. După fiecare schimbare, procesul continuă pentru următoarea
pozit, ie, folosind operat, iile rămase.
Pornind de la permutarea init, ială:
9, 1, 2, 6, 5, 4, 3, 7, 10, 8,
putem observa că elementul 1 poate fi adus pe prima pozit, ie utilizând o singură opera t, ie.
După această mutare, obt, inem permutarea:
1, 9, 2, 6, 5, 4, 3, 7, 10, 8,
30

Subiect și barem · pagina 31

Concursul MateInfoUB, Sect, iunea Informatic˘a
rămânând cu 4 operat, ii disponibile. Procedând similar pentru pozit, ia a doua, elementul 2
poate fi adus în fat, ă folosind o singură operat, ie. Astfel, obt, inem permutarea:
1, 2, 9, 6, 5, 4, 3, 7, 10, 8,
rămânând cu 3 operat, ii disponibile. Pentru pozi t, ia a treia, cea mai mică valoare care poate
fi adusă este 4. Aceasta necesită utilizarea exactă a celor 3 operat, ii rămase. Efectuând
schimburile necesare, obt, inem permutarea finală:
1, 2, 4, 9, 6, 5, 3, 7, 10, 8.
Astfel, răspunsul corect este D.
Problema 16
În timpul taberei la munte, Alex are de aprins un foc. El are la dispozi t, ie o grămadă de
lemne de diferite mărimi, identificate prin numere de la 1 la 100. Unicul bă t, , de dimensiune
1, este un chibrit, cu care Alex are de aprins focul. De s, i buturuga mică răstoarnă carul mare,
nu poate ca un chibrit să aprindă un bus, tean. De fapt, o bucată de lemn de dimensiune d
care ia foc la momentul t aprinde la momentul t + 1 toate bucă t, ile neaprinse de dimensiune
mai mică sau egală cu 2 · d.
S, tiind că grămada de lemne cont, ine bucăt, i cu dimensiunile:
1, 2, 2, 2, 3, 5, 5, 5, 7, 13, 14, 15, 15, 25, 35, 50, 50, 51, 78, 99, 100
s, i că Alex dă foc chibritului în momentul t = 1, care este primul moment de timp când
toate lemnele sunt aprinse?
A. 6 B. 7 C. 8 D. 9 (CORECT) E. 10
Explicat, ie:
La momentul de timp t + 1, lemnele care se vor aprinde sunt determinate de cel mai
mare lemn aprins la momentul t. Procesul poate fi modelat astfel: pornim de la starea
(1, 1), unde prima valoare reprezintă momentul de timp, iar cea de-a doua reprezintă
dimensiunea celui mai mare lemn aprins. În momentul t = 2, toate lemnele cu dimensiuni
mai mici sau egale cu 2 · 1 = 2 se vor aprinde, trecând astfel în starea (2, 2). În momentul
t = 3, toate lemnele mai mici sau egale cu 2 · 2 = 4 vor fi aprinse. Deoarece 3 este cel mai
mare lemn mai mic sau egal cu 4, starea devine (3, 3). Continuând acest proces, vom trece
succesiv prin următoarele stări:
(1, 1) → (2, 2) → (3, 3) → (4, 5) → (5, 7) → (6, 13) → (7, 25) → (8, 50) → (9, 100)
În starea (9, 100), toate lemnele vor fi aprinse.
De asemenea, problema poate fi rezolvată algoritmic prin scrierea unui fragment de cod.
Vom stoca dimensiunile lemnelor într-un vector s, i vom aplica un algoritm de tip greedy.
La fiecare moment de timp, ret, inem dimensiunea celui mai mare lemn aprins s, i pozi t, ia
curentă în vector. La cres, terea momentului de timp, determinăm noua pozit, ie în vector
corespunzătoare lemnelor aprinse. O implementare în limbajul C++ este următoarea:
int getAns() {
int a[] = {1, 2, 2, 2, 3, 5, 5, 5, 7,
13, 14, 15, 15, 25, 35, 50, 50, 51, 78, 99, 100};
int t = 1, curr = 1, nrLemne = 21;
31

Subiect și barem · pagina 32

Probleme de dificultate sc˘azut˘a
while(curr < nrLemne) {
int maxVal = a[curr - 1];
while(curr < nrLemne && a[curr] <= 2 * maxVal) {
curr++;
}
t++;
}
return t;
}
Această func t, ie returnează valoarea 9, care este, de altfel, răspunsul corect. Prin urmare,
varianta D este corectă.
Problema 17
Matei s, i-a cumpărat o plantă nouă, pe care trebuie să o ude zilnic, cu exact un litru de apă.
El are patru sticle, init, ial goale, cu volumele de 2, 8, 10 s, i 20 litri.
Într-o operat, ie, Matei poate să:
• ia o sticlă, pe care o umple complet de la robinet;
• ia două sticle s, i varsă cât de mult poate din prima în a doua (fie până când prima
sticlă se goles, te, fie până când a doua sticlă se umple);
• udă planta, dacă are o sticlă umplută cu exact 1 litru.
Considerăm afirmat, iile următoare:
1. Matei poate uda planta în 6 mutări.
2. Matei poate uda planta folosind numai 3 sticle.
3. Matei poate uda planta fără să folosească mai mult de 22 de litri de apă.
4. Matei nu poate uda planta.
Care din afirmat, ii este adevărată?
A. afirmat, iile 1, 2 s, i 3
B. afirmat, iile 1 s, i 2
C. afirmat, ia 4 (CORECT)
D. afirmat, iile 2 s, i 3
E. afirmat, iile 1, 2 s, i 4
Explicat, ie:
Pentru început, observăm că afirma t, ia 4 este contradictorie cu toate celelalte, deoarece
sus t, ine că udarea plantei nu este posibilă, în timp ce celelalte afirmat, ii presupun că udarea
este posibilă s, i adaugă anumite restrict, ii.
Vom analiza mai întâi validitatea afirma t, iei 4. Observăm că toate sticlele au capacită t, i
pare, iar operat, iile disponibile sunt următoarele:
• umplerea completă a unei sticle de la robinet
• golirea unei sticle într-o altă sticlă până când prima se goles, te complet sau a doua
devine plină
Prin urmare, folosind doar prima operat, ie toate volumele de apă manipulate vor fi numere
pare, deoarece sticlele au capacită t, i pare. Adică sticle care au o cantitate pară de apă s, i au
nevoie de o cantitate pară de apă ca să fie pline
32

Subiect și barem · pagina 33

Concursul MateInfoUB, Sect, iunea Informatic˘a
În momentul în care aplicăm opera t, ia de golire a unei sticle în alta (operat, ia 2), pentru
prima oară, situat, ia init, ială presupune că toate sticlele con t, in volume pare de apă, s, i au
nevoie de un volum par de apă ca să fie pline. Aplicând această operat, ie, avem următoarele
cazuri:
• Dacă golim o sticlă într-o sticlă cu capacitate mai mică, aceasta din urmă se va umple
complet, iar volumul rămas în prima sticlă va fi tot par, deoarece se scade un volum
par dintr-un alt volum par.
• Dacă umplem o sticlă care necesită un volum par de apă, după opera t, ie vom avea o
sticlă goală s, i o altă sticlă plină cu un volum par.
În toate cazurile, observăm că volumele rămân pare în fiecare sticlă. Astfel, indiferent de
operat, iile efectuate, nu putem obt, ine un volum impar de apă în nicio sticlă. Deoarece este
necesar un volum de exact 1 litru (un număr impar) pentru a uda planta, concluzionăm că
acest lucru este imposibil.
Prin urmare, răspunsul corect este C.
Problema 18
Considerăm o matrice pătratică A de dimensiune n = 1000, având liniile s, i coloanele
indexate de la 1.
Orice element A[i][ j] al matricei este egal cu ((i + j) mod n) + 1. Dacă sumlin(i) reprezintă
suma tuturor elementelor aflate pe linia i s, i sumcol( j) reprezintă suma tuturor elementelor
aflate pe coloana j, atunci valoarea maximă a expresiei |sumlin(i) − sumcol( j)|, unde
i, j ∈ {1, 2, . . . , n}, este egală cu:
A. 0 (CORECT) B. 500 C. 1000 D. 1998 E. 500500
Explicat, ie:
Vom analiza valorile elementelor de pe linia i din matrice. Aceste valori au următoarea
structură:
((i + 1) mod n) + 1, ((i + 2) mod n) + 1, ((i + 3) mod n) + 1, . . . , ((i + n) mod n) + 1.
Examinând mai atent s, i ignorând temporar adunarea cu 1, observăm că i + j ia treptat
fiecare valoare de la i + 1 la i + n. Aplicând opera t, ia mod n, aceste valori vor lua fiecare
valoare de la 0 la n − 1 exact o dată. Adăugând 1, fiecare element al liniei va lua o valoare
distinctă între 1 s, i n. Prin urmare, suma tuturor elementelor de pe o linie este:
sumlin(i) = n · n + 1
2 = 500500.
Aceea s, i observa t, ie este valabilă s, i pentru coloane. Fixând j, iterăm i de la 1 la n, iar fiecare
valoare din 1 până la n este întâlnită o dată. Astfel, suma elementelor de pe orice coloană
este identică cu suma elementelor de pe orice linie:
sumcol( j) = 500500.
Prin urmare, valoarea expresiei |sumlin(i) − sumcol( j)| este 0 pentru orice i, j ∈ {1, 2, . . . , n}.
De asemenea dacă nu observăm aceste lucruri putem implementa un scurt fragment de cod
care construies, te matricea, apoi calculează suma pentru fiecare linie s, i coloană, urmând să
itereze prin toate posibilităt, ile de a alege linia s, i coloană. Fragmentul de cod în limbajul
C++ este următorul:
33

Subiect și barem · pagina 34

Probleme de dificultate sc˘azut˘a
int getAns() {
int sumLinie[1005] = {0}, sumColoana[1005] = {0};
for(int i = 1; i <= 1000; i++) {
for(int j = 1; j <= 1000; j++) {
int elem = (i + j) % 1000 + 1;
sumLinie[i] += elem;
sumColoana[j] += elem;
}
}
int ans = 0;
for(int i = 1; i <= 1000; i++) {
for(int j = 1; j <= 1000; j++) {
ans = max(ans, abs(sumLinie[i] - sumColoana[j]));
}
}
return ans;
}
Această funct, ie returnează valoarea 0, confirmând că răspunsul corect este A.
Problema 19
Considerăm s, irul infinit 1234567891011121314151617181920 . . ., ob t, inut prin alipirea tu-
turor cifrelor tuturor numerelor naturale nenule. Considerând s, irul respectiv ca fiind
indexat de la 0, cifra aflată pe pozit, ia 21052022 este egală cu:
A. 1 (CORECT) B. 2 C. 3 D. 6 E. 9
Explicat, ie:
În primul rând, vom rezolva problema fără a apela la instrumente algoritmice, des, i acest
lucru nu este recomandat. Deoarece s, irul este indexat de la 0, presupunem că dorim să
găsim a 21052023-a cifră din acest s, ir, dar o vom considera indexată de la 1.
Init, ial, vom scrie numerele de lungime 1, care sunt 9 la număr. Astfel, putem elimina
aceste numere s, i să continuăm cu s, irul începând de la valoarea 10, presupunând că ne
interesează pozi t, ia 21052023 − 9 = 21052014. Continuând acest proces pentru lungimi mai
mari, obt, inem următoarele s, iruri:
• Avem 9 numere de lungime 1: 21052023 − 9 · 1 = 21052014.
• Avem 90 de numere de lungime 2: 21052014 − 90 · 2 = 21051834.
• Avem 900 de numere de lungime 3: 21051834 − 900 · 3 = 21049134.
• Avem 9000 de numere de lungime 4: 21049134 − 9000 · 4 = 21013134.
• Avem 90000 de numere de lungime 5: 21013134 − 90000 · 5 = 20563134.
• Avem 900000 de numere de lungime 6: 20563134 − 900000 · 6 = 15163134.
Când luăm în considerare numerele de lungime 7, rezultatul devine negativ, ceea ce ne
indică faptul că cifra pe care o căutăm se află într-un număr de lungime 7. Dacă ignorăm
numerele de lungime mai mică de 7, ne interesează pozit, ia 15163134 în s, irul indexat de la 1.
Observăm că acest număr este divizibil exact cu 7. Prin urmare, cifra căutată este ultima cifră
34

Subiect și barem · pagina 35

Concursul MateInfoUB, Sect, iunea Informatic˘a
al 15163134
7 = 2166162 număr de 7 cifre. Totu s, i, acest număr reprezintă pozi t, ia în cadrul nu-
merelor de 7 cifre, iar, prin urmare, el corespunde numărului 2166162 + 999999 = 3166161
în cadrul întregului s, ir de numere. Astfel, ultima cifră este 1, care este răspunsul corect.
O altă variantă, care este mult mai sigură, este să implementăm un algoritm care să
calculeze această cifră. Avem două opt, iuni pentru a implementa logica descrisă mai sus
în cod. Prima opt, iune oferă o solut, ie cu complexitate O(1) atât în timp, cât s, i în spa t, iu,
dar este mai dificil de implementat. A doua op t, iune este să implementăm naiv folosind
concatenare de s, iruri pentru a ret, ine toate cifrele, ob t, inând astfel o solut, ie cu complexitate
O(n) în timp s, i spa t, iu, unde n este cifra căutată. Această solut, ie este mult mai u s, or de
implementat. Fragmentul de cod în limbajul C++ este următorul:
int getAns() {
string s;
int nr = 1;
while(s.length() < 21052023) {
s += to_string(nr); // convertim numărul curent la un s, ir
nr++;
}
return s[21052022] - '0'; // convertim o cifră din char în int
}
Acest algoritm ne returnează din nou cifra 1. Mai există s, i alte metode de a implementa
această problemă într-un mod naiv s, i u s, or, cum ar fi să nu concatenăm într-un s, ir s, i să
scădem lungimea numărului din pozi t, ia pe care o căutăm. Totus, i, solut, ia prezentată este
probabil cea mai scurtă s, i us, or de implementat.
În concluzie, răspunsul corect este A.
Problema 20
Uli a descoperit palindromurile s, i este foarte pasionată de ele, as, a că dores, te să calculeze
câte palindromuri sunt mai mici ca 2022. Totu s, i, după o experien t, ă traumatizantă la ora
de fizică, Uli nu mai suportă cifra 4, a s, a că dores, te să calculeze toate palindromurile între
0 (inclusiv) s, i mai mici ca 2022 care nu cont, in cifra 4. Câte astfel de palindromuri sunt?
A. 99 (CORECT) B. 100 C. 101 D. 102 E. 103
Explicat, ie:
Putem calcula răspunsul fără a ne folosi de un instrument algoritmic, analizând următoarele
cazuri distincte:
• Palindroamele de lungime 1: Acestea au structura x, unde x poate fi orice cifră
diferită de 4. Prin urmare, există 9 astfel de palindroame.
• Palindroamele de lungime 2: Acestea au structura xx, unde x este o cifră diferită de
4 s, i 0. Prin urmare, există 8 astfel de palindroame.
• Palindroamele de lungime 3: Acestea au structura xyx, unde x este o cifră diferită de
4 s, i 0, iar y este o cifră diferită de 4. În acest caz, există 8 · 9 = 72 variante.
• Palindroamele de lungime 4: Acestea au structura xyyx, unde x este fie 1, fie 2
(pentru ca numerele să fie mai mici decât 2022). Dacă x = 1, atunci y poate lua orice
valoare diferită de 4, rezultând 9 variante. Dacă x = 2, atunci y poate fi doar 0 (orice
altă valoare ar produce un număr mai mare decât 2022), rezultând 1 variantă. În
35

Subiect și barem · pagina 36

Probleme de dificultate sc˘azut˘a
total, există 9 + 1 = 10 astfel de palindroame.
În concluzie, numărul total de palindroame care respectă condit, iile este:
9 + 8 + 72 + 10 = 99.
De asemenea, putem implementa această problemă algoritmic. Este suficient să iterăm
prin fiecare valoare între 0 s, i 2022 s, i să utilizăm o func t, ie simplă pentru a verifica dacă un
număr este palindrom s, i nu cont, ine cifra 4. Următorul fragment de cod, scris în limbajul
C++, implementează această solut, ie:
bool checkInt(int n) {
int rev = 0, aux = n;
while(n) {
int c = n % 10;
if(c == 4) return false;
rev = rev * 10 + c;
n /= 10;
}
return rev == aux;
}
int getAns() {
int ans = 0;
for(int i = 0; i < 2022; i++) {
ans += checkInt(i);
}
return ans;
}
Func t, ia returnează valoarea 99, care este răspunsul corect. Prin urmare, varianta corectă
este A.
2.3 Din anul 2023
Problema 1
Considerăm numărul N = 1! + 2! + · · · + 2023!. Care este ultima cifră a numărului N?
A. 0 B. 1 C. 3 (CORECT) D. 5 E. 8
Explicat, ie:
Fiecare factorial de la 5 la 2023 va avea ultima cifră egală cu 0. Astfel trebuie doar să
calculăm primele 4 factoriale s, i să adunăm ultima cifră a fiecăruia dintre ele:
1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33 ⇒ ultima cifră este 3
Prin urmare ultima cifră a lui N este 3, deci răspunsul corect este C.
Alternativ putem folosi următorul cod în C++/Python pentru a calcula ultima cifră a lui N:
36

Subiect și barem · pagina 37

Concursul MateInfoUB, Sect, iunea Informatic˘a
// cod C++
int N = 0;
for (int i = 1; i < 2024; ++i) {
int fact = 1;
for (int j = 2; j <= i; ++j)
(fact *= j) %= 10;
(N += fact) %= 10;
}
std::cout << N << '\n';
# cod Python
N = 0
for i in range(1, 2024):
fact = 1
for j in range(2, i + 1):
fact *= j
N += fact
last_digit = N % 10
print(last_digit)
Problema 2
Un număr este puternic dacă este strict mai mare decât răsturnatul său. De exemplu, 10
s, i 21 sunt numere puternice, dar 1 s, i 34 nu sunt. Răsturnatul lui 10 este 1. Câte numere
pozitive până în 2023 (inclusiv) sunt puternice?
A. 519 B. 646 (CORECT) C. 766 D. 1258 E. 1378
Explicat, ie:
Acestă problemă se rezolvă foarte simplu prin programare. Putem itera prin toate numerele
de la 1 la 2023 s, i pentru fiecare număr verificăm dacă este mai mare decât răsturnatul său
cu ajutorul unei func t, ii. Astfel pentru a rezolva această problemă, putem folosi următorul
cod în C++/Python:
// cod C++
int invers(int x) {
int y = 0;
while (x) {
y = y * 10 + x % 10;
x /= 10;
}
return y;
}
int main() {
int cnt = 0;
for (int i = 1; i <= 2023; ++i)
if (i > invers(i))
++cnt;
std::cout << cnt << '\n';
return 0;
}
# cod Python
def inv(n):
return int(str(n)[::-1])
cnt = 0
for i in range(1, 2024):
if i > inv(i):
cnt += 1
print(cnt)
Problema 3
Matei se pregăte s, te să învet, e asiduu pentru examenul de Bacalaureat. Pentru a avea mai
multă energie, el s, i-a cumpărat 100 de doze de băutură energizantă RedDrink. Matei
preferă această băutură s, i pentru promot, ia de care poate beneficia, respectiv dacă reciclează
7 doze de aluminiu goale de RedDrink prime s, te una plină la schimb. El s, i-a făcut un plan
37

Subiect și barem · pagina 38

Probleme de dificultate sc˘azut˘a
să bea 3 doze de RedDrink pe zi (diminea t, a, la prânz s, i seara) pentru a sus t, ine un efort
mare de învă t, are. Dacă nu are 3 doze la dispozit, ie se mult, ume s, te cu 2 doze, iar dacă nu
are 2 doze la dispozit, ie se mult, ume s, te cu una. În fiecare zi când poate recicla 7 doze, Matei
î s, i ia o pauză s, i merge la reciclat. După câte zile Matei nu mai poate să bea nicio doză de
RedDrink?
A. 34 B. 37 C. 39 (CORECT) D. 41 E. 42
Explicat, ie:
Matei va putea bea timp de 33 de zile câte 3 doze pe zi, în acest timp acesta acumulează un
total de ⌊ 99
7 ⌋ = 14 doze suplimentare. Astfel, după 33 de zile, Matei va mai avea un total
de 1 + 14 = 15 doze pline s, i o singură doză goală. Acesta va mai putea bea în continuare
timp de 15
3 = 5 zile 3 doze de RedDrink pe zi. În acest timp, el va mai acumula un total de
2 doze suplimentare, astfel după aceste 38 de zile, Matei va mai avea un total de 2 doze
pline s, i 2 doze goale. El va bea băuturile rămase într-o singură zi, ne mai ob t, inând alte
doze pline. Astfel, după 39 de zile, Matei nu va mai avea nicio doză plină de RedDrink.
Prin urmare răspunsul corect este C.
Alternativ putem construii o solut, ie în C++ pentru a rezolva această problemă:
int zile = 0;
int doze = 100, doze_goale = 0;
while (doze > 0) {
++zile;
doze_goale += std::min(3, doze);
doze -= std::min(3, doze);
if (doze_goale >= 7) doze_goale -= 7, ++doze;
}
std::cout << zile << '\n';
Problema 4
Valoarea unei expresii de forma (a < b) este 1 dacă expresia este adevărată s, i 0 dacă ea este
falsă. Care este valoarea expresiei E de mai jos?
E = (123345 < 654274) + 2 ∗ (345322 < 654294) + 4 ∗ (923263 < 452284)
A. 0 B. 2 C. 3 (CORECT) D. 5 E. 6
Explicat, ie:
Selectăm fiecare inegalitate din paranteze s, i vedem dacă aceasta este adevărată sau falsă.
Ne folosim de următoarea proprietate a logaritmului:
Propozit, ie: ln(ab) = b · ln(a)
Pentru prima inegalitate avem: (123345 < 654274) vom logaritma ambele păr t, i ale inegalită t, ii
pentru a simplifica calculul, astfel obt, inem: 345 · ln 123 < 274 · ln 654. Cu ajutorul unui
calculator vedem 1660.20 < 1776.37 ceea ce este adevărat.
Similar procedăm s, i pentru celelalte două inegalităt, i, obt, inând:
(345322 < 654294) ⇒ 322 · ln 345 < 294 · ln 654 ⇒ 1881.62 < 1906.03 ⇒ adevărat
(923263 < 452284) ⇒ 263 · ln 923 < 284 · ln 452 ⇒ 1795.66 < 1736.28 ⇒ fals
38

Subiect și barem · pagina 39

Concursul MateInfoUB, Sect, iunea Informatic˘a
Prin urmare expresia E va fi egală cu 1 + 2 + 0 = 3, deci răspunsul corect este C.
Alternativ putem folosi următorul cod în Python pentru a calcula valoarea expresiei E:
print((123**345 < 654**274) + 2*(345**322 < 654**294) + 4*(923**263 < 452**284))
Problema 5
Considerăm o matrice infinită (asemenea unui ocean nemărginit) în care pătratele albe
reprezintă apă, iar pătratele negre reprezintă fâ s, ii de pământ. Mai multe fâs, ii formează o
insulă dacă se poate ajunge din orice fâs, ie din insulă în orice altă fâ s, ie din insulă mergând
fie pe orizontală, fie pe verticală pe fâ s, ii de pământ adiacente (fără a merge pe diagonale).
O insulă poate fi formată s, i dintr-o singură fâs, ie de pământ. De pe o fâs, ie dintr-o insulă
nu putem ajunge pe o altă fâ s, ie de pe altă insulă. Dimensiunea unei insule reprezintă
numărul de fâ s, ii care alcătuiesc insula. În figura de mai jos sunt 4 astfel de insule cu
dimensiunile 1, 4, 4 s, i 24.
Presupunem că pentru fiecare fâs, ie de pământ cunoas, tem dimensiunea insulei din care
face parte. Dându-se o matrice infinită în care s, tim că se află 30 de fâs, ii de pământ s, i lista
următoare sortată a dimensiunilor insulelor din care face parte fiecare fâs, ie de pământ:
1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
să se afle numărul de insule.
A. 5 B. 7 C. 11 (CORECT) D. 13 E. 15
Explicat, ie:
Avem:
• 2 fâs, ii de pământ cu dimensiunea 1
• 4 fâs, ii de pământ cu dimensiunea 2
• 12 fâs, ii de pământ cu dimensiunea 3
• 12 fâs, ii de pământ cu dimensiunea 4
Răspunsul este dat de suma insulelor împărt, ite la dimensiunea lor, din moment ce pentru
a avea o configurat, ie validă, numărul de fâs, ii va fi egal cu un multiplu al dimensiunii
insulei respective din care fâs, iile fac parte. Astfel avem:
2
1 + 4
2 + 12
3 + 12
4 = 2 + 2 + 4 + 3 = 11
Prin urmare răspunsul corect este C.
Problema 6
Matei vrea să recicleze. Are 6 obiecte pe care vrea să le arunce s, i pentru fiecare din ele s, tie
câtă sticlă, cât plastic s, i câtă hârtie cont, ine fiecare obiect. Din păcate, din motive tehnice,
trebuie să arunce fiecare obiect la exact unul din cele 3 tomberoane de reciclare selectivă.
39

Subiect și barem · pagina 40

Probleme de dificultate sc˘azut˘a
Câte unităt, i de materie primă poate recicla maxim, dacă aruncă obiectele în tomberoane în
mod optim? Materia primă reciclată este sticla aruncată la tomberonul de sticlă, plasticul
aruncat la tomberonul de plastic s, i hârtia aruncată la tomberonul de hârtie.
Cele 6 obiecte pe care le are Matei au:
• 4 unităt, i de sticlă, 5 unităt, i de plastic s, i 3 unităt, i de hârtie.
• 10 unităt, i de sticlă, 0 unităt, i de plastic s, i 5 unităt, i de hârtie.
• 3 unităt, i de sticlă, 9 unităt, i de plastic s, i 4 unităt, i de hârtie.
• 5 unităt, i de sticlă, 5 unităt, i de plastic s, i 5 unităt, i de hârtie.
• 1 unităt, i de sticlă, 2 unităt, i de plastic s, i 3 unităt, i de hârtie.
• 9 unităt, i de sticlă, 9 unităt, i de plastic s, i 8 unităt, i de hârtie.
A. 14 B. 32 C. 41 (CORECT) D. 74 E. 90
Explicat, ie:
Pentru a maximiza cantitatea de materie primă reciclată, Matei va arunca fiecare obiect la
tomberonul care con t, ine cea mai mare cantitate din materialul respectiv. Astfel, Matei va
arunca obiectele în următoarele tomberoane:
• Obiectul 1: Plastic
• Obiectul 2: Sticlă
• Obiectul 3: Plastic
• Obiectul 4: Sticlă, Plastic sau Hârtie
• Obiectul 5: Hârtie
• Obiectul 6: Sticlă sau Plastic
Astfel, Matei va recicla un total de 5 + 10 + 9 + 5 + 3 + 9 = 41 unită t, i de materie primă. Prin
urmare răspunsul corect este C.
Problema 7
Arhipelagul Fort Leon este format din 14 insule, majoritatea locuitorilor fiind programatori
începători. Într-o zi cu soare, locuitorii arhipelagului s-au gândit că le-ar plăcea foarte
mult să construiască mai multe poduri între insule astfel încât să poate pleca de pe orice
insulă, să treacă o singură dată pe fiecare pod s, i să ajungă tot pe insula de unde au plecat.
Pentru a- s, i îndeplini mai repede dorint, a, ei au scris un program care să-i ajute. Din păcate,
ei au scris un program gres, it, care le-a furnizat următoarea modalitate de construire a
unor poduri între cele 14 insule:
Deoarece sunt foarte nerăbdători, locuitorii din Fort Leon vă roagă să-i ajutat, i, precizându-
le numărul minim de poduri pe care trebuie să le adauge la cele deja indicate de programul
scris de ei, astfel încât să-s, i îndeplinească dorint, a.
A. 3 B. 4 C. 5 D. 6 (CORECT) E. 7
40

Subiect și barem · pagina 41

Concursul MateInfoUB, Sect, iunea Informatic˘a
Explicat, ie:
Putem observa cum în poză toate componentele sunt complete, anume toate insulele din
componentă sunt conectate între ele două câte două, formând un total de 4 componente
conexe. Astfel din cerint, a problemei reiese că va trebuii să unim cele 4 componente
conexe într-un singur graf conex, astfel încât acesta să fie Eulerian. Ne aducem aminte de
următoarea teoremă:
Teorem˘a— Euler 1736. Un graf conex este Eulerian dacă s, i numai dacă are toate vârfurile
de grad par.
Astfel, pentru a transforma graful dat într-un graf Eulerian, va trebui să adăugăm un
număr minim de poduri astfel încât toate vârfurile să aibă grad par. În cazul nostru, avem:
(2, 2, 2); (3, 3, 3, 3); (3, 3, 3, 3); (2, 2, 2)
unde în paranteze reprezentăm gradul fiecărui vârf din componentele conexe. Mai
întâi unim toate componentele conexe într-un mod favorabil anume primul nod din
prima componentă cu primul nod din a doua componentă, al doilea nod din a doua
componentă cu primul nod din a treia componentă s, i al doilea nod din a treia compo-
nentă cu primul nod din a patra componentă, pentru a ob t, ine o singură componentă conexă.
(2, 2, 2); (3, 3, 3, 3); (3, 3, 3, 3); (2, 2, 2)
Astfel obt, inem următoarele grade ale vârfurilor:
(3, 2, 2, 4, 4, 3, 3, 4, 4, 3, 3, 3, 2, 2)
Observăm că avem 6 vârfuri de grad impar, astfel va trebui să adăugăm 3 poduri mi-
nim, în ordinea indicată de culori, ce reprezintă una din variantele posibile, pentru a
ob t, ine un graf Eulerian. În total am adăugat 3 poduri pentru a unii cele 4 componente
într-una singură, s, i încă 3 poduri pentru a scăpa de vârfurile de grad impar, în total 6 poduri.
Prin urmare răspunsul corect este D.
Problema 8
Matei vrea să îs, i cumpere pungi cu bomboanele lui favorite. Are la dispozi t, ie 4 oferte,
dintre care trebuie să aleagă cel mult una, pe care o poate folosi de oricâte ori.
Ofertele sunt următoarele:
• Prima ofertă: pentru fiecare 24 pungi cumpărate, următoarele 12 sunt gratuite.
• A doua ofertă: pentru fiecare 15 pungi cumpărate, următoarele 6 sunt gratuite.
• A treia ofertă: pentru fiecare 3 pungi cumpărate, următoarea este gratuită.
• A patra ofertă: pentru fiecare 40 pungi cumpărate, următoarele 20 sunt gratuite.
Presupunând că o pungă de bomboane costă un leu, cât trebuie să plătească minim
pentru a îs, i cumpăra minim 100 pungi?
A. 25 B. 72 (CORECT) C. 75 D. 80 E. 100
Explicat, ie:
Vom analiza fiecare ofertă în parte pentru a vedea care este cea mai avantajoasă pentru
Matei.
• Prima ofertă: Pentru 24 pungi cumpărate, Matei va primi 12 gratuite. Astfel, pentru
36 de pungi va plăti doar pentru 24, deci: (⌊ 100
36 ⌋ = 2) · 24 + min{100 (mod 36) =
28, 24} = 72 lei.
41

Subiect și barem · pagina 42

Probleme de dificultate sc˘azut˘a
• A doua ofertă: Pentru 15 pungi cumpărate, Matei va primi 6 gratuite. Astfel, pentru
21 de pungi va plăti doar pentru 15, deci: (⌊ 100
21 ⌋ = 4) · 15 + min{100 (mod 21) =
16, 15} = 75 lei.
• A treia ofertă: Pentru 3 pungi cumpărate, Matei va primi 1 gratuită. Astfel, pentru 4
pungi va plăti doar pentru 3, deci: (⌊ 100
4 ⌋ = 25) · 3 + min{100 (mod 4) = 1, 3} = 75 lei.
• A patra ofertă: Pentru 40 pungi cumpărate, Matei va primi 20 gratuite. Astfel, pentru
60 de pungi va plăti doar pentru 40, deci: (⌊ 100
60 ⌋ = 1) · 40 + min{100 (mod 60) =
40, 40} = 80 lei.
Astfel, cea mai avantajoasă ofertă pentru Matei este prima, care îi va permite să cumpere
100 pungi de bomboane la pret, ul de 72 lei.
Prin urmare răspunsul corect este B.
Problema 9
Matei are bidoane de 5, 7 s, i 10 litri. Matei poate pune K litri de apă în bidoane dacă există
un număr de bidoane de 5, 7 s, i 10 litri pe care le poate alege astfel încât suma capacităt, ilor
bidoanelor alese să fie exact K. Concret, Matei poate pune K litri de apă în bidoane dacă
există a, b s, i c astfel încât 5a + 7b + 10c = K.
Care este cel mai mare număr de litri de apa pe care nu îl poate pune în bidoane?
A. 13 B. 17 C. 23 (CORECT) D. 26 E. 27
Explicat, ie:
O primă Observa t, ie este că bidoanele de 10 litrii nu sunt necesare pentru a rezolva această
problemă, deoarece putem ob t, ine orice multiplu de 10 litrii folosind doar bidoanele de 5.
Astfel putem reduce formula la 5a + 7b = K, unde a s, i b sunt numere întregi.
Este important să remarcăm că odată ce putem forma 5 numere întregi consecutive, putem
forma orice număr întreg de la acel moment înainte. Astfel vom itera manual numerele pe
care le putem forma folosind bidoanele de 5 s, i 7:
5 format din 1 × 5 + 0 × 7 7 format din 0 × 5 + 1 × 7
10 format din 2 × 5 + 0 × 7 12 format din 1 × 5 + 1 × 7
14 format din 0 × 5 + 2 × 7 15 format din 3 × 5 + 0 × 7
17 format din 2 × 5 + 1 × 7 19 format din 1 × 5 + 2 × 7
20 format din 4 × 5 + 0 × 7 21 format din 0 × 5 + 3 × 7
22 format din 3 × 5 + 1 × 7 24 format din 2 × 5 + 2 × 7
25 format din 5 × 5 + 0 × 7 26 format din 1 × 5 + 3 × 7
27 format din 4 × 5 + 1 × 7 28 format din 0 × 5 + 4 × 7
Am ajuns să formăm 5 numere întregi consecutive: 24, 25, 26, 27, 28, de aici putem aduna 5
la fiecare număr s, i putem obt, ine:
24 25 26 27 28 | + 5
29 30 31 32 33 | + 5
29 30 31 32 33 | + 5
34 35 36 37 38 | + 5
39 40 41 42 43 | + 5
... ... ... ... ...
Prin urmare, cel mai mare număr de litri de apă pe care nu îl poate pune în bidoane este
23, deci răspunsul corect este C.
O altă variantă matematică, este folosind numerele lui Frobenius.
42

Subiect și barem · pagina 43

Concursul MateInfoUB, Sect, iunea Informatic˘a
Teorem˘a— Frobenius, n = 2. Pentru două numere întregi pozitive s, i prime între ele, n
s, i m, cea mai mare sumă care nu poate fi exprimată ca o combina t, ie liniară pozitivă a
acestora este determinată de m × n − m − n.
Astfel pentru n = 5 s, i m = 7 avem: 5 × 7 − 5 − 7 = 23.
Problema 10
Netty este foarte preocupată de siguran t, a datelor din PC-urile aflate în firma sa, a s, a că
s-a gândit să interconecteze PC-urile pentru a realiza rapid s, i sigur backup-ul datelor.
Deoarece nu s, tie exact cum trebuie să interconecteze PC-urile, Netty a apelat la un
oracol apa s, care i-a sugerat mai multe configurat, ii magice. Deoarece oracolul era foarte
grăbit, acesta i-a spus, în fiecare configura t, ie, doar numărul PC-urilor cu care trebuie
interconectate fiecare PC din firmă. De exemplu, configura t, ia (2, 3, 1, 2) înseamnă că
un PC trebuie interconectat cu alte două PC-uri, alt PC trebuie interconectat cu 3 PC-uri
s, .a.m.d. Unele dintre configura t, iile respective sunt realizabile (de exemplu, configurat, ia
men t, ionată anterior), iar altele nu (de exemplu, configurat, ia (3, 2, 3)). S, tiind că oracolul
apas, i-a sugerat lui Netty configurat, iile magice
C1 = (5, 2, 6, 4, 3, 4, 2, 2, 1, 1),
C2 = (5, 1, 1, 4, 4, 3, 5, 2, 2, 2),
C3 = (6, 4, 4, 3, 9, 2, 2, 2, 1, 1),
C4 = (6, 2, 6, 2, 6, 2, 6, 2, 8, 2),
C5 = (7, 6, 7, 3, 3, 2, 2, 2, 4, 4),
ajutat, i-o pe Netty, determinând numărul de configurat, ii realizabile din cele 5 precizate!
A. 0 B. 1 C. 2 D. 3 (CORECT) E. 4
Explicat, ie:
Probleme se reduce în a afla pentru o configurat, ie de grade ale unor noduri (PC-uri)
dacă un graf neorientat simplu (o ret, ea de PC-uri) poate fi construit astfel încât, nodurile
grafului să respecte configurat, ia de grade dată.
Pentru a rezolva această problemă, putem folosi următoarea teoremă:
Teorem˘a— Erd˝os-Gallai. O secvent, ă de numere întregi pozitive d1 ≥ d2 ≥ · · · ≥ dn poate
fi secvent, a de grade ale unui graf simplu neorientat dacă s, i numai dacă:
1. ∑n
i=1 di este un număr par.
2. ∑k
i=1 di ≤ k(k − 1) + ∑n
i=k+1 min{di, k} pentru fiecare k = 1, 2, . . . , n.
Vom sorta listele date s, i vom verifica pentru fiecare configurat, ie dacă aceasta respectă
teorema lui Erdős-Gallai.
• Configurat, ia C1: (5, 2, 6, 4, 3, 4, 2, 2, 1, 1)
Sortată descrescător devine: (6, 5, 4, 4, 3, 2, 2, 2, 1, 1), suma totală este 30, s, i nu există
niciun k pentru care să nu se respecte teorema lui Erdős-Gallai.
• Configurat, ia C2: (5, 1, 1, 4, 4, 3, 5, 2, 2, 2)
Sortată descrescător devine: (5, 5, 4, 4, 3, 2, 2, 2, 1, 1), suma totală este 29, deci nu se
respectă prima condit, ie a teoremei.
• Configurat, ia C3: (6, 4, 4, 3, 9, 2, 2, 2, 1, 1)
Sortată descrescător devine: (9, 6, 4, 4, 3, 2, 2, 2, 1, 1), suma totală este 34, s, i nu există
niciun k pentru care să nu se respecte teorema.
• Configurat, ia C4: (6, 2, 6, 2, 6, 2, 6, 2, 8, 2)
Sortată descrescător devine: (8, 6, 6, 6, 6, 2, 2, 2, 2, 2), suma totală este 42, s, i există
k = 5 pentru care să nu se respecte teorema, 8 + 4 × 6 = 32 > 5 × 4 + 5 × 2 = 30.
43

Subiect și barem · pagina 44

Probleme de dificultate sc˘azut˘a
• Configurat, ia C5: (7, 6, 7, 3, 3, 2, 2, 2, 4, 4)
Sortată descrescător devine: (7, 7, 6, 4, 4, 3, 3, 2, 2, 2), suma totală este 40, s, i nu există
niciun k pentru care să nu se respecte teorema.
Astfel, din cele 5 configurat, ii, doar 3 sunt realizabile, deci răspunsul corect este C.
Putem folosi următorul cod în C++, pentru a verifica dacă o configurat, ie este realizabilă,
pentru a us, ura munca:
std::vector <std::vector <int>> configuratii = {
{5, 2, 6, 4, 3, 4, 2, 2, 1, 1},
{5, 1, 1, 4, 4, 3, 5, 2, 2, 2},
{6, 4, 4, 3, 9, 2, 2, 2, 1, 1},
{6, 2, 6, 2, 6, 2, 6, 2, 8, 2},
{7, 6, 7, 3, 3, 2, 2, 2, 4, 4}
};
int res = 0;
for (std::vector <int> grade : configuratii) {
std::sort(grade.rbegin(), grade.rend());
int sum = 0;
for (int i = 0; i < 10; ++i)
sum += grade[i];
if (sum % 2) {
continue;
}
bool ok = true;
for (int i = 1; i <= 10; ++i) {
int cc = 0, ss = 0;
for (int j = 0; j < i; ++j) cc += grade[j];
for (int j = i; j < 10; ++j) ss += std::min(grade[j], i);
if (cc > i * (i - 1) + ss) {
ok = false;
break;
}
}
res += ok;
}
std::cout << res << '\n';
Alternativ se mai poate folosi s, i teorema lui Havel-Hakimi pentru a verifica dacă o secvent, ă
de grade este realizabilă.
44

Subiect și barem · pagina 45

Concursul MateInfoUB, Sect, iunea Informatic˘a
2.4 Din anul 2024
Problema 1
Se dă următoarea hartă:
Harta reprezintă un râu (albastru), două maluri, s, i patru insule (verde), precum s, i opt
poduri (negru).
Care este numărul minim de poduri ce trebuie construite astfel încât un turist să poată
traversa toate podurile exact o dată?
Atent, ie: turistul îs, i poate începe traseul oriunde dore s, te (pe un mal sau pe o insulă) s, i, de
asemenea, poate termina traseul oriunde dores, te.
A. 0 B. 1 (CORECT) C. 2 D. 3 E. 4
Explicat, ie:
Imaginii prezentate îi putem asocia următorul graf (malurile s, i insulele sunt reprezentate
de noduri, iar podurile de muchii):
Acum, problema init, ială se reduce la găsirea numărului minim de muchii care trebuie
adăugate în acest graf pentru a avea un lant, eulerian.
45

Subiect și barem · pagina 46

Probleme de dificultate sc˘azut˘a
Teorem˘a Pentru ca un graf să cont, ină un lant, eulerian, gradul fiecărui nod trebuie să fie
par, cu excep t, ia a două noduri care au gradul impar s, i care reprezintă capetele lan t, ului.
Gradele nodurilor sunt următoarele: g1 = 3, g2 = 3, g3 = 3, g4 = 3, g5 = 2, g6 = 2. Conform
teoremei de mai sus, graful actual nu cont, ine un lant, eulerian.
Observăm că avem 4 noduri cu grad impar s, i 2 cu grad par. Mai mult, muchia (2, 4)
este singura din subgraful format de nodurile 1, 2, 3, 4 care nu apare. Prin adăugarea ei,
gradele nodurilor devin: g1 = 3, g2 = 4, g3 = 3, g4 = 4, g5 = 2, g6 = 2.
As, adar, conform teoremei de mai sus, graful rezultat prin adăugarea muchiei (2, 4)
este eulerian. Prin urmare, răspunsul este 1.
Problema 2
Se dă următoarea secvent, ă de cod:
int n = 3;
for (int i = 0; i < n; i--) {
cout << '$';
}
Care dintre următoarele modificări va face ca programul să afi s, eze exact de 3 ori caracterul
dolar (i.e., „$$$”)?
1. Înlocuim "n = 3" cu "n = -3"
2. Înlocuim "int i = 0" cu "long i = 0"
3. Înlocuim "i < n" cu "-i < n"
4. Înlocuim "i < n" cu "i + n"
5. Înlocuim "i–" cu "n–"
6. Înlocuim "cout « ’$’" cu ‘cout « "$$$"‘
A. 1, 2 si 3. B. 2, 3 si 4. C. 3, 4 si 5. (CORECT) D. 3, 5 si 6. E. 1, 3 si 6.
Explicat, ie:
Codul dat în enun t, ul problemei rulează la infinit, deoarece i scade, iar condi t, ia din
instruc t, iunea for este una care îl limitează pe i superior (n fiind pozitiv). Analizăm
modificările pe rând:
1. înlocuim ”n = 3” cu ”n = −3” - codul rezultat nu va afis, a nimic, deoarece condit, ia
este respectată doar pentru valori ale lui i strict mai mici decât −3.
2. înlocuim ”int i = 0” cu ”long i = 0” - în limbajul C/C + + tipurile int s, i long sunt
amândouă pentru întregi pe 32 de bit, i. Prin urmare, această modificare nu rezolvă
problema pe care o are codul din enunt, .
3. înlocuim ”i < n” cu ”−i < n” - această modificare este echivalentă cu înlocuirea lui
”i − −” în ”i + +”. Deci, după aplicarea ei, programul va afis, a ”$$$”
4. înlocuim ”i < n” cu ”i + n” - aici i va scădea până când i + n = 0 ⇔ i = −n ⇔ i = −3.
Deci, după aplicarea ei, programul va afis, a ”$$$”
5. înlocuim ′i − −‘ cu ′n − −‘ - i rămâne mereu la valoarea 0, deci condi t, ia va fi respectată
până când n = 0. Deci, după aplicarea modificării, programul va afis, a ”$$$”
6. înlocuim ”cout << ’$’ ” cu ”cout << ’$$$’ ” - această modificare nu ne ajută, deoarece
programul va rula în continuare la infinit.
As, adar, răspunsul corect este C.
Observat, ie
Un alt mod de a rezolva problema ar fi fost să scriem codul într-un editor de C/C + + s, i să
aplicăm modificările pe rând. De s, i unele programe ar fi rulat la infinit, am fi putut să le
46

Subiect și barem · pagina 47

Concursul MateInfoUB, Sect, iunea Informatic˘a
oprim după afis, area a minim 4 simboluri $.
Problema 3
Se dă următoarea listă de cuvinte:
char cuvinte[10][5] = {
"mate",
"buri",
"mute",
"mese",
"cute",
"mare",
"iute",
"sute",
"sate",
"muri"
};
Două cuvinte sunt similare dacă sunt exact la o literă distant, ă (adică se poate schimba
exact o literă din primul cuvânt astfel încât el să devină egal cu al doilea cuvânt).
De exemplu, „abab” este similar cu „abbb”, dar „aaaa” nu este similar cu „aabb” s, i, de
asemenea, „aaaa” nu este similar cu „aaaa”.
Câte perechi neordonate (perechea (a, b) este considerată egală cu perechea (b, a)) de
cuvinte similare există?
A. 3 B. 7 C. 11 (CORECT) D. 15 E. 19
Explicat, ie:
Putem rezolva problema în două feluri: fie comparând cuvintele pe hârtie, fie scriind un
program care să rezolve cerint, a. În continuare, vom alege a doua abordare, deoarece este
mai rapidă. O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int main()
{
char cuvinte[10][5] = {
"mate",
"buri",
"mute",
"mese",
"cute",
"mare",
"iute",
"sute",
"sate",
"muri"
};
int ans;
for (int i = 0; i < 10; i++)
for (int j = i + 1; j < 10; j++)
{
int no_diff = 0;
for (int k = 0; k < 4; k++)
if (cuvinte[i][k] != cuvinte[j][k])
47

Subiect și barem · pagina 48

Probleme de dificultate sc˘azut˘a
no_diff++;
if (no_diff == 1)
ans++;
}
cout << ans;
return 0;
}
As, adar, răspunsul corect este C.
Problema 4
Cât, i arbori part, iali de cost minim are următorul graf?
A. 6 B. 5 C. 7 (CORECT) D. 3 E. 9
Explicat, ie:
Observăm că în orice arbore par t, ial de cost minim vor apărea ambele muchii de cost 1.
Prin urmare, numărul de arbori part, iali de cost minim va fi determinat de numărul de
moduri în care putem alege muchiile de cost 2.
Pentru a forma un arbore part, ial la un graf cu 6 noduri, avem nevoie de 5 muchii. Cum
avem deja 2 muchii de cost 1, mai trebuie să alegem 3 muchii de cost 2.
Numărul de posibilităt, i de a alege 3 muchii de cost 2 din totalul de 5 este: C5
3 = 5!
3!·2! =
4·5
2 = 10.
Totu s, i, nu putem alege oricum aceste 3 muchii, deoarece graful rezultat trebuie să fie
un arbore. Toate alegerile care cont, in perechile (2, 5), (3, 6) nu sunt valide. Acestea fiind în
număr de 3, putem deduce că numărul total de arbori part, iale este de 7.
Observat, ie:
Putem rezolva problema folosind s, i o abordare teoretică, precum cea explicată aici.
Problema 5
Alexandrina, fiind pasionată de transport public, a cumpărat 1 milion de bilete de auto-
buz, având coduri distincte între ele, formate din exact 6 cifre. Un bilet este considerat
norocos dacă suma primelor 3 cifre ale sale este egală cu suma ultimelor 3. De exemplu, bi-
letul cu codul 000013 are suma primelor 3 cifre egală cu 0 s, i suma ultimelor 3 cifre egală cu 4.
Ajutat, i-o pe Alexandrina să numere câte bilete norocoase det, ine!
A. 50412 B. 55252 (CORECT) C. 57823 D. 49575 E. 45198
48

Subiect și barem · pagina 49

Concursul MateInfoUB, Sect, iunea Informatic˘a
Explicat, ie:
Cel mai simplu mod de rezolvare al acestei probleme se bazează pe scrierea unui cod în
C + + în care să verificăm pentru fiecare număr de la 000000 la 999999 dacă suma primelor
3 cifre este egală cu suma ultimelor 3. Observăm că pentru a testa toate aceste numere
putem de fapt să fixăm toate perechile ordonate de numere de cel mult 3 cifre, unde primul
număr reprezintă primele 3 cifre, iar următorul ultimele 3 cifre. O implementare a solut, iei
descrise mai sus în limbajul C++ este următoarea:
int main()
{
int ans = 0;
for (int n1 = 0; n1 <= 999; n1++)
for (int n2 = 0; n2 <= 999; n2++)
if (n1 % 10 + n1 / 10 % 10 + n1 / 100 ==
n2 % 10 + n2 / 10 % 10 + n2 / 100)
ans++;
cout << ans;
return 0;
}
Problema 6
Marius i-a cumpărat fetit, ei sale, Luna, un calculator de jucărie.
În mod curios, acest calculator are un procesor care func t, ionează pe 10 bi t, i. O varia-
bilă de tip număr real păstrează valoarea sa în următorul format: m × 2−e, unde m s, i e
sunt numere naturale a căror reprezentare binară este păstrată în variabilă. Mai exact,
primii 3 bi t, i semnificativi reprezintă valoarea lui e, iar următorii 7 reprezintă valoarea lui m.
De exemplu, variabila x dată prin secvent, a de bi t, i 1010101010 reprezintă numărul:
(32 + 8 + 2) × 2−5 = 1.3125.
Marius îi dă următoarea temă Lunei: Care este cea mai mică valoare nenulă care poate fi
reprezentată de o variabilă în noua ei jucărie? O putet, i ajuta?
A. 0.001 B. 0.0078125 (CORECT) C. 0.00390625 D. 0.005859375 E. 0.015625
Explicat, ie:
Putem rezolva problema atât matematic, cât s, i scriind un program de tip backtracking în
care să testăm toate numerele. Cu toate acestea, în cadrul celei de-a doua abordări pot
apărea probleme de precizie, deci vom prefera prima variantă.
Pentru a determina cel mai mic număr pe care îl putem forma, ne dorim ca m să fie
cât mai mic s, i e cât mai mare. Astfel, vom lua m = 0000001 s, i e = 111. Numărul va fi
1 × 2−7 = 2−7 = 0.0078125.
Problema 7
La ora de design hardware, Teo inventează o tastatură circulară care cont, ine cifrele de la 0
la 9 în ordine crescătoare s, i un ac care indică către una dintre ele.
Această tastatură poate efectua de oricâte ori una dintre următoarele două operat, ii:
1. Să scrie pe ecran o dată cifra către care indică acul.
49

Subiect și barem · pagina 50

Probleme de dificultate sc˘azut˘a
2. Să mute acul pe pozit, ia succesoare (dacă acul arată către 0, va fi mutat către cifra 1;
dacă arată către 9, va fi mutat către cifra 0).
Init, ial, acul arată către cifra 0. Care este numărul minim de operat, ii necesare pentru a scrie
pe ecran numărul 11052024?
A. 41 B. 42 (CORECT) C. 43 D. 44 E. 45
Explicat, ie:
Dacă în momentul actual suntem la cifra x s, i vrem să ajungem la cifra y cu un număr
minim de opera t, ii vom muta arcul până când ajungem prima dată la cifra y. Dacă x ≤ y
atunci numărul de operat, ii este y − x pentru a ajunge pe y, iar dacă y < x atunci numărul
de opera t, ii este 9 − x + y + 1. Pe lângă acestea mai este nevoie de încă o opera t, ie pentru a
scrie cifra y.
Pentru a scrie pe ecran numărul 11052024 avem nevoie de:
• de la pozit, ia 0 la pozit, ia 1 facem 1 − 0 = 1 operat, ie
• de la pozit, ia 1 la pozit, ia 1 facem 1 − 1 = 0 operat, ii
• de la pozit, ia 1 la pozit, ia 0 facem 9 − 1 + 0 + 1 = 9 operat, ii
• de la pozit, ia 0 la pozit, ia 5 facem 5 − 0 = 5 operat, ii
• de la pozit, ia 5 la pozit, ia 2 facem 9 − 5 + 2 + 1 = 7 operat, ii
• de la pozit, ia 2 la pozit, ia 0 facem 9 − 2 + 0 + 1 = 8 operat, ii
• de la pozit, ia 0 la pozit, ia 2 facem 2 − 0 = 2 operat, ii
• de la pozit, ia 2 la pozit, ia 4 facem 4 − 2 = 2 operat, ii
În total avem 1 + 0 + 9 + 5 + 7 + 8 + 2 + 2 = 34 de opera t, ii de tipul 2, la care se adaugă
opera t, iile de tipul 1, care sunt în număr de 8. Prin urmare, numărul minim de opera t, ii
necesare pntru a scrie pe ecran numărul 11052024 este 42.
Problema 8
În datacenter-ul UniBuc, un server A de calcul s, tiint, ific porne s, te o conexiune către un
serviciu extern o dată la 17 secunde. Un alt server B pornes, te câte o conexiune o dată la
21 secunde. Alexandru, noul tehnician-s, ef al datacenter-ului, a făcut un program care
monitorizează numărul de conexiuni pornite la orice moment de timp. S, tiind că fiecare
conexiune rămâne deschisă exact 5 minute de la pornire, care este numărul maxim de
conexiuni care pot exista simultan?
A. 29 B. 30 C. 31 D. 32 E. 33 (CORECT)
Explicat, ie:
Putem calcula independent numărul maxim de conexiuni pornite de server-ul A s, i numărul
maxim de conexiuni pornite de server-ul B. Pentru calcul este de ajuns să ne raportăm la
ce se întâmplă pe intervalul de timp format de primele 5 minute.
La secunda 0 server-ul A deschide prima conexiune, apoi la secunda 17 a doua, · · · , la
secunda 172 = 289 deschide a 18-a conexiune.
La secunda 0 server-ul B deschide prima conexiune, apoi la secunda 21 a doua, · · · , la
secunda 21 · 14 = 294 deschide a 15-a conexiune.
As, adar, numărul maxim de conexiuni care pot exista simultan este de 32.
Problema 9
S, tefan împreună cu cei 23 de prieteni ai săi joacă un joc de strategie. Aces, tia primesc
un ID unic în cadrul jocului, un număr din intervalul [2, N + 1], unde N este numărul de
jucători. Jucătorii formează aliant, e astfel: doi jucători sunt în aceea s, i aliant, ă dacă ID-urile
lor au acela s, i număr de divizori (de exemplu, jucătorul cu ID-ul 2 este în aceea s, i alian t, ă cu
50

Subiect și barem · pagina 51

Concursul MateInfoUB, Sect, iunea Informatic˘a
jucătorul cu ID-ul 3). Comunicarea este foarte importantă în acest joc, iar după stabilirea
alian t, elor, doar membrii acelea s, i alian t, e pot stabili conexiuni securizate bidirec t, ionale
între ei prin care comunică. Care este numărul total de conexiuni securizate ce se pot
stabili?
A. 63 (CORECT) B. 61 C. 62 D. 65 E. 64
Explicat, ie:
Cel mai simplu mod de rezolvare al acestei probleme se bazează pe scrierea unui cod în
C + + în care să verificăm pentru fiecare pereche de numere din interval dacă au acela s, i
număr de divizori. O implementare a solut, iei descrise mai sus în limbajul C++ este
următoarea:
int nr_div(int n)
{
int d, ans = 0;
for (d = 1; d * d < n; d++)
if (n % d == 0)
ans += 2;
if (d * d == n)
ans++;
return ans;
}
int main()
{
int ans = 0;
for (int i = 2; i <= 24; i++)
for (int j = i + 1; j <= 25; j++)
if (nr_div(i) == nr_div(j))
ans++;
cout << ans;
return 0;
}
Observat, ie
Aten t, ie că numărul de jucători este 23 + 1 = 24, deci intervalul din care alegem ID-uri este
[2, 25]. În cazul în care nu îl considerat, i s, i pe S, tefan la numărătoare (adică căuta t, i pe lucra t, i
cu intervalul [2, 24]) vet, i obt, ine răspunsul B.
Problema 10
Mara este pasionată de numere. După ce a analizat foarte multe tipuri de numere, s, i-a dat
seama că favoritele ei sunt numerele cu toate cifrele distincte care nu con t, in cifra 0. Mara a
făcut o groază de studii pentru numerele scrise în baza 10, dar acum este curioasă ce se
întâmplă în alte baze de numera t, ie. De exemplu, pentru baza 2 s, i-a dat seama că îi place
doar un număr, iar pentru baza 3 îi plac 4 numere. Câte numere o să îi placă Marei pentru
baza 5?
A. 31 B. 68 C. 15 D. 64 (CORECT) E. 260
51

Subiect și barem · pagina 52

Probleme de dificultate sc˘azut˘a
Explicat, ie:
În baza 5 vom lucra doar cu 4 cifre nenule, de aceea numerele care au toate cifrele distincte
s, i nenule vor avea lungimea cel mult 4.
Putem aborda problema atât din punct de vedere matematic, cât s, i scriind un program
de tip backtracking care să genereze toate numerele care respectă condi t, ia s, i a afla numărul
lor. În continuare, vom prezenta prima metodă de rezolvare deoarece este mai valoroasă
s, i posibil mai rapidă.
Numărul numerelor în baza 5 de o cifră care sunt nenule este de 4, de 2 cifre distincte
s, i nenule este de 4 · 3 = 12, de 3 cifre distincte s, i nenule este de 4 · 3 · 2 = 24, iar de 4 cifre
distincte s, i nenule este de 4 · 3 · 2 · 1 = 24.
A s, adar, numărul de numere în baza 5 care au toate cifrele distincte s, i nenule este egal
cu 4 + 12 + 24 + 24 = 64.
52

Subiect și barem · pagina 53

3. Probleme de dificultate medie
3.1 Din anul 2021
Problema 1
Vă aminti t, i de Cristian cel neastâmpărat? Tatăl lui s-a hotărât să îl înve t, e pu t, ină aritmetică.
El spune că de la un număr natural x se poate ajunge la un număr natural y (y > x) trecând
prin numerele dintre ele utilizând o secven t, ă de pa s, i. Lungimea fiecărui pas este pozitivă
s, i poate fi egală cu lungimea pasului anterior, mai mare cu 1 sau mai mică cu 1. Lungimile
primului s, i ultimului pas trebuie să fie egale cu 1.
Problema dată lui Cristian este de a găsi numărul minim de pas, i prin care se poate ajunge
de la 2021 la 3110. Ce să aleagă Cristian?
A. 64 B. 65 (CORECT) C. 66 D. 67 E. 68
Explicat, ie:
Datorită condi t, ie că primul s, i ultimul pas trebuie să aibă lungimea egală cu 1 s, i a faptului
că ne dorim un număr minim de pas, i, observăm că trebuie să cres, tem lungimea pa s, ilor
până la un punct s, i apoi să o scădem. Cu men t, iunea că atât la cres, tere, cât s, i la scădere,
putem stagna la anumite valori.
Astfel, dacă lungimea maximă a unui pas va fi x, atunci vom face x pa s, i la partea de
cre s, tere, x − 1 la partea de scădere s, i eventual alt, i pa s, i pentru care s-a păstrat lungimea
realiza t, i intermediar. De asemenea, lungimea parcursă la cre s, tere este egală cu x·(x+1)
2 , iar
la scădere este (x−1)·x
2 , adunate înseamnă x·(x+1+x−1)
2 = 2x2
2 = x2.
Trebuie să parcurgem o distan t, ă totală de 3110 − 2021 = 1079. Pentru a găsi numărul
minim de pa s, i trebuie să găsim cel mai mare x pentru care x2 ≤ 1079 ⇐⇒ x ≤ √1079 ≃ 32, 84.
Deci, vom alege x = 32, cu care vom acoperi o distant, ă de 1024. Prin urmare, trebuie să mai
acoperim o distant, ă de 55 = 32 + 23. Astfel, putem să mai facem câte un pas cu valorile 32
s, i 23.
În total vom face x + (x − 1) + 2 = 32 + 31 + 2 = 65 de pas, i.
Problema 2
Primarul P. are de acoperit un perete lung de 100 m s, i înalt de 1 m, pe care vrea să îl
împânzească cu postere publicitare. În acest sens, a cumpărat 8 postere, de înălt, ime egală
53

Subiect și barem · pagina 54

Probleme de dificultate medie
cu 1 m s, i lăt, imile (exprimate în metri):
12, 27, 13, 25, 26, 38, 28, 38
El va trebui să aranjeze posterele de-a lungul peretelui. Posterele nu au voie să se suprapună
s, i nu pot depăs, i marginile peretelui. Care este aria maximă de perete pe care o poate
acoperi folosind posterele cumpărate (exprimată în m2)?
A. 93 B. 94 (CORECT) C. 95 D. 96 E. 97
Explicat, ie:
Pentru a ob t, ine aria maximă trebuie să alegem posterele astfel încât suma lungimilor lor
să fie maximă, deoarece toate au înălt, imea de 1 m.
Pentru a rezolva problema vom scrie un program C + + în care vom genera sumele
tuturor submul t, imilor, ceea ce putem face fie printr-o rezolvare de tip backtracking, fie
printr-o dinamică de tip rucsac. În continuare vom prezenta câte o rezolvare în limbajul
C++ pentru varianta backtracking s, i pentru varianta cu programare dinamică:
// cod backtracking
int main()
{
int ans = 0, no_submultimi = (1 << 8);
vector<int> lungimi = {12, 27, 13, 25, 26, 38, 28, 38};
for (int submultime = 0; submultime < no_submultimi; submultime++)
{
int sum = 0;
for (int i = 0; i < (int)lungimi.size(); i++)
if (submultime & (1 << i))
sum += lungimi[i];
if (sum > ans && sum <= 100)
ans = sum;
}
cout << ans;
return 0;
}
// cod dinamica
int main()
{
int ans = 0, n = 8, G = 100;
// adaugam un 0 pentru a indexa de la 1
vector<int> lungimi = {0, 12, 27, 13, 25, 26, 38, 28, 38};
vector<vector<bool>> dp(n + 1, vector<bool>(G + 1, false));
dp[0][0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= G; j++)
{
// nu folosim posterul i
if (dp[i - 1][j])
54

Subiect și barem · pagina 55

Concursul MateInfoUB, Sect, iunea Informatic˘a
dp[i][j] = dp[i - 1][j];
// folosim posterul i
if (j >= lungimi[i] && dp[i - 1][j - lungimi[i]])
dp[i][j] = dp[i - 1][j - lungimi[i]];
}
for (int i = 1; i <= G; i++)
if (dp[n][i])
ans = max(ans, i);
cout << ans;
return 0;
}
Problema 3
Considerăm triunghiul infinit de mai jos, format din numere naturale, în care numărul 1
se află la nivelul 1, numerele 2 s, i 3 se află la nivelul 2, numerele 4, 5 s, i 6 se află la nivelul 3
s, i as, a mai departe:
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Pentru un anumit nivel k, vrem să calculăm suma numerelor din interiorul triunghiului
care se opre s, te la nivelul k. Spre exemplu, pentru nivelul k = 5, numerele din interiorul
triunghiului creat sunt 5, 8, 9 s, i suma lor este 22. Iar pentru k = 7, numerele din interiorul
triunghiului creat sunt 5, 8, 9, 12, 13, 14, 17, 18, 19, 20 s, i suma lor este 135.
Calculat, i suma numerelor din interiorul triunghiului care se opres, te la nivelul k = 2021.
A. 2076403516157 B. 2080520640766 (CORECT) C. 2080520640767 D. 2084643884965
E. 2084643884966
Explicat, ie:
Putem rezolva problema atât matematic, cât s, i prin intermediul unui program. În
continuare alegem să prezentăm ambele solu t, ii, chiar dacă este evident că varianta în care
scriem un program pentru a calcula suma este cea care consumă mai put, in timp.
Observăm că pe linia k se vor afla k numere. Prin urmare, pe primele k linii se află
primele k·(k+1)
2 numere naturale.
Solut, ia 1
Pentru a afla suma numerelor din triunghiul interior, putem calcula suma tuturor elemen-
telor de pe primele k − 1 linii, din care să scădem suma primelor elemente de pe fiecare
rând s, i suma ultimelor elemente de pe fiecare rând, având grijă să adunăm 1, deoarece îl
scădem de 2 ori. Astfel, excludem direct ultima linie din sumă. În continuare, pentru a
lucra mai us, or cu indicii, vom considera k = 2020 (sumele care trebuiau să fie până la linia
k − 1 vor fi acum până la linia k).
55

Subiect și barem · pagina 56

Probleme de dificultate medie
Notăm elementul de pe rândul i, pozit, ia j cu Ai, j. Observăm:
• Ai,1 = Ai−1,1 + (i − 1)
• Ai,i = Ai−1,i−1 + i
Prin urmare:
k
∑
i=1
Ai,1 = 1 + (1 + 1) + (1 + 1 + 2) + (1 + 1 + 2 + 3) + · · · + (1 + 1 + 2 + · · · + (k − 1))
= k + 1 + (1 + 2) + (1 + 2 + 3) + · · · + (1 + 2 + · · · + (k − 1))
= k + ( 1 · 2
2 + 2 · 3
2 + 3 · 4
2 + · · · + (k − 1)k
2 )
= k +
k−1
∑
i=1
i(i + 1)
2 = k +
k−1
∑
i=1
i2 + i
2 = k + 1
2 (
k−1
∑
i=1
i2 +
k−1
∑
i=1
i)
= k + 1
2 ( (k − 1)k(2k − 1)
6 + (k − 1)k
2 )
= k + (k − 1)k(2k + 2)
12 = k + (k − 1)k(k + 1)
6
Similar calculăm s, i suma pentru ultimele elemente:
k
∑
i=1
Ai,i = 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + · · · + (1 + 2 + 3 + · · · + k)
= 1 · 2
2 + 2 · 3
2 + 3 · 4
2 + 4 · 5
2 + · · · + k(k + 1)
2
=
k
∑
i=1
i(i + 1)
2 =
k
∑
i=1
i2 + i
2 = 1
2 (
k−1
∑
i=1
i2 +
k−1
∑
i=1
i)
= 1
2 ( k(k + 1)(2k + 1)
6 + k(k + 1)
2 )
= k(k + 1)(2k + 4)
12 = k(k + 1)(k + 2)
6
Formula matematică descrisă mai sus este următoarea:
S =
k(k+1)
2
∑
i=1
i −
k
∑
i=1
Ai,1 −
k
∑
i=1
Ai,i + 1
=
k(k+1)
2 · ( k(k+1)
2 + 1)
2 − (k + (k − 1)k(k + 1)
6 ) − k(k + 1)(k + 2)
6 + 1
= k(k + 1) · (k(k + 1) + 2)
8 − k − (k − 1)k(k + 1)
6 − k(k + 1)(k + 2)
6 + 1
= k(k + 1) · (k(k + 1) + 2)
8 − k − k(k + 1)(k − 1 + k + 2)
6 + 1
= k(k + 1) · (k(k + 1) + 2)
8 − k − k(k + 1)(2k + 1)
6 + 1
= (2020 · 2021)(2020 · 2021 + 2)
8 − 2020 − 2020 · 2021 · 4041
6 + 1
= 505 · 2021 · 2041211 − 2019 − 1010 · 2021 · 1347
= 2080520640766
Solut, ia 2
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
56

Subiect și barem · pagina 57

Concursul MateInfoUB, Sect, iunea Informatic˘a
// matricea are o dimensiune considerabila, deci o declaram global
long long a[2022][2022];
int main()
{
// Construim matricea
long long val = 1;
for (int i = 1; i <= 2021; i++)
for (int j = 1; j <= i; j++)
{
a[i][j] = val;
val++;
}
// Calculam suma elementelor din triunghiul interior
long long ans = 0;
for (int i = 1; i <= 2020; i++)
for (int j = 2; j < i; j++)
ans += a[i][j];
cout << ans;
return 0;
}
Problema 4
Fie A o matrice binară cu 50 de linii s, i 50 de coloane (numerotate de la 1 la 50). Celula de
pe rândul i s, i coloana j cont, ine valoarea 1 dacă s, i numai dacă numărul 50 × (i − 1) + j se
divide cu 7 sau cu 13; altfel, valoarea este 0. Matricea se poate vizualiza aici (celulele albe
reprezintă pozit, iile egale cu 0, iar celulele negre, pozit, iile egale cu 1):
Vrem să plasăm un singur „domino” (piesă de mărime 1 × 2 sau 2 × 1) în matrice. Domino-
ul trebuie să acopere 2 celule vecine (pe orizontală sau verticală) de 0 ale matricei. În câte
feluri putem face acest lucru?
A. 1479 B. 1480 C. 1520 D. 2959 (CORECT) E. 3039
Explicat, ie:
Pentru a rezolva problema vom scrie un program unde să generăm matricea din enun t, .
După aceea vom parcurge fiecare linie, iar dacă două elemente alăturate au ambele valoarea
0, adunăm 1 la răspuns. Procedăm similar pentru coloane. O implementare a solu t, iei
57

Subiect și barem · pagina 58

Probleme de dificultate medie
descrise mai sus în limbajul C++ este următoarea:
int main()
{
// Construim matricea
bool a[51][51] = {};
for (int i = 1; i <= 50; i++)
for (int j = 1; j <= 50; j++)
{
int val = 50 * (i - 1) + j;
if (val % 7 == 0 || val % 13 == 0)
a[i][j] = 1;
}
int ans = 0;
// Parcurgem liniile
for (int i = 1; i <= 50; i++)
for (int j = 1; j <= 49; j++)
if (a[i][j] == 0 && a[i][j + 1] == 0)
ans++;
// Parcurgem coloanele
for (int j = 1; j <= 50; j++)
for (int i = 1; i <= 49; i++)
if (a[i][j] == 0 && a[i + 1][j] == 0)
ans++;
cout << ans;
return 0;
}
Problema 5
Considerăm următorul algoritm de acoperire a unei sume de bani, folosind bancnotele
disponibile în portofel:
Cât timp suma este neacoperită s, i avem în portofel o bancnotă de valoare mai mică sau egală cu
suma, alegem cea mai mare bancnotă de acest tip, scoatem bancnota din portofel s, i reducem suma
cu valoarea ei.
Dacă algoritmul se încheie cu suma 0, a reus, it, altfel a es, uat.
În funct, ie de configurat, ia de bancnote disponibile s, i suma de acoperit, e posibil ca acest
algoritm să nu găsească o solu t, ie, des, i ea există. Spre exemplu, dacă avem bancnotele
{1, 1, 4, 5, 6} s, i trebuie să acoperim suma S = 9, algoritmul va selecta bancnotele 6, 1, 1,
după care se va bloca, fiindcă nu mai poate acoperi suma rămasă (egală cu 1). Totu s, i,
există solut, ia {4, 5} care acoperă complet suma. Numim o astfel de pereche de bancnote
disponibile, respectiv sumă de acoperit, un contraexemplu pentru algoritmul descris.
Fie Smin cea mai mică sumă de acoperit care apare într-un contraexemplu construit doar
cu tipurile de bancnote românes, ti aflate în circulat, ie, anume: {1, 5, 10, 50, 100, 200, 500}.
58

Subiect și barem · pagina 59

Concursul MateInfoUB, Sect, iunea Informatic˘a
Fiecare tip de bancnotă poate fi folosit de oricâte ori (inclusiv deloc). Care este restul lui
Smin la împărt, irea cu 37?
A. 13 B. 3 C. 8 (CORECT) D. 18 E. 23
Explicat, ie:
Observăm că pentru un set de bancnote sortate crescător dacă pentru fiecare element
valoarea sa le divide pe toate de după el, atunci algoritmul oferă mereu o solu t, ie, dacă
aceasta există.
Prin urmare, pentru a crea un contraexemplu trebuie să vedem dacă există 2 bancnote
care să nu se dividă una pe cealaltă. Acestea 2 sunt cea de 200 s, i cea de 500.
Este evident că nu putem crea un contraexemplu cu suma mai mică decât 500, iar
pentru a crea un contraexemplu trebuie să alegem o sumă care e divizibilă cu 200. Suma
minimă care respectă ambele proprietăt, i este Smin = 600, iar setul de bancnote ales poate fi
200, 200, 200, 500. Se observă că algoritmul va alege 500 s, i va trebui după să acopere suma
100, lucru imposibil, dar totus, i există solut, ie, anume alegerea celor 3 bancnote de 200.
As, adar, mai rămâne doar să calculăm restul lui Smin la împărt, irea cu 37 s, i ob t, inem
600 ≡ 8(mod 37).
Problema 6
Câte dreptunghiuri distincte sunt în figura următoare?
A. 43 (CORECT) B. 44 C. 45 D. 46 E. 47
Explicat, ie:
Problema poate fi rezolvată atât matematic, cât s, i prin intermediului unui program. În
continuare vom prezenta prima variantă, la care vom discuta o metodă de abordare care
ar trebui să fie rapidă s, i să ne asigure faptul că nu numărăm de 2 ori acelas, i dreptunghi.
Această abordare poate fi s, i implementată, dar trebuie să construim figura de mână s, i
după aceea să avem grijă să facem verificările că un dreptunghi este valid. Pot apărea
destul de multe bug-uri sau cazuri ratate la implementare.
Considerăm că figura are 5 linii (cele care încep cu +) s, i 7 coloane (considerăm că dacă
pe o linie există un + acesta determină că în acel punct este o coloană, chiar dacă pe altă
linie este un -).
Pentru a număra dreptunghiurile, trebuie să observăm că un dreptunghi este determinat
de două linii s, i două coloane. Astfel, putem fixa oricare două linii i < j pentru care să
vedem numărul de coloane pentru care colt, urile dreptunghiului sunt conectate, atât pe
coloane cât s, i pe linie.
Avem 4 · 5/2 = 10 perechi de linii pe care le putem alege s, i pentru fiecare calculăm câte
dreptunghiuri formează în felul următor:
59

Subiect și barem · pagina 60

Probleme de dificultate medie
• i = 1, j = 2 sunt valide coloanele 1, 3, 4, 5. Perechile de coloane valide sunt (1, 3), (4, 5),
ele fiind în număr de 2.
• i = 1, j = 3 sunt valide coloanele 1, 3, 4, 5, 6. Perechile de coloane valide sunt
(1, 3), (1, 4), (1, 5), (1, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6), ele fiind în număr de 10.
• i = 1, j = 4 sunt valide coloanele 1, 4, 6, 7. Perechile de coloane valide sunt (1, 4), (1, 6),
(1, 7), (4, 6), (4, 7), (6, 7), ele fiind în număr de 6.
• i = 1, j = 5 sunt valide coloanele 1, 4, 7. Perechile de coloane valide sunt (1, 4), (1, 7), (4, 7),
ele fiind în număr de 3.
• i = 2, j = 3 sunt valide coloanele 1, 2, 3, 4, 5. Perechile de coloane valide sunt
(1, 2), (1, 3), (2, 3), (4, 5), ele fiind în număr de 4.
• i = 2, j = 4 sunt valide coloanele 1, 2, 4. Perechea de coloane (1, 2) este singura validă.
• i = 2, j = 5 sunt valide coloanele 1, 4. Totu s, i nu există nicio pereche de coloane validă.
• i = 3, j = 4 sunt valide coloanele 1, 2, 4, 6. Perechile de coloane valide sunt (1, 2), (1, 4),
(1, 6), (2, 4), (2, 6), (4, 6), ele fiind în număr de 6.
• i = 3, j = 5 sunt valide coloanele 1, 4. Perechea de coloane (1, 4) este validă.
• i = 4, j = 5 sunt valide coloanele 1, 3, 4, 5, 7. Perechile de coloane valide sunt
(1, 3), (1, 4), (1, 5), (1, 7), (3, 4), (3, 5), (3, 7), (4, 5), (4, 7), (5, 7), ele fiind în număr de 10.
În total avem 2 + 10 + 6 + 3 + 4 + 1 + 0 + 6 + 1 + 10 = 43 de dreptunghiuri.
3.2 Din anul 2022
Problema 1
În oras, ul Netville sunt 14052022 case, identificate prin numerele naturale 1, 2, . . . , 14052022.
În majoritatea caselor locuiesc student, i (sau viitori student, i) ai Facultăt, ii de Matematică s, i
Informatică, care s-au gândit să creeze o re t, ea de calculatoare folosind următoarea regulă:
casa cu numărul h (2 ≤ h ≤ 14052022) va fi interconectată cu toate casele al căror număr d
este un divizor al lui h (1 ≤ d < h). De exemplu, casa cu numărul 10 va fi interconectată cu
casele cu numerele 1, 2, 5, 20, 30, . . . , 14052020.
Numărul de conexiuni care trebuie realizate între toate cele 14052022 case este egal cu: ?
A. 233442104 B. 226416093 C. 219390082 (CORECT) D. 205338061 E. 248511938
Explicat, ie:
Vom nota numărul 14052022 cu n. Deoarece numărul n este destul de mare, este imposibil
să aflăm rezultatul fără a ne folosi de un instrument algoritmic. Prin urmare, va fi necesar
să scriem cod pentru această problemă.
Pentru început, avem mai multe op t, iuni. Prima s, i cea naivă este de a număra câ t, i divizori
au toate numerele de la 1 la n. Deoarece calculul divizorilor unui număr are complexitatea
O(√n), complexitatea totală a acestui algoritm va fi O(n√n), ceea ce înseamnă că va rula în
câteva zeci de secunde. O implementare în limbajul C++ este următoarea:
int getAns() {
int n = 14052022, ans = 0;
for(int i = 2; i <= n; i++) {
ans++;
for(int j = 2; j * j <= i; j++) {
if(i % j == 0) {
ans++;
if(i / j != j) ans++;
60

Subiect și barem · pagina 61

Concursul MateInfoUB, Sect, iunea Informatic˘a
}
}
}
return ans;
}
În funct, ia getAns(), iterăm prin toate numerele i de la 2 la n, apoi, pentru fiecare, îi
numărăm divizorii. Deoarece nu vrem să îl numărăm pe n însu s, i, îl numărăm pe 1 separat,
apoi iterăm de la 1 la √i. Când găsim un divizor j, îl numărăm s, i verificăm dacă i/ j,
care este tot un divizor, este diferit de i, dacă da, îl numărăm s, i pe acesta. Astfel, evităm
numărarea dublă în cazul pătratelor perfecte. Funct, ia returnează valoarea 219390082, care
este s, i răspunsul.
O altă metodă, mai eficientă, este să observăm că numărul divizorilor numerelor de la 1 la
n este acela s, i cu numărul multiplilor numerelor de la 1 la n, care sunt mai mici decât n s, i
diferi t, i de numerele în sine. Acest lucru este o consecin t, ă a faptului că un număr este un
multiplu al divizorilor săi, iar numărul multiplilor unui număr x mai mici decât n este
egal cu n/x. Astfel, putem calcula rezultatul în O(n). O implementare în limbajul C++ este
următoarea:
int getAns() {
int n = 14052022, ans = 0;
for(int i = 1; i <= n; i++) {
ans += n / i - 1;
}
return ans;
}
Aici, în func t, ia getAns(), iterăm prin fiecare număr de la 1 la n s, i numărăm cât, i multipli
are mai mici decât n, apoi scădem 1 pentru a exclude numărul în sine. Func t, ia returnează
219390082, care este răspunsul corect. Prin urmare, varianta C este corectă.
Problema 2
Alex joacă un joc. Init, ial, acesta se află lipit cu spatele de perete. La fiecare pas, poate să
facă un salt în fat, ă sau în spate, de lungime egală cu 2k unită t, i, unde k ≥ 0. Pentru a evita
accidente, Alex nu va efectua saltul în spate dacă pozi t, ia rezultată va fi mai mică decât 0.
Care este numărul minim de salturi necesare lui Alex pentru a ajunge la pozi t, ia 1340291?
A. 7 B. 8 (CORECT) C. 9 D. 10 E. 11
Explicat, ie:
Pentru început, vom men t, iona că atâta timp cât pozi t, ia finală este mai mare decât 0, chiar
dacă vom efectua salturi înapoi, există o ordine a acestor salturi astfel încât să nu ajungem
pe o pozi t, ie mai mică decât 0. Deoarece putem mereu să efectuăm salturile înainte primele,
vom ignora complet condit, ia zidului.
Vom nota n = 1340291 s, i îl vom scrie pe n ca sumă de puteri ale lui 2, astfel obt, inem:
n = 220 + 218 + 214 + 213 + 212 + 29 + 28 + 27 + 21 + 20
Acum vom considera un s, ir de puteri de 2 consecutive:
2x + 2(x+1) + 2x + 2 + · · · + 2(x+n) = 2(x+n+1) − 2x
61

Subiect și barem · pagina 62

Probleme de dificultate medie
Astfel, observăm că pentru un s, ir consecutiv de n puteri ale lui 2, le putem scrie mereu
cu doar 2 puteri ale lui 2 s, i o operat, ie de scădere. Acest lucru este echivalent cu faptul
că putem scrie orice s, ir de n salturi cu valori ale lui k consecutive un salt înainte s, i unul
înapoi.
Observăm că în scrierea lui n avem 2 s, iruri consecutive de lungime 3. Aplicând ideea de
mai sus, putem să-l scriem pe n în felul următor:
n = 220 + 218 + 215 − 212 + 210 − 27 + 21 + 20
Secven t, a obt, inută nu mai poate fi îmbunătăt, ită. Astfel, obt, inem următoarea secvent, ă de
salturi:
• Un salt cu k = 20 înainte
• Un salt cu k = 18 înainte
• Un salt cu k = 15 înainte
• Un salt cu k = 12 înapoi
• Un salt cu k = 10 înainte
• Un salt cu k = 7 înapoi
• Un salt cu k = 1 înainte
• Un salt cu k = 0 înainte
În concluzie, avem nevoie de 8 salturi pentru a ajunge la pozit, ia n. Prin urmare, răspunsul
corect este B.
Problema 3
Care este numărul minim de pătrate perfecte necesar astfel încât suma acestora să fie 2022?
De exemplu:
• 2 = 12 + 12, deci răspunsul pentru 2 este 2.
• 10 = 32 + 12, deci răspunsul pentru 10 este tot 2.
• 100 = 102, deci răspunsul pentru 100 este 1.
• 18 = 32 + 32, deci răspunsul pentru 18 este 2.
A. 2 B. 3 (CORECT) C. 4 D. 5 E. 6
Explicat, ie:
Pentru început, nu avem o metodă bună de a rezolva problema fără a scrie un fragment de
cod. În schimb, putem rezolva problema folosind programare dinamică, mai specific un
algoritm asemănător cu problema sumei submult, imilor. Mai concret, definim d p(i, j) ca
fiind numărul minim de pătrate perfecte necesare pentru a forma suma j, folosind doar
primele i pătrate perfecte. Init, ial, avem d p(0, 0) = 0, iar tranzit, iile sunt următoarele:
d p(i, j) =
(
min{d p(i − 1, j), d p(i, j − i2) + 1} dacă j ≥ i2,
d p(i − 1, j) altfel.
În prima tranzit, ie, creăm noi solut, ii adăugând i2 la cele anterioare, iar în a doua, copiem
solu t, iile obt, inute anterior. De observat este faptul că, deoarece tranzact, ionăm de la i, nu
de la i − 1, putem folosi valoarea i2 de mai multe ori. O implementare în limbajul C++ este
următoarea:
62

Subiect și barem · pagina 63

Concursul MateInfoUB, Sect, iunea Informatic˘a
int getAns() {
int n = 2022;
int dp[50][2025];
for(int i = 0; i <= 44; i++) {
for(int j = 0; j <= 2022; j++) {
dp[i][j] = 1e9;
}
}
dp[0][0] = 0;
for(int i = 1; i * i <= 2022; i++) {
for(int j = 0; j <= 2022; j++) {
dp[i][j] = dp[i - 1][j];
if(j >= i * i) dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
}
}
return dp[44][2022];
}
În funct, ia getAns(), setăm valorile lui d p(i, j) foarte mari pentru a nu ne încurca, apoi
ini t, ializăm d p(0, 0). De observat este că nu avem nevoie decât de primele 44 pătrate
perfecte, deoarece 452 = 2025 > 2022 s, i nu ne ajută cu nimic. Apoi, construim solut, ia
folosind tranzi t, iile de mai sus s, i returnăm d p(44, 2022). Func t, ia returnează valoarea 3, care
este s, i răspunsul corect. Complexitatea de timp s, i spa t, iu este O(n√n), unde n este valoarea
pe care vrem să o construim folosind pătratele perfecte. De asemenea, complexitatea de
spa t, iu poate fi îmbunătă t, ită la O(n), deoarece nu avem nevoie să copiem în mod constant
linia anterioară, ci putem scrie direct peste ea.
De asemenea, există destul de multe variante de a scrie 2022 ca sumă de trei pătrate
perfecte, una fiind 2022 = 432 + 132 + 22. Din câteva încercări cu calculatorul, ar trebui
să găsim o solu t, ie formată din trei pătrate perfecte. De asemenea, devine evident că nu
există o solut, ie formată din doar două pătrate perfecte. Astfel, prin eliminare, ajungem la
concluzia că varianta B este cea corectă. De s, i nu este o metodă de rezolvare riguroasă,
valoarea 2022 ne permite să găsim solut, ia prin încercări succesive.
Concluzie: Varianta B este cea corectă.
Problema 4
Pe masă se află trei zaruri. Pe fiecare dintre cele s, ase fe t, e ale zarurilor este inscript, ionată
câte o cifră:
• Z1 : [1, 3, 2, 4, 5, 7]
• Z2 : [1, 7, 6, 2, 1, 5]
• Z3 : [7, 9, 8, 2, 4, 2]
Spunem că un număr de trei cifre se poate forma folosind zarurile dacă putem aranja cele
trei zaruri pe masă astfel încât fe t, ele de sus să descrie acel număr. De exemplu, putem
forma numărul 562 folosind zarurile Z1, Z2, Z3 (în această ordine).
Câte numere distincte de trei cifre se pot forma cu cele trei zaruri?
A. 125 B. 317 C. 499 D. 521 (CORECT) E. 729
63

Subiect și barem · pagina 64

Probleme de dificultate medie
Explicat, ie:
Pentru început, observăm că este foarte dificil să contorizăm câte numere putem forma
fără a ne folosi de un instrument algoritmic, prin urmare, vom scrie un scurt fragment de
cod pentru a rezolva problema. În continuare, vom considera următorul algoritm: vom
ini t, ializa trei vectori cu valorile celor trei zaruri, apoi iterăm prin toate cele trei, selectând
câte o cifră din fiecare vector. Apoi, este suficient doar să considerăm toate cele 6 permutări
ale celor 3 cifre s, i vom t, ine un vector caracteristic pentru a marca dacă putem forma un
număr. O implementare în limbajul C++ este următoarea:
int getAns() {
int Z1[] = {1, 3, 2, 4, 5, 7};
int Z2[] = {1, 7, 6, 2, 1, 5};
int Z3[] = {7, 9, 8, 2, 4, 2};
int fr[1000] = {0};
for(int i = 0; i < 6; i++) {
for(int j = 0; j < 6; j++) {
for(int k = 0; k < 6; k++) {
int a = Z1[i], b = Z2[j], c = Z3[k];
int val = a * 100 + b * 10 + c; //permutarea 1, 2, 3;
fr[val] = 1;
val = a * 100 + c * 10 + b; //permutarea 1, 3, 2;
fr[val] = 1;
val = b * 100 + a * 10 + c; //permutarea 2, 1, 3;
fr[val] = 1;
val = b * 100 + c * 10 + a; //permutarea 2, 3, 1;
fr[val] = 1;
val = c * 100 + a * 10 + b; //permutarea 3, 1, 2;
fr[val] = 1;
val = c * 100 + b * 10 + a; //permutarea 3, 2, 1;
fr[val] = 1;
}
}
}
int sol = 0;
for(int i = 100; i <= 999; i++) {
sol += fr[i];
}
return sol;
}
În funct, ia getAns(), init, ializăm cei trei vectori s, i iterăm toate combinat, iile posibile s, i toate
modurile de a permuta cele trei zaruri. Apoi, pentru a concatena cifrele, înmult, im prima
cifră cu 100, pe a doua cu 10 s, i o adunăm, iar apoi o adunăm s, i pe a treia. Marcăm valorile
găsite în vectorul fr s, i numărăm câte valori de 1 avem. Funct, ia returnează valoarea 521,
care este s, i răspunsul corect. Prin urmare, varianta D este corectă.
Problema 5
Pentru care dintre următoarele valori ale lui n există o alegere de semne plus/minus astfel
încât expresia 1 ± 2 ± 3 ± 4 ± · · · ± n să ia valoarea 0?
A. 2021 B. 2022 C. 2023 (CORECT) D. 2025 E. 2026
64

Subiect și barem · pagina 65

Concursul MateInfoUB, Sect, iunea Informatic˘a
Explicat, ie:
Cea mai us, oară metodă de a rezolva problema necesită să observăm că trebuie să putem
împăr t, i elementele în două mult, imi de sume egale, atribuind uneia semnul minus s, i
celeilalte semnul plus. Deoarece suma elementelor este n·(n+1)
2 , iar aceasta trebuie să fie
pară pentru a putea să o împăr t, im, rezultă că trebuie să fie un multiplu de 4. Prin urmare,
restul împărt, irii lui n la 4 trebuie să fie 0 sau 3. Astfel, singura opt, iune rămasă este 2023.
Dacă nu observăm acest lucru, mai sunt s, i alte metode de a construi o solut, ie. De exemplu,
putem forma perechi de tipul (1, 2), (3, 4), . . . , (n − 1, n), punând semnul plus între perechi
s, i semnul minus între termenii unei perechi. Astfel, pentru un n par vom ob t, ine suma − n
2 ,
iar pentru un n impar vom mai avea s, i un termen liber. În acest caz, vrem ca elementul de
valoare n
2 să aibă semnul plus, iar în rest să formăm perechi exact ca mai sus. Observăm că
acest lucru este posibil dacă n
2 este impar, deoarece nu este legat de niciun alt element care
să ne oblige să îi atribuim semnul minus.
Având în vedere cele de mai sus, observăm că n trebuie să fie impar, iar n
2 trebuie să fie tot
impar. Prin urmare, 2023 este singurul candidat. Putem scrie:
1 − 2 + 3 − 4 + · · · + 1009 − 1010 + 1011 + 1012 − 1013 + · · · + 2022 − 2023
Astfel, vom avea 1011 perechi de forma i − (i + 1), ceea ce duce la suma −1011. Adăugând
1011, obt, inem 0.
În concluzie, răspunsul corect este C.
Problema 6
Se consideră funct, ia:
int h(int a, int b, int k) {
if(a <= 0) {
if(k == 1)
return a + b;
else return b;
} else {
return h(a - b, b, k + 1);
}
}
Care va fi valoarea expresiei h(14052022, 23, 0)?
A. 14 B. 23 (CORECT) C. 2022 D. 610957 E. 14051999
Explicat, ie:
La o analiză a funct, iei, observăm că, atâta timp cât a este mai mare decât 0, vom scădea b
din el s, i vom cres, te k. Apoi, pentru prima valoare a lui a care este mai mică sau egală cu 0,
vom intra pe primul if. Aici, dacă am scăzut o singură dată din a pe b, vom returna a + b,
altfel vom returna b. Primul caz se întâmplă doar dacă avem b ≥ a, caz în care vom face
a = a − b s, i vom returna a + b, prin urmare, de fapt vom returna a atunci când a ≤ b, iar în
rest vom returna b, care rămâne neschimbat. Astfel, observăm că func t, ia este echivalentă
cu min(a, b), prin urmare va returna 23.
O altă variantă este să observăm că mereu scădem b din a, până când a va fi ≤ 0, apoi ne
oprim. Astfel, observăm că numărul de apeluri recursive este O(a/b), s, i deoarece această
valoare pentru inputul nostru nu este foarte mare, putem să rulăm funct, ia, asumându-ne
65

Subiect și barem · pagina 66

Probleme de dificultate medie
că avem stack size-ul setat la o valoare suficient de mare pentru a face aproximativ 700000
de apeluri recursive. De altfel, putem să o rulăm pe un judge online care ne oferă un stack
size suficient de mare, un astfel de judge s, i funct, ia scrisă în C++ se găses, te aici.
Problema 7
Câte numere între 1 s, i 2.000.000.000 au exact 5 divizori?
A. 0 B. 12 C. 34 D. 47 (CORECT) E. 156
Explicat, ie:
Este bine cunoscut faptul că doar pătratele perfecte au un număr impar de divizori. Motivul
este că fiecare divizor trebuie să aibă un complementar, iar doar pătratele perfecte au un
divizor al cărui complementar este egal cu el însus, i, adăugând astfel un singur divizor
suplimentar în loc de doi la numărul total de divizori.
Vom nota f (x) ca fiind numărul de divizori ai lui x. Observăm că f (x · x) = 2 · f (x) − 1.
Aceasta se explică prin faptul că, pentru fiecare divizor al lui x, acesta devine divizor al lui
x · x, având un complementar suplimentar. Prin urmare, pentru ca un pătrat perfect să aibă
exact 5 divizori, radicalul său trebuie să fie, la rândul său, un pătrat perfect, s, i mai mult,
un pătrat perfect al unui număr prim.
Folosind aceste două observa t, ii, trebuie să determinăm câte numere prime, ridicate la
puterea a patra, sunt mai mici decât limita superioară. Observăm că al 48-lea număr prim
223), ridicat la puterea a patra, este mai mare decât limita superioară.
As, adar, există 47 de numere care respectă condit, ia, iar răspunsul corect este D.
O variantă alternativă ar fi, după prima observa t, ie, să scriem un algoritm care verifică,
pentru fiecare pătrat perfect, cât, i divizori are s, i să contorizăm acele pătrate cu exact
5 divizori. Acesta ar avea o complexitate de O(limita superioară), deoarece trebuie să
verificăm doar radicalul valori, fiecare verificare având o complexitate de radical.
Problema 8
Care este suma maximă a elementelor matricei de mai jos, după înmult, irea unor linii s, i/sau
coloane (posibil chiar toate) cu −1? Înmul t, irea unei linii sau coloane cu −1 presupune
înmult, irea tuturor elementelor sale cu −1.
4 −1 6 4 −5
−2 −33 −12 10 −11
1 0 3 −1 4
−99 −98 −40 34 33
A. 233 B. 234 C. 235 D. 361 (CORECT) E. 427
Explicat, ie:
Pentru început, putem aplica o strategie greedy în care, atâta timp cât avem o linie sau
coloană cu suma mai mică decât 0, o înmul t, im cu -1. Astfel, observăm că putem înmult, i
liniile 2 s, i 4, obt, inând matricea:
66

Subiect și barem · pagina 67

Concursul MateInfoUB, Sect, iunea Informatic˘a
4 −1 6 4 −5
2 33 12 −10 11
1 0 3 −1 4
99 98 40 −34 −33
Acum mai putem înmult, i coloana 4 s, i 5 cu -1 obt, inând matricea:
4 −1 6 −4 5
2 33 12 10 −11
1 0 3 1 −4
99 98 40 34 33
Însumând elementele obt, inem:
4 − 1 + 6 − 4 + 5 + 2 + 33 + 12 + 10 − 11 + 1 + 0 + 3 + 1 − 4 + 99 + 98 + 40 + 34 + 33 = 361
care este s, i răspunsul corect. În concluzie varianta D este cea corectă.
Problema 9
Toată lumea are acasă o ceas, că cu monedele de 10 s, i 50 bani cu care nu are ce să facă. Alex
a decis să schimbe acest lucru. Începând de acum, el s-a hotărât să plătească orice sumă
cât mai exact poate. Concret, dacă are de plătit la magazin, va încerca:
• să dea cât mai multe monede de 50 de bani poate, fără să depăs, ească suma totală;
• după ce nu mai poate da monede de 50 de bani, încearcă să dea cât mai multe de 10
bani, de asemenea fără a depăs, i suma totală;
• după aceea plătes, te suma rămasă cu bancnote de 1 leu.
De notat că mereu casierul dă restul exact, cu numărul minim de monede necesar. Init, ial,
Alex are:
• 10 monede de 50 de bani
• 10 monede de 10 bani.
Cu ce monede va rămâne Alex, dacă are de plătit, în ordine, sumele 4.7, 2.3, 10.1, 3.5?
A. o monedă de 50 de bani s, i o monedă de 10 bani.
B. două monede de 50 de bani.
C. nicio monedă.
D. 4 monede de 10 bani. (CORECT)
E. o monedă de 50 de bani.
Explicat, ie:
Vom nota monedele de 10 bani cu x s, i pe cele de 50 de bani cu y. Init, ial vom avea 10x s, i 10y.
Prima plată este de 4, 7 lei. Conform algoritmului, vom efectua această plată utilizând 2x
s, i 9y, astfel reus, ind să achităm suma exactă. După această plată, rămânem cu 8x s, i y.
Pentru a doua plată, vom folosi ultimul y rămas s, i cei 8x, rămânând cu 1 leu de achitat.
Suma se va plăti exact, astfel încât, după această etapă, vom rămâne cu 0x s, i 0y.
La a treia plată, neavând monede, vom achita cei 11 lei utilizând bancnote de 1 leu. Vom
primi un rest de 90 de bani, care va fi oferit sub forma a 4x s, i y.
67

Subiect și barem · pagina 68

Probleme de dificultate medie
În ultima plată, vom folosi toate monedele disponibile, iar după efectuarea plă t, ii vom
rămâne cu 2,6 lei de achitat. Această sumă va fi achitată cu 3 bancnote de 1 leu, primind
un rest de 4x.
În concluzie, la final vom avea 4 monede de 10 bani rămase. Răspunsul corect este D.
Problema 10
Alex se uită la pret, ul ac t, iunilor sale pe pia t, ă. În mod inexplicabil, pret, ul ac t, iunilor la
minutul i este:
(i3 + 7 · i2 + 3 · i + 84) mod 100
Având pre t, ul act, iunilor pentru minutul 1, 2, . . . , 100, Alex î s, i pune următoarea întrebare:
dacă ar putea, pe parcursul acestor 100 de minute, să cumpere o ac t, iune s, i să o vândă mai
târziu, care este profitul maxim pe care ar putea să îl obt, ină?
A. 0 B. 34 C. 55 D. 73 E. 96 (CORECT)
Explicat, ie:
Putem vinde s, i cumpăra o singură dată, prin urmare presupunem că vom vinde ac t, iunea
pe care o cumpărăm în minutul i. Pentru a ne maximiza profitul, trebuie să o cumpărăm
în minutul cu cel mai mic pre t, care are indexul ≤ i. Astfel, pentru a obt, ine profitul maxim,
selectăm valoarea maximă a diferen t, ei dintre pret, ul din minutul i s, i cel mai mic pre t, anterior.
Deoarece calculele ar necesita un timp considerabil, vrem să utilizăm un instrument
algoritmic pentru a determina răspunsul. O implementare a logicii descrise mai sus, în
limbajul C++, este următoarea:
int getAns() {
int ans = 0, minn = 100;
for(int i = 1; i <= 100; i++) {
int val = i * i * i + 7 * i * i + 3 * i + 84;
val %= 100;
minn = min(minn, val);
ans = max(ans, val - minn);
}
return ans;
}
În func t, ia getAns, iterăm prin fiecare minut, calculăm valoarea corespunzătoare s, i
actualizăm minimul înregistrat până în acel moment. Apoi, determinăm diferent, a maximă.
Func t, ia returnează valoarea 96, care este s, i răspunsul corect, prin urmare varianta E este
cea corectă.
Problema 11
Fie numerele speciale:
100, 356, 440, 1137, 1901
Definim puterea unui număr x întreg ca fiind distan t, a fa t, ă de cel mai apropiat număr
special, respectiv valoarea minimă a modulului: |x − s| unde s este unul dintre numerele
speciale.
68

Subiect și barem · pagina 69

Concursul MateInfoUB, Sect, iunea Informatic˘a
Câte numere cuprinse între 1 s, i 2022 (inclusiv) au puterea un număr prim?
A. 141 B. 2008 C. 446 D. 431 (CORECT) E. 1577
Explicat, ie:
Pentru început, vom încerca să rezolvăm această problemă fără a scrie cod, dar ne vom
folosi totus, i de o resursă online care poate determina câte numere prime mai mici decât o
valoare n există, precum aceasta. Pe noi ne interesează valoarea distan t, ei fa t, ă de cel mai
apropiat număr special, astfel încât putem împărt, i numerele în următoarele cazuri:
• Numerele din intervalul [1, 100] sunt cele mai apropiate de numărul special 100 s, i
vor avea valori ale puterii între 0 s, i 99. Fiecare valoare apare o singură dată, astfel că
ne interesează câte numere prime există mai mici decât 99. Folosind resursa online
ment, ionată anterior, obt, inem că există 25 de astfel de numere.
• Următorul interval este [101, 356]. Numerele până la jumătatea acestuia, adică cele
din [101, 228], sunt mai apropiate de 100, iar cele din [229, 356] sunt mai apropiate
de 356. Astfel, pentru primul subinterval, ne interesează câte numere prime există
între 1 s, i 128, iar pentru al doilea între 0 s, i 127. În ambele cazuri, obt, inem câte 31 de
numere cu puteri prime.
• Repetăm procesul pentru intervalul [357, 440], pe care îl împăr t, im în [357, 398] s, i
[399, 440]. Ne interesează câte numere prime există între 1 s, i 41 s, i între 0 s, i 41,
obt, inând câte 13 numere pentru fiecare subinterval.
• Pentru intervalul [441, 1137], îl împăr t, im în [441, 789] s, i [790, 1137]. Ne interesează
câte numere prime există între 1 s, i 348 s, i între 0 s, i 347, ob t, inând 69 pentru fiecare
subinterval.
• Pentru intervalul [1138, 1901], îl împăr t, im în [1138, 1519] s, i [1520, 1901]. Ne interesează
câte numere prime există între 1 s, i 381 s, i între 0 s, i 381, ambele având câte 75 de astfel
de numere.
• Pentru ultimul interval [1902, 2022], ne interesează câte numere prime există mai
mici decât 120, obt, inând 30 de astfel de numere.
Adunând rezultatele, ob t, inem: 25 + 31 + 31 + 13 + 13 + 69 + 69 + 75 + 75 + 30 = 431, care
este s, i răspunsul corect.
De asemenea, putem scrie un scurt fragment de cod pentru a rezolva problema. O
implementare în limbajul C++ este următoarea:
int getAns() {
int val[] = {100, 356, 440, 1137, 1901};
int ans = 0;
for(int i = 1; i <= 2022; i++) {
int minn = 2022;
for(int j = 0; j < 5; j++)
minn = min(minn, abs(i - val[j]));
if(minn < 2) continue;
bool isPrime = true;
for(int j = 2; j * j <= minn; j++)
if(minn % j == 0) isPrime = false;
ans += isPrime;
}
return ans;
}
69

Subiect și barem · pagina 70

Probleme de dificultate medie
Funct, ia getAns() parcurge fiecare valoare de la 1 la 2022, calculează distant, a minimă fa t, ă
de un număr special s, i verifică dacă aceasta este primă. Func t, ia returnează valoarea 431,
care este răspunsul corect, prin urmare varianta D este corectă.
Problema 12
Bunica lui Matei are un fotoliu. Fotoliul este foarte vechi, iar din tapit, erie au început să
iasă arce.
Putem privi fotoliul ca o matrice pătratică de 100 × 100, având cele patru colt, uri la coordo-
natele: (0, 0), (0, 100), (100, 0), (100, 100). Matei a observat 5 arce, fiecare reprezentat prin
două coordonate (Xi,Yi), care indică locul unde acesta străpunge fotoliul.
Evident, Matei nu vrea să se as, eze pe un arc, astfel că se întreabă care este aria celui
mai mare pătrat inclus în tapit, erie, având laturile paralele cu axele de coordonate s, i în
interiorul căruia să nu se afle niciun arc. Se observă că arcele au voie să se afle pe laturile
s, i colt, urile pătratului.
Arcele sunt caracterizate prin următoarele coordonate:
(48, 47), (64, 27), (54, 28), (80, 83), (92, 36)
Care este latura maximă a unui pătrat complet inclus în tapi t, erie, cu laturile paralele cu
axele de coordonate, în interiorul căruia nu se află niciun arc?
A. 23 B. 33 C. 43 D. 53 (CORECT) E. 63
Explicat, ie:
Pentru început, putem observa că punctul (48, 47) este foarte central s, i ne limitează latura
semnificativ. Datorită acestuia, nu putem plasa un pătrat cu latura mai mare de 53,
deoarece acesta ar cuprinde punctul în interiorul său.
În continuare, dacă am reprezenta punctele în plan, aici se află o reprezentare grafică,
de men t, ionat este faptul că coordonatele sunt inversate, deoarece într-o matrice liniile
corespund axei OY , iar coloanele axei OX. De asemenea, col t, urile de sus sunt de fapt
colt, uri de jos s, i invers. Din desen observăm că în partea dreapta-sus există un spat, iu mare
gol. Aici putem plasa un pătrat cu latura 53, mai exact îl putem plasa cu col t, ul stânga-sus
în (0, 47) s, i colt, ul dreapta-jos în (53, 100).
De asemenea, dacă nu reprezentăm punctele în plan, putem scrie un scurt fragment de cod
care rezolvă problema. Prima observa t, ie este că arcele au coordonate întregi, iar col t, urile
care limitează fotoliul au, de asemenea, coordonate întregi. Astfel, s, tim că există cel put, in
un pătrat cu latura maximă care are col t, urile cu coordonate întregi. Motivul este că, fie
pe orizontală, fie pe verticală, pătratul nostru trebuie să fie mărginit de un arc sau de
marginea planului; altfel, l-am putea extinde s, i mai mult.
Folosindu-ne de observat, ia anterioară, putem fixa latura L, iterând prin toate valorile de la
1 la 100. Apoi, fixăm col t, ul stânga-sus iterând prin toate combina t, iile posibile de valori
(x, y), unde 0 ≤ x, y ≤ 100. Pentru un punct fixat (x, y) s, i o latură fixată L, colt, ul dreapta-jos
va fi în (x + L, y + L). Acum trebuie să verificăm că niciun punct nu se află în interiorul
pătratului, adică vrem ca fiecare dintre cele 5 puncte să nu aibă coordonata x cuprinsă
între x s, i x + L, s, i coordonata y cuprinsă între y s, i y + L. O implementare în limbajul C++
este următoarea:
70

Subiect și barem · pagina 71

Concursul MateInfoUB, Sect, iunea Informatic˘a
int getAns() {
int ans = 0;
pair<int, int> p[] = {{48, 47}, {64, 27}, {54, 28}, {80, 83}, {92, 36}};
for(int L = 0; L <= 100; L++) {
for(int x = 0; x + L <= 100; x++) {
for(int y = 0; y + L <= 100; y++) {
bool ok = true;
for(int i = 0; i < 5; i++) {
if(x < p[i].first && p[i].first < x + L
&& y < p[i].second && p[i].second < y + L)
ok = false;
}
if(ok) ans = L;
}
}
}
return ans;
}
În func t, ia getAns(), fixăm latura s, i coordonatele (x, y). De ment, ionat este că trebuie să
avem x + L ≤ 100, la fel s, i y + L ≤ 100, deoarece matricea este mărginită de colt, ul (100, 100)
în direct, ia dreapta-jos. Apoi, verificăm ca fiecare punct să nu se afle în interiorul pătratului.
Deoarece acesta poate fi pe margini, folosim strict < în loc de ≤ la comparat, ie. În cazul în
care găsim un punct care este inclus în pătrat, setăm variabila ok la false. Dacă ok rămâne
true pentru un punct (x, y), atunci acesta este o solut, ie cu latura L.
Funct, ia returnează valoarea 53, care este s, i răspunsul corect. În concluzie, varianta D este
cea corectă.
3.3 Din anul 2023
Problema 1
Alex, Dan s, i Matei sunt prieteni buni. Ei au participat împreună la un concurs de
programare formând o echipă s, i au câ s, tigat marele premiu, o consolă XBOX. Cum ei se
în t, eleg bine, se hotărăsc să împartă marele premiu, respectiv fiecare dintre ei se va juca pe
rând o săptămână pe consolă. Cei trei prieteni trebuie să decidă acum ordinea în care se
vor juca pe consola XBOX. Alex propune să stabilească această ordine folosind următorul
algoritm care amestecă cele trei elemente din vectorul v situate pe pozit, iile 0, 1 s, i 2:
v = [Alex, Dan, Matei]
pentru i de la 0 la 2
swap(v[i], v[random(3)])
unde swap(a, b) interschimbă valorile elementelor a s, i b, iar random(3) returnează un
număr aleator 0, 1 sau 2 cu probabilitatea uniformă 1/3.
Care este s, ansa ca Matei să fie generat pe prima pozi t, ie (pozi t, ia 0) a vectorului v
folosind algoritmul de mai sus?
A. 1/2 B. 1/3 C. 1/4 D. 8/27 (CORECT) E. 3/10
71

Subiect și barem · pagina 72

Probleme de dificultate medie
Explicat, ie:
Algoritmul efectuează 3 swap-uri consecutive, iar fiecare swap poate schimba pozit, ia lui
Matei. Pentru a calcula probabilitatea finală, vom analiza scenariile posibile: Fie vectorul
init, ial:
v = [Alex, Dan, Matei]
Algoritmul efectuează 3 swap-uri, pentru i = 0, 1, 2 se alege un index aleator r din {0, 1, 2}
s, i se interschimbă v[i] cu v[r]. Prima observa t, ie de care ne putem lega este aceea că Matei
poate ajunge pe pozi t, ia 0, de la pasul i = 0 sau de la pasul i = 2. Analiza se face în trei pa s, i:
La pasul i = 0:
Se face swap între v[0] s, i v[r0]. Dintre acestea cazurile care ne interesează sunt:
• Dacă r0 = 2, atunci Matei ajunge pe pozit, ia 0 (probabilitate 1
3 ).
• Altfel (adică r0 = 0 sau r0 = 1), Matei va rămâne pe pozit, ia 2 (probabilitate 2
3 ).
La pasul i = 1:
Se efectuează swap între v[1] s, i v[r1]. Dintre acestea cazurile care ne interesează sunt:
• Dacă Matei se află pe pozit, ia 0, atunci probabilitatea ca matei să rămână pe
pozit, ia 0 este 2
3 .
• Dacă Matei se află pe pozi t, ia 2, atunci probabilitatea ca Matei să rămână pe
pozit, ia 2 este 2
3 .
La pasul i = 2:
Se efectuează swap între v[2] s, i v[r2]. Dintre acestea cazurile care ne interesează sunt:
• Dacă Matei se află pe pozi t, ia 0, atunci probabilitatea ca Matei să rămână pe
pozit, ia 0 este 2
3 .
• Dacă Matei se află pe pozit, ia 2, atunci probabilitatea ca Matei să ajungă pe
pozit, ia 0 este 1
3 .
Astfel, combinând contribut, iile din to t, i pas, ii s, i analizând toate scenariile posibile, probabi-
litatea ca Matei să se afle pe pozit, ia 0 la final este:
( 1
3 × 2
3 × 2
3 ) + ( 2
3 × 2
3 × 1
3 ) = 8
27
Prin urmare, răspunsul corect este D.
De asemnea ne putem folosi de un program C++ pentru a calcula această probabilitate.
Vom lua fiecare posibilitate pentru r0, r1, r2 s, i vom calcula probabilitatea ca Matei să fie pe
pozit, ia 0 la final.
int fav = 0;
for (int r_0 = 0; r_0 < 3; ++r_0)
for (int r_1 = 0; r_1 < 3; ++r_1)
for (int r_2 = 0; r_2 < 3; ++r_2) {
std::vector <std::string> v = {"Alex", "Dan", "Matei"};
swap(v[0], v[r_0]);
swap(v[1], v[r_1]);
swap(v[2], v[r_2]);
fav += (v[0] == "Matei");
}
std::cout << fav << "/27\n";
72

Subiect și barem · pagina 73

Concursul MateInfoUB, Sect, iunea Informatic˘a
Problema 2
Considerăm s, irurile de caractere de lungime 10 care cont, in literele a s, i b, dar fără a cont, ine
trei aparit, ii consecutive ale literelor a sau b. Spre exemplu, s, irul ‘ababababab’ este un
exemplu pozitiv (verifică regulile), iar s, irul ‘aaabababab’ este un exemplu negativ (nu
verifică regulile). Câte exemple pozitive de astfel de s, iruri de caractere există?
A. 68 B. 110 C. 175 D. 178 (CORECT) E. 288
Explicat, ie:
Vom folosi programare dinamică pentru a rezolva această problemă. Fie:
• a1− numărul de s, iruri de lungime n care se termină cu o singură literă a,
• a2− numărul de s, iruri de lungime n care se termină cu două litere a,
• b1− numărul de s, iruri de lungime n care se termină cu o singură literă b,
• b2− numărul de s, iruri de lungime n care se termină cu două litere b.
Recurent, a este următoarea:
new_a1 = b1 + b2(punem litera a după litera b)
new_a2 = a1(punem litera a după litera a)
new_b1 = a1 + a2(punem litera b după litera a)
new_b2 = b1(punem litera b după litera b)
Pentru a rezolva problema, vom calcula a1, a2, b1, b2 pentru n = 10 s, i vom aduna toate
aceste valori pentru a ob t, ine numărul total de s, iruri care respectă condit, iile date. Vom
folosi următorul cod în C++ pentru a calcula numărul de s, iruri care respectă condit, iile
date:
// Init, ializare pentru n = 1
long long a1 = 1;
long long a2 = 0;
long long b1 = 1;
long long b2 = 0;
for (int i = 2; i <= 10; ++i) {
long long new_a1 = b1 + b2;
long long new_a2 = a1;
long long new_b1 = a1 + a2;
long long new_b2 = b1;
// Actualizăm stările pentru următorul pas
a1 = new_a1;
a2 = new_a2;
b1 = new_b1;
b2 = new_b2;
}
// Suma tuturor s, irurilor valide de lungime 10
long long total = a1 + a2 + b1 + b2;
std::cout << total << '\n';
Răspunsul furnizat este egal cu 178, astfel răspunsul corect este D.
73

Subiect și barem · pagina 74

Probleme de dificultate medie
O altă abordare pentru această problemă este să observăm că din moment ce avem doar 2
litere, întregul proces poate fi gândit în baza 2, unde 0 reprezintă litera a s, i 1 reprezintă
litera b. Vom enumera toate numere în baza 2 de la 0 la 1023 (deci de la 0 la 210 − 1) s, i
vom verifica dacă numărul respectă condit, iile date, anume să nu con t, ină trei apari t, ii
consecutive ale aceleia s, i cifre. Având un total de 210 s, iruri posibile, putem folosi următorul
cod în C++/Python pentru a calcula numărul de s, iruri care respectă condit, iile date:
// cod C++
int cnt = 0;
for (int msk = 0; msk < (1 << 10); ++msk)
{
// convertim masca de biti in string
std::string s = std::bitset<10>(msk)
.to_string();
bool bad = false;
// verificam daca exista 3 biti
// consecutivi de aceeasi valoare
for (int i = 0; i <= 7; ++i) {
if (s[i] == s[i + 1] &&
s[i] == s[i + 2]) {
bad = true;
break;
}
}
cnt += (!bad);
}
// afisam numarul de masti valide
std::cout << cnt << '\n';
# cod Python
cnt = 0
for msk in range(0, 2 ** 10):
s = str(bin(msk))[2:].zfill(10)
bad = False
for i in range(8):
if s[i:i+3] == '000' or \
s[i:i+3] == '111':
bad = True
break
if not bad:
cnt += 1
print(cnt)
Problema 3
Care este, în medie, probabilitatea ca funct, ia de mai jos să returneze true? Func t, ia rnd()
returnează un număr aleator real uniform distribuit între 0 s, i 1.
Atent, ie: funct, ia rnd() nu este aceeas, i cu funct, ia rand() din C/C++.
bool F() {
if (rnd() < 0.5)
return true;
if (rnd() < 0.4)
return false;
return rnd() < 0.3;
}
A. 0.5 B. 0.56 C. 0.59 (CORECT) D. 0.9 E. 0.94
Explicat, ie:
Calculăm probabilitatea de a returna true, în funct, ia F(), analizând fiecare caz posibil:
Prima condit, ie rnd() < 0.5
• Probabilitatea de a returna true este 0.5.
• Dacă nu se intră în această condit, ie, probabilitatea de a ajunge la a doua condit, ie
este 0.5.
74

Subiect și barem · pagina 75

Concursul MateInfoUB, Sect, iunea Informatic˘a
A doua condit, ie rnd() < 0.4
• Probabilitatea de a returna false este 0.5 × 0.4 = 1
2 × 2
5 = 2
10 = 0.2.
• Dacă nu se intră în această condi t, ie, probabilitatea de a ajunge la a treia condit, ie
este (0.5 × (1 − 0.4) = 1
2 × 3
5 = 3
10 = 0.3).
A treia condit, ie rnd() < 0.3
• Probabilitatea de a returna true este 0.3 × 0.3 = 0.09.
Probabilitatea totală de a returna true este suma probabilităt, ilor de a returna true în fiecare
caz posibil:
0.5 + (0.5 × 0.6 × 0.3 = 0.09) = 0.59
Prin urmare, răspunsul corect este C.
Problema 4
Se dau următoarele 3 funct, ii:
int A(int x) {
if (x <= 1)
return x;
return A(x - 1) + A(x - 2);
}
int B(int x) {
if (x <= 1)
return 1;
return B(x / 2) + B(x / 2);
}
int C(int x) {
if (x < 0)
return 0;
return 1 + C(x - 10);
}
Se presupune ca tipul de date int folosit nu dă overflow s, i poate salva valori oricât de mari.
Considerând numerele a = A(123456789), b = B(123456789) s, i c = C(123456789), care dintre
următoarele inegalităt, i este adevărată?
A. a < b < c B. c < b < a (CORECT) C. b < a < c D. c < a < b E. a < c < b
Explicat, ie
Vom analiza comportamentul fiecărei funct, ii în parte.
• Funct, ia A returnează pentru un număr dat x, al x-lea termen Fibonnaci.
• Func t, ia B returnează pentru un număr dat x, o puterea a lui 2, care este mai mică
sau egală decât x.
• Funct, ia C returnează pentru un număr dat x, valoarea ⌊ x
10 ⌋ + 1.
Este clar că valoarea funct, iei A va avea cea mai mare valoare din moment ce numerele
Fibonacci cresc exponent, ial: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . ..
Funct, ia B va returna o valoare care este o putere a lui 2, iar func t, ia C va returna o valoare
care este un factorul multiplicativ al lui 10, pentru a ob t, ine un număr care este mai mare
decât n. Astfel, putem concluziona că a > b > c. Prin urmare, răspunsul corect este B.
Problema 5
Într-o matrice M de dimensiune m×n se nume s, te punct s, a un element M[i][ j] cu proprietatea
că fie este minim pe linia i s, i maxim pe coloana j, fie este maxim pe linia i s, i minim pe
75

Subiect și barem · pagina 76

Probleme de dificultate medie
coloana j. Dacă elementele matricei M sunt o permutare a mul t, imii {1, 2, . . . , m . . . n}, unde
m ≥ 3 s, i n ≥ 3, atunci numărul maxim de puncte s, a pe care poate să le aibă matricea M este:
A. minimul dintre m s, i n B. maximul dintre m s, i n C. 0 D. 1 E. 2 (CORECT)
Explicat, ie
Vom demonstra că numărul maxim de puncte s, a pe care le poate avea matricea M este 2.
Fie M o matrice de dimensiune m × n care cont, ine o permutare a mult, imii {1, 2, . . . , m . . . n}.
Vom presupune că există cel put, in 3 puncte s, a în matricea M.
0 1 2 3 4
0
1
2
3
4
Considerăm figura de mai sus unde avem 3 puncte s, a colorate diferit. Considerăm punctele
în ordinea culorilor (de la stânga la dreapta). Presupunem că punctul violet are o valoare
mai mică decât punctul ros, u. De asemenea presupunem că punctul violet este minim pe
linia sa, s, i maxim pe coloana sa.
Din acest moment putem concluziona că punctul ro s, u nu poate fi minim pe linia sa
deoarece, intersectându-se cu coloana punctului violet, pe coloana punctului violet se află
un element mai mic decât cel violet (din moment ce este maxim pe coloana), astfel pe linia
punctului ro s, u se va afla un element mai mic decât punctul ros, u (am stabilit că punctul
ros, u este mai mare decât cel violet), deci punctul ros, u nu va putea fi minim pe linia sa.
Dar punctul ros, u poate fi maxim pe linia sa, s, i minim pe coloana sa. Acest lucru în schimb
fort, ează punctul albastru să fie ori minim pe linie s, i maxim pe coloană, ceea ce am stabilit
că nu este posibil, ori maxim pe lini s, i minim de coloană, presupunând că punctul albastru
este mai mare decât punctul ros, u, s, i folosindu-ne de aceea s, i logică ca mai sus, ajungem la
o contradict, ie.
Prin urmare, numărul maxim de puncte s, a pe care le poate avea matricea M este 2. Prin
urmare, răspunsul corect este E.
Problema 6
O furnicu t, ă se deplasează pe o frunză, reprezentată printr-o matrice triunghiulară de
dimensiune 2023, cu liniile s, i coloanele numerotate de la 1 (matricea are deci 2023 linii, iar
fiecare linie i din matrice are i coloane). Ea ar vrea să calculeze în câte moduri poate ajunge
din vârful frunzei, adică prima linie a matricei (din celula (1, 1)), la baza frunzei, adică pe
ultima linie a matricei (în oricare dintre celulele acesteia), s, tiind că pentru că este as, a de
mică se poate deplasa dintr-o celulă a matricei doar un pas în jos sau un pas în dreapta-jos
(din celula (i, j) în (i + 1, j) sau (i + 1, j + 1)). Până să găsească ea o strategie de numărare,
o omidă a venit s, i a mu s, cat dintr-o margine a frunzei celulele (x, 1) unde x este multiplu
de 100. Mai mult, omida pofticioasă a mu s, cat s, i celula (2001, 1999). Furnicut, a nu mai s, tie
acum să calculeze câte trasee poate face fără a trece prin celulele mus, cate, as, a ca va roagă
pe voi să calculat, i care este cea mai mare putere a lui 2 care divide numărul acestor trasee.
76

Subiect și barem · pagina 77

Concursul MateInfoUB, Sect, iunea Informatic˘a
A. 22 B. 25 (CORECT) C. 2021 D. 23 E. 0
Explicat, ie
În frunza completă (matricea triunghiulară de dimensiune 2023), fiecare traseu de la (1, 1),
la ultima linie are 2022 de pas, i, fiecare pas având 2 op t, iuni (jos sau dreapta-jos). Prin
urmare, numărul total de trasee este 22022.
Celulele de tip (x, 1), cu x multiplu de 100, sunt mus, cate. Observa t, i că în mod normal,
în orice traseu, celula din stânga, (r, 1), se obt, ine numai dacă la fiecare pas s-a ales ‘jos’,
(deoarece din (r − 1, 1), singurul mod de a rămâne în coloana 1 este pasul vertical). Astfel,
un traseu care folose s, te pas, ii verticali în primele 99 de mutări va ajunge la (100, 1) - celulă
mus, cată. Numărul acestor trasee este 22022−99 = 21923.
Deci după eliminare acestora, numărul de trasee care nu ating celule mus, cate este
N1 = 22022 − 21923 = 21923 × (299 − 1).
Pentru a ajunge la (2001, 1999), un traseu (în frunza completă) necesită 2000 de pas, i, dintre
care:
• 1999 − 1 = 1998 pas, i ‘dreapta-jos’ (deoarece numărul coloanei este 1 plus numărul
de astfel de pas, i)
• 2001 − 1998 = 2 pas, i ‘verticali’.
Deci numărul de trasee de la (1, 1) la (2001, 1999) este 2000
2

.
Din (2001, 1999) până pe ultima linie (rândul 2023) sunt 22 pas, i, deci numărul de completări
este 222.
Astfel, numărul de trasee care trec prin (2001, 1999) (s, i care, fiind de natură cu doar 2 pa s, i
verticali, nu pot fi afectat, i de restrict, ia de la margine) este
N2 =
2000
2

· 222 = 23 · (125 · 1999) · 222 = 225 · (125 · 1999).
Scăzând din N1 cele N2 trasee care trec prin (2001, 1999), obt, inem:
N = 21923(299 − 1) − 225 · (125 · 1999).
Factorizăm 225:
N = 225 21923−25(299 − 1) − (125 · 1999) .
În paranteză avem un număr impar minus 125 · 1999 (produs de numere impare), deci
rezultatul este impar. Concluzionăm astfel că 225 divide N s, i nu se poate extrage un factor
suplimentar de 2.
Prin urmare, cea mai mare putere a lui 2 care divide numărul traseelor este 225, prin
urmare răspunsul corect este B.
O altă varianta presupune codarea unui algoritm, C++, care să calculeze numărul de trasee
care nu trec prin celulele mus, cate s, i să găsească puterea de 2 potrivită, pentru mai multe
detalii consultat, i Problema numărului de drumuri în matrice, unde se prezintă o abordare
similară pentru calcularea numărului de trasee într-o matrice.
77

Subiect și barem · pagina 78

Probleme de dificultate medie
int n = 2023;
dp[1][1] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j) {
if (i % 100 == 0 && j == 1) continue;
if (i == 2001 && j == 1999) continue;
if (i - 1 >= 1) dp[i][j] += dp[i - 1][j];
if (i - 1 >= 1 && j - 1 >= 1) dp[i][j] += dp[i - 1][j - 1];
}
unsigned long long sum = 0;
for (int i = 1; i <= n; ++i)
sum += dp[n][i];
for (int i = 61; i >= 0; --i)
if (sum % (1LL << i) == 0) {
std:: cout << i << '\n';
break;
}
3.4 Din anul 2024
Problema 1
Comanda copăcel afi s, ează structura directoarelor. De exemplu, dacă avem un director A
care con t, ine directoarele B, C s, i D, directorul B cont, ine directoarele E s, i F, iar directorul D
cont, ine directorul G, atunci rezultatul comenzii copăcel va arăta în felul următor:
> copacel A
A
|-- B
| |-- E
| |-- F
|-- C
|-- D
| |-- G
7 directories, 0 files
În exemplul de mai sus, directoarele C, E, F s, i G sunt goale.
La linkul acesta se află rezultatul rulării comenzii copăcel pe un sistem cu 1500 de directoare
(s, i niciun fis, ier). Câte dintre directoarele prezente sunt goale?
A. 53 B. 164 C. 419 D. 602 E. 734 (CORECT) F. 953 G. 1231
Explicat, ie:
După o analiză a exemplului dat, putem observa că un director este gol dacă lungimea
liniei afi s, ate pentru el este de lungime cel pu t, in egală cu lungimea liniei următoare, sau
dacă este ultima linie dintre cele afis, ate. Astfel, pentru a răspunde la întrebarea problemei,
putem scrie un program C/C + + care să verifice condit, ia de mai sus.
78

Subiect și barem · pagina 79

Concursul MateInfoUB, Sect, iunea Informatic˘a
Observat, ie
Fi s, ierul oferit are la final 3 linii în plus care trebuie ignorate pentru ca rezultatul să fie
corect. Cel mai simplu este să le eliminăm direct din fis, ier.
O implementare a solu t, iei descrise mai sus în limbajul C++ este următoarea (considerăm
că au fost eliminate ultimele 3 linii din fis, ier):
ifstream f("tree_fixed.txt");
int main()
{
int ans = 0;
string s1, s2;
getline(f, s1);
while (getline(f, s2))
{
if (s1.size() >= s2.size())
ans++;
s1 = s2;
}
ans++; // ultimul director sigur este gol
cout << ans;
return 0;
}
Problema 2
Matei are 6 valize cu capacită t, ile de 14, 3, 16, 8, 2 s, i 5 litri. El î s, i alege o submul t, ime de
valize s, i calculează suma capacităt, ilor valizelor alese. Amuzat, Matei observă: „Există
exact două alegeri posibile ale valizelor care să dea suma aceasta!”.
Care este suma maximă a capacităt, ilor valizelor alese de Matei?
A. Este imposibil. B. 5 C. 8 D. 13 E. 19 F. 30 G. 43 (CORECT)
Explicat, ie:
Putem rezolva problema atât matematic, cât s, i prin intermediul unui program. În
continuare alegem să prezentăm ambele solut, ii în scop didactic, deoarece cea matematică
este clar mai rapidă.
Solut, ia 1
Pentru a exista exact două alegeri posibile ale valizelor care să dea suma aceasta, trebuie
să avem 2 elemente din submultime care să poată fi înlocuite cu un al treilea element.
Pentru a ob t, ine valoarea maximă, suma celor 2 elemente înlocuite trebuie să fie minimă.
Astfel, putem observa că cele 2 elemente sunt 2 s, i 3, iar cel de-al treilea element este 5.
Astfel, suma maximă pe care o putem obt, ine s, i care respectă proprietatea că poate fi
aleasă în două moduri este 43 (alegerea 1 este 2, 3, 8, 14, 16 s, i alegerea 2 este 5, 8, 14, 16).
Solut, ia 2
În total sunt 26 submul t, imi pe care Matei le poate alege. Putem rezolva problema scriind
un algoritm de tip backtracking.
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int main()
{
79

Subiect și barem · pagina 80

Probleme de dificultate medie
int ans = -1, nr_submultimi = (1 << 6);
vector<int> valize = {14, 3, 16, 8, 2, 5};
unordered_map<int, int> m;
for (int submultime = 0; submultime < nr_submultimi; submultime++)
{
int suma = 0;
for (int i = 0; i < (int)valize.size(); i++)
if (submultime & (1 << i))
suma += valize[i];
m[suma]++;
}
for (auto &it : m)
if (it.second == 2 && it.first > ans)
ans = it.first;
if (ans == -1)
cout << "este imposibil";
else
cout << ans;
return 0;
}
Problema 3
Câte numere X între 5 s, i 999 (inclusiv) au proprietatea că următorul s, ir de operat, ii se
termină:
X := numar intre 5 si 999
Y := 1
WHILE Y != 3:
Y = Y * 2 % X
Pentru cunoscători, problema cere să se afle pentru câte numere n cuprinse între 5 s, i 999,
numărul 3 este generat de 2 în (Zn, ×).
A. 0 B. 10 C. 64 D. 134 (CORECT) E. 257 F. 752 G. 989
Explicat, ie:
Putem observa că răspunsul la această problemă este echivalent cu răspunsul la următoarea
întrebare: pentru câte numere X între 5 s, i 999 (inclusiv) există k astfel încât 2k ≡ 3(mod X).
Folosind teoria grupurilor s, tim că puterile lui 2 vor cicla la un moment dat, ordinul
lui 2 fiind maxim X. As, adar, vom realiza un algoritm pătratic în care pentru un X fixat,
determinăm primele X puteri ale lui 2 modulo X s, i dacă dăm de valoarea 3 incrementăm
răspunsul s, i oprim calcularea pentru X-ul curent. O implementare a solut, iei descrise mai
sus în limbajul C++ este următoarea:
int main()
{
int ans = 0;
for (int X = 5; X <= 999; X++)
80

Subiect și barem · pagina 81

Concursul MateInfoUB, Sect, iunea Informatic˘a
{
int Y = 1;
for (int i = 1; i <= X; i++)
{
Y = (2 * Y) % X;
if (Y == 3)
{
ans++;
break;
}
}
}
cout << ans;
return 0;
}
Problema 4
Cecilia dore s, te să asculte playlist-ul ei preferat în recrea t, ia mare, care durează 15 minute.
Playlist-ul ei este compus din 5 cântece cu următoarele durate:
1. Cântecul 1: 4 minute s, i 35 de secunde
2. Cântecul 2: 3 minute s, i 25 de secunde
3. Cântecul 3: 6 minute s, i 20 de secunde
4. Cântecul 4: 12 minute s, i 20 de secunde
5. Cântecul 5: 5 minute s, i 40 de secunde
Înainte de a începe să asculte playlist-ul, Cecilia va apăsa pe butonul “shuffle” care va
amesteca în mod aleatoriu (uniform) cântecele. Care este numărul mediu de cântece pe
care Cecilia le poate asculta în totalitate?
A. 1.8 (CORECT) B. 2.5 C. 1.5 D. 2.2 E. 2.4 F. 2.3 G. 2.6
Explicat, ie:
Vom genera toate permutările cântecelor s, i vom verifica pentru fiecare câte cântece pot fi
ascultate în totalitate. Răspunsul va fi suma acestor numere supra numărului de permutări
care este 5! = 120. Pentru simplitate, vom considera lungimile cântecelor s, i timpul de
ascultare în secunde.
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int v[] = {0, 4 * 60 + 35, 3 * 60 + 25, 6 * 60 + 20,
12 * 60 + 20, 5 * 60 + 40};
int limita = 15 * 60, cnt = 0;
int permutare[6];
void procesare_solutie()
{
int suma = 0;
for (int i = 1; i <= 5; i++)
{
suma += v[permutare[i]];
if (suma <= limita)
cnt++;
}
}
bool valid(int k)
81

Subiect și barem · pagina 82

Probleme de dificultate medie
{
if (k == 1)
return true;
for (int i = 1; i < k; i++)
if (permutare[i] == permutare[k])
return false;
return true;
}
void bkt(int k)
{
for (int i = 1; i <= 5; i++)
{
permutare[k] = i;
if (valid(k))
{
if (k == 5)
procesare_solutie();
else
bkt(k + 1);
}
}
}
int main()
{
bkt(1);
cout << 1.0 * cnt / 120;
return 0;
}
Problema 5
Prietenel are 23 de colegi la firma la care lucrează (deci sunt în total 24 de angajat, i). El a
construit o ret, ea cu relat, iile de prietenie dintre angaja t, ii de la firmă. Astfel, el a numerotat
colegii cu numere de la 1 la 23 (pentru el a păstrat numărul 24, pentru că suntem în
2024) s, i a constatat că există m relat, ii de prietenie reciprocă între perechi (neordonate) de
angajat, i de la firma la care lucrează. Spunem că i este prieten cu j dacă există o rela t, ie de
prietenie între i s, i j (rela t, ia de prietenie între i s, i j fiind reciprocă, adică dacă i este prieten
cu j, atunci s, i j este prieten cu i). Prietenel s, i-a făcut lista L1 a prietenilor săi s, i lista L2 a
prietenilor prietenilor lui s, i a constatat că exact doi colegi ai săi nu se află în niciuna dintre
aceste liste. Care este valoarea minimă s, i, respectiv, valoarea maximă a lui m?
A. 21 s, i 252 (CORECT) B. 23 s, i 252 C. 21 s, i 251 D. 23 s, i 251 E. 21 s, i 232 F. 23 s, i
232 G. 22 s, i 231
Explicat, ie:
Observăm că putem modela problema ca pe un graf, unde angaja t, ii reprezintă nodurile,
iar relat, iile de prietenie muchiile. Datorită faptului că exact doi colegi de-ai lui Prietenel
nu se află în niciuna dintre cele 2 liste, putem deduce că graful distant, a de la Prietenel la ei
este fie 3 pentru amândoi, fie 3 pentru unul s, i 4 pentru celălalt, fie infinit (caz în care ele
sunt în altă componentă conexă).
Pentru a găsi valoarea minimă a lui m, observăm că vrem ca graful format cu muchiile
dintre Prietenel s, i nodurile din L1 s, i nodurile din L1 s, i L2 să fie un arbore, iar cei doi colegi
82

Subiect și barem · pagina 83

Concursul MateInfoUB, Sect, iunea Informatic˘a
care nu apar în niciuna dintre liste să fie în componente conexe separate (graful trebuie să
aibă în total 3 componente conexe). Prin urmare, numărul minim este de 21.
Pentru a obt, ine valoarea maximă a lui m vrem ca cele 2 noduri care nu apar nici în L1
s, i nici în L2 să fie la distan t, ă 3 de Prietenel, deoarece astfel putem adăuga muchii între
toate nodurile din L2 s, i cele 2 noduri din L3. Dacă în L1 sunt a noduri, iar în L2 sunt b
noduri, cu proprietate a + b = 21, numărul de muchii dintre mult, imile L1, L2 s, i L3 este
1 · a + a · b + b · 2 = a + a · b + 2b = a + b · (a + 2). Pe lângă acestea, trebuie să numărăm s, i
numărul de muchii din cadrul fiecărei mult, imi, pentru L1 este (a−1)a
2 , pentru L2 este (b−1)b
2
s, i pentru L1 este 1. Numărul maxim de muchii va fi a + b · (a + 2) + (a−1)a
2 + (b−1)b
2 + 1.
Mai rămâne să vedem cum vrem să distribuim cele 21 de noduri între L1 s, i L2. Putem
să verificăm toate variantele s, i să vedem care este numărul maxim de muchii. Cel mai
simplu este să scriem un program pentru a găsi răspunsul.
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int main()
{
int maxx = 0;
for (int a = 1; a <= 20; a++)
{
int b = 21 - a;
int calc = a + b * (a + 2) + (a - 1) * a / 2 + (b - 1) * b / 2 + 1;
if (calc > maxx)
maxx = calc;
}
cout << maxx;
return 0;
}
Problema 6
Într-un turneu de table de tip jackpot participă 40 de jucători, iar aces, tia sunt premiat, i cu
diverse sume, doar primii 4 în funct, ie de clasamentul final al acestora. Valoarea totală a
premiilor este de 10800 de dolari. Desigur, cei 4 nu vor primi exact aceea s, i sumă, însă, în
principiu, fiecare dintre ei are s, ansa să câ s, tige în medie 10800/4 = 2700 dolari. Turneul se
desfă s, oară astfel: jucătorii sunt grupat, i aleatoriu câte doi, joacă o partidă, iar câ s, tigătorii
trec în etapa următoare. Astfel, după 3 runde rămân 5 jucători: A, B, C, D s, i E. Teoretic
acum, fiecare dintre cei cinci are s, ansa să câ s, tige în medie 10800/5 = 2160 dolari. Pentru a
hotărî care vor fi cei 4 finali s, ti, se aleg aleatoriu doi jucători din cei cinci, să zicem D s, i E,
care vor juca o rundă suplimentară, câs, tigătorul intrând în finala celor 4.
Această rundă suplimentară diminuează s, ansele lui D s, i E la câs, tigul teoretic mediu.
83

Subiect și barem · pagina 84

Probleme de dificultate medie
Cu cât ar trebui compensat, i atât D cât s, i E din fondul total de premii, înainte de runda
suplimentară pe care o vor juca, astfel încât în final s, ansa la câs, tigul mediu (oricare ar fi
acesta) să rămână aceeas, i, s, i pentru cei cinci?
A. 0 dolari B. 540 dolari C. 720 dolari D. 1080 dolari (CORECT) E. 1350 dolari
F. 2160 dolari G. 2700 dolari
Explicat, ie:
Mai întâi trebuie să calculăm care este câs, tigul mediu al lui D s, i al lui E în momentul
actual. Pentru câs, tig probabilitatea este de 1/2 s, i atunci câs, tigul va fi de 2160 de dolari, iar
dacă pierde, eveniment care are probabilitate tot 1/2, câs, tigul lui va fi de 0 dolari, as, adar
câs, tigul lor mediu este 1/2 · 2160 + 1/2 · 0 = 1080.
Pentru A, B s, i C câs, tigul mediu este de 2160 de dolari. Problema ne cere să oferim o
compensat, ie, fie aceasta de a dolari, lui D s, i lui E astfel încât a+1080 = 2160 ⇐⇒ a = 1080.
84

Subiect și barem · pagina 85

4. Probleme de dificultate crescut˘a
4.1 Din anul 2021
Problema 1
Pe masă este scrisă ecuat, ia a + b = c. După un cutremur masiv, s-au permutat toate cifrele
s, i semnele matematice între ele s, i s-a obt, inut o nouă „ecuat, ie” (evident, gres, ită):
129129851 = 29552 + 1177003
Care ar fi putut fi valoarea init, ială a lui c?
A. 8739191 B. 3001892 C. 3072104 D. 3735094 E. 5790835 F. 7192195 G. 8952530
H. 15038950 I. 15111922 (CORECT) J. 15839920
Explicat, ie:
Pentru a rezolva această problemă cel mai u s, or este să scriem un program care cu un
algoritm de tip backtracking care să încerce toate posibilităt, ile de 3 numere. Pentru
simplitate, vom vrea să facem o permutare a tuturor numerelor, iar între a, b s, i c vom
pune numărul 10 pentru a putea diferent, ia între ele. Fără a pierde generalitatea putem
considera că vectorul reprezintă ecuat, ia în forma a + b = c.
Numărul permutărilor este prea mare, prin urmare vom alege pe rând fiecare răspunsul
s, i vom considera c-ul s, tiut, astfel rămânând mai put, ine cifre de aranjat s, i doar pentru
numerele a s, i b, deci programul va fi mai rapid. În continuare însă programul este mult
prea lent s, i trebuie să mai facem o optimizare. Vom genera numărul a, iar b va fi calculat
ca fiind diferent, a dintre c s, i a. Trebuie să verificăm s, i că numărul b se poate obt, ine.
Vom afi s, a răspunsul −1 dacă c-ul încercat nu este cel corect sau valoarea lui c dacă
acesta este răspunsul corect (frecven t, ele, cât s, i lungimea maximă a numărului a sunt
ajustate pentru răspunsul I).
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int fr[10] = {2, 1, 2, 1, 0, 2, 0, 2, 1, 2};
int v[9];
int ans = -1, c = 15111922, lg_c = 8;
void procesare_solutie(int k)
{
int a = 0, b = 0;
for (int i = 1; i <= k; i++)
a = a * 10 + v[i];
85

Subiect și barem · pagina 86

Probleme de dificultate crescut˘a
b = c - a;
if (b >= 0)
{
// verificăm dacă numărul b se poate obt, ine
int frb[10] = {};
while (b)
{
frb[b % 10]++;
b /= 10;
}
bool ok = true;
for (int i = 0; i <= 9; i++)
ok &= (fr[i] == frb[i]);
if (ok)
ans = c;
}
}
void bkt(int k)
{
for (int i = 0; i <= 9; i++)
if (fr[i] > 0)
{
v[k] = i;
if (k == 0 && i == 0)
continue;
fr[i]--;
procesare_solutie(k);
// lungimea maxima a lui a este lungimea lui c
if (k < lg_c)
bkt(k + 1);
fr[i]++;
}
}
int main()
{
bkt(1);
cout << ans;
return 0;
}
Problema 2
În această problemă ne vom referi la date calendaristice care t, in cont de an, lună, zi, oră s, i minut.
Spunem că o astfel de dată este robustă dacă putem deduce în mod unic la ce dată validă
se referă o mul t, ime de numere, fără să avem coresponden t, a dintre valori s, i câmpurile datei.
Spre exemplu, având valorile {3, 20, 30, 53, 2021} s, tim că nu poate fi vorba decât de
30.03.2021 20 : 53, deci această dată este robustă. Pe de altă parte, data 23.05.2021 20 : 53 nu
este robustă, deoarece mult, imea {5, 20, 23, 53, 2021} poate identifica s, i alte date (de exemplu,
86

Subiect și barem · pagina 87

Concursul MateInfoUB, Sect, iunea Informatic˘a
20.05.2021 23 : 53).
Câte date între 01.01.2021 00 : 00 s, i 31.12.2021 23 : 59 sunt robuste?
O dată este validă dacă ora este în intervalul [0, 23], minutul în [0, 59], luna în [1, 12], iar
ziua în intervalul corespunzător lunii respective conform calendarului anului 2021.
A. 27412 B. 29568 C. 35797 D. 37409 E. 44382 (CORECT) F. 44516 G. 46870
H. 512260 I. 525600 J. 535680
Explicat, ie:
Putem rezolva problema atât matematic, cât s, i prin scrierea unui program care să calculeze
răspunsul. Cu toate acestea, vom prezenta doar varianta a doua, deoarece este considerabil
mai rapidă decât cealaltă s, i pentru că pot apărea mai put, ine erori de rat, ionament.
Avem următoarele condit, ii pentru ca o dată să fie validă:
• ziua este în intervalul [1, a], unde a reprezintă ziua maximă din luna respectivă
• luna este în intervalul [1, 12]
• ora este în intervalul [0, 23]
• minutul este în intervalul [0, 59]
Pentru a verifica dacă o dată este robustă vom crea din ea toate datele posibile. Dacă se
creează o altă dată validă atunci aceasta nu este robustă. O implementare a solut, iei descrise
mai sus în limbajul C++ este următoarea:
int zile_per_luna[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<vector<int>> permutations;
vector<int> v(5);
bool valid(int k)
{
if (k == 1)
return true;
for (int i = 1; i < k; i++)
if (v[i] == v[k])
return false;
return true;
}
void bkt(int k)
{
for (int i = 1; i <= 4; i++)
{
v[k] = i;
if (valid(k))
{
if (k == 4)
permutations.push_back(v);
else
bkt(k + 1);
}
}
}
bool validare_data(int data[5])
{
int zi = data[1], luna = data[2];
87

Subiect și barem · pagina 88

Probleme de dificultate crescut˘a
int ora = data[3], minut = data[4];
return 1 <= luna && luna <= 12 &&
1 <= zi && zi <= zile_per_luna[luna - 1] &&
0 <= ora && ora <= 23 &&
0 <= minut && minut <= 59;
}
bool date_egale(int data[5], int data1[5])
{
bool ok = true;
for (int i = 1; i <= 4; i++)
ok &= (data[i] == data1[i]);
return ok;
}
bool verificare_robust(int data[5])
{
int cnt = 0;
for (int i = 0; i < (int)permutations.size(); i++)
{
int data1[5];
for (int j = 1; j <= 4; j++)
data1[j] = data[permutations[i][j]];
// vrem sa vedem daca data obtinuta este robusta
// totodata, s-ar putea sa generam aceeasi data prin permutari
// daca avem elemente egale
// in acest caz nu vrem sa incrementam contorul
if (validare_data(data1) && !date_egale(data, data1))
cnt++;
}
return cnt == 0;
}
int main()
{
// generam toate permutarile cu 4 elemente
bkt(1);
int ans = 0;
// putem sa nu mai fixam anul,
// deoarece parcurgem doar date din anul 2021
for (int luna = 1; luna <= 12; luna++)
for (int zi = 1; zi <= zile_per_luna[luna - 1]; zi++)
for (int ora = 0; ora <= 23; ora++)
for (int minut = 0; minut <= 59; minut++)
{
int data[5] = {0, zi, luna, ora, minut};
if (verificare_robust(data))
ans++;
}
cout << ans;
return 0;
88

Subiect și barem · pagina 89

Concursul MateInfoUB, Sect, iunea Informatic˘a
}
Observat, ie
Evident, se poate deduce o formulă după care să verificăm dacă o dată este robustă, dar
pot apărea complica t, ii s, i se pot uita cazuri. Prin urmare, cel mai simplu este să verificăm
toate datele pe care le putem forma dintr-o anumită dată.
Problema 3
Considerăm 7 copii (identifica t, i prin numere de la 1 la 7) s, i rela t, iile de prietenie
(bidirect, ionale):
{(1, 2), (4, 5), (4, 6), (6, 7), (7, 2), (4, 2), (3, 1), (5, 6), (4, 3), (3, 2)}
În ziua 0, copilul 5 află de la profesoară un secret (că aceasta vrea să organizeze o onomas-
tică pentru copilul 2 la sfârs, itul celei de-a 4-a zi). În fiecare dintre următoarele 4 zile, se
întâmplă următorul lucru:
Fiecare copil care s, tie secretul îs, i alege exact un prieten aleator (echiprobabil din lista lui
de prieteni) s, i îi comunică secretul (se poate întâmpla ca un copil să comunice secretul de
mai multe ori aceluias, i prieten, în zile diferite).
Astfel, noi copii pot afla secretul, pe care îl vor comunica în continuare începând cu zilele
următoare.
Care este probabilitatea pentru copilul 2 să afle secretul cel târziu la sfâr s, itul celei de-a 4-a zi?
(Aleget, i varianta cea mai apropiată de răspunsul real)
A. 0% B. 26% C. 32% D. 44% E. 58% F. 68% (CORECT) G. 76% H. 85%
I. 94% J. 100%
Explicat, ie:
Graful din enunt, este următorul:
Observat, ie
În reprezentarea grafului am păstrat numerotarea init, ială a prietenilor, în cod însă vom
indexa totul de la 0, astfel copilul i devine copilul i − 1.
Vom construi următoarea dinamică:
89

Subiect și barem · pagina 90

Probleme de dificultate crescut˘a
• d p[i][masca] = probabilitatea ca în ziua i toate nodurile marcate cu 1 în mască să
s, tie secretul (numerotăm bit, ii cu 0 de la dreapta la stânga, iar bitul j corespunde
copilului j)
• pentru a face tranzit, iile între stări vom face un backtracking pentru a genera toate
măs, tile în care putem ajunge, deoarece de la o zi la alta, fiecare copil trebuie să
transmită secretul echiprobabil prietenilor săi (mai multe explicat, ii sunt prezente
sub formă de comentarii în cadrul codului).
• Init, ial, d p[0][16] = 1 (16 = 0010000, masca în care numai nodul 5 s, tie secretul) s, i
d p[i][masca] = 0, ∀(i, masca)̸ = (0, 16)
• Răspunsul va fi suma tuturor valorilor din d p[4][masca], pentru toate măs, tile care au
bitul al 2-lea setat.
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
const int n = 7;
vector<vector<int>> graf(n, vector<int>());
double dp[5][(1 << n)];
void bkt(int zi, int masca_init, int masca_curenta, int copil, double prob)
{
if (copil == n) // am trecut prin toti copiii si deci toti au impartasit secretul unui
dp[zi][masca_curenta] += prob;
else // suntem la copilul copil si vrem sa impartasim secretul unui prieten de-al sau
{
if (masca_init & (1 << copil)) // verificam daca copilul acesta stie secretul
{
prob /= (int)graf[copil].size();
// luam toti prietenii copilului si le spunem "pe rand" secretul
for (int i = 0; i < (int)graf[copil].size(); ++i)
bkt(zi, masca_init, masca_curenta | (1 << graf[copil][i]), copil + 1, prob
}
else // nu stie secretul
bkt(zi, masca_init, masca_curenta, copil + 1, prob);
}
}
int main()
{
// Initializare graf
vector<pair<int, int>> muchii = {{1, 2}, {4, 5}, {4, 6}, {6, 7}, {7, 2}, {4, 2}, {3, 1
for (auto &[a, b] : muchii)
{
a--;
b--;
graf[a].push_back(b);
graf[b].push_back(a);
}
// Copilului 5 ii corespunde bitul 4
dp[0][(1 << 4)] = 1;
90

Subiect și barem · pagina 91

Concursul MateInfoUB, Sect, iunea Informatic˘a
for (int i = 0; i < 4; i++)
for (int masca = 0; masca < (1 << n); masca++)
{
// Daca nu putem ajunge in aceasta configuratie
// nu are sens sa calculam pentru ea
if (dp[i][masca] == 0)
continue;
// backtracking pentru generarea tuturor mastilor viitoare
bkt(i + 1, masca, masca, 0, dp[i][masca]);
}
double ans = 0;
for (int masca = 0; masca < (1 << n); masca++)
if (masca & 2)
ans += dp[4][masca];
cout << ans * 100;
return 0;
}
Problema 4
Compania Grigorescu: Grile, grătare s, i grilaje are 7 angaja t, i. Ziua de mâine are un total de
1440 de minute. Fiecare angajat s, tie exact câte minute poate lucra mâine. Aceste valori
sunt date de s, irul:
480, 360, 333, 1000, 285, 560, 15
Un angajat care poate lucra X minute poate alege orice interval continuu de X minute care
începe la minut fix s, i este inclus complet în cele 1440 de minute ale zilei. Angajat, ii vor să- s, i
coordoneze alegerile astfel încât oricare doi dintre ei să aibă cel pu t, in un minut comun în
program. Câte configurat, ii de alegeri satisfac această cerint, ă? Răspunsul este foarte mare,
deci suntem interesat, i de restul acestui număr la împărt, irea cu 1 000 000 007.
O configura t, ie A diferă de o configura t, ie B dacă există cel pu t, in un angajat care s, i-a ales un
anumit interval în A s, i un interval diferit în B.
A. 82930407 B. 195773645 (CORECT) C. 231919841 D. 353129100 E. 371820425
F. 469187746 G. 715377483 H. 67843200 I. 802170567 J. 918401827
Explicat, ie:
Pentru a număra în câte configura t, ii tot, i angaja t, ii se suprapun în cel put, in un minut, vom
fixa pe rând primul minut când se suprapun. Pentru un minut fixat vom calcula numărul
de configura t, ii care au cel pu t, in un interval care începe în acel minut. Acest număr se
poate calcula us, or în felul următor: calculăm toate posibilităt, ile de a a s, eza intervalele, din
care scădem opt, iunile unde niciun interval nu începe fix în acel minut.
Pentru a afla numărul total, vom calcula pentru fiecare valoare în parte câte intervale
care cont, in acest minut poate forma. Pentru o valoare v, un interval poate începe la orice
minut din intervalul [1, 1440 − v + 1]. Pentru un minut X s, i o valoare v, numărul de intervale
de lungime v care cont, in minutul X este max(0, min(1440 − v + 1, X) − max(1, X − v + 1) + 1).
Pentru a afla câte opt, iuni nu au niciun interval care să înceapă fix în acel minut, calculăm
în câte moduri putem acoperi intervalul [X-1, X], unde X este momentul actual. Pentru o
valoare v trebuie să alegem un interval de forma [s, s + v − 1] astfel încât X − 1 ≥ s s, i X ≤
s + v − 1. Prin urmare, s trebuie să satisfacă max(1, X − v + 1) ≤ s ≤ min(1440 − v + 1, X − 1).
91

Subiect și barem · pagina 92

Probleme de dificultate crescut˘a
Acest număr se calculează cu formula următoare max(0, min(1440−v+1, X −1)−max(1, X −
v + 1) + 1).
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int main()
{
const int MOD = 1e9 + 7;
int v[7] = {480, 360, 333, 1000, 285, 560, 15};
long long ans = 0;
for (int i = 1; i <= 1440; i++)
{
long long total = 1, descazut = 1;
for (int j = 0; j < 7; j++)
{
total = (total
* max(0, min(1440 - v[j] + 1, i) - max(1, i - v[j] + 1) + 1)) % MOD;
descazut = (descazut
* max(0, min(1440 - v[j] + 1, i - 1) - max(1, i - v[j] + 1) + 1)) % MOD;
}
ans = (ans + (total - descazut + MOD)) % MOD;
}
cout << ans;
return 0;
}
4.2 Din anul 2022
Problema 1
Considerăm funct, ia:
const int kLim = 1000000;
void fun(int a, int b, int c) {
if(a > kLim || b > kLim || c > kLim) {
return;
}
if(a != c && b != c) {
cout << c << "\n";
}
fun(a + 1, b, c + b);
fun(a, b + 1, c + a);
}
Care dintre următoarele numere va fi afi s, at la un moment dat ca urmare a apelului ‘fun(0,
0, 0)‘?
A. 361 (CORECT) B. 5051 C. 1787 D. 53411 E. 41
Explicat, ie:
La o analiză a func t, iei observăm că mereu valoarea c = a · b. Ca să demonstrăm acest lucru,
presupunem că suntem într-un stadiu f (a, b, c), unde c = a · b. De aici, funct, ia se ramifică
în felul următor:
92

Subiect și barem · pagina 93

Concursul MateInfoUB, Sect, iunea Informatic˘a
• Odată apelăm f (a + 1, b, c + b) s, i considerăm noul produs. Observăm că (a + 1) · b =
a · b + b = c + b, s, i noi cres, tem c-ul cu b, prin urmare relat, ia c = a · b se ment, ine.
• La apelul f (a, b + 1, c + a), produsul devine a · (b + 1) = a · b + a = c + a din nou cre s, tem
c-ul cu a s, i relat, ia noastră c = a · b se ment, ine.
Deoarece din orice stadiu în care c = a · b vom merge doar într-un stadiu unde c = a · b, iar
stadiul nostru init, ial respectă această relat, ie, mereu aceasta va rămâne adevărată.
Acum vom analiza condit, ia de afi s, are. În această funct, ie, valoarea c trebuie să fie diferită
de a s, i b. Deoarece c = a · b, acest lucru este echivalent cu a̸ = 1 s, i b̸ = 1. Deoarece c în
momentul afis, ării este produsul a două numere diferite de 1, c trebuie să fie un număr
compus, prin urmare c nu poate să fie prim.
O altă modalitate de a observa această relat, ie este de a mics, ora kLim s, i a vedea ce valori
sunt afis, ate. Vom observa că nu ne afis, ează numere prime.
Deoarece func t, ia ne afis, ează doar numere compuse s, i 361 este singurul număr compus,
devine evident că A este varianta corectă.
Problema 2
Avem 10 bet, e de lungimile: 3, 4, 5, 8, 10, 12, 14, 32, 57, 64.
Vrem să folosim unele dintre aceste be t, e (posibil toate) pentru a construi conturul unui
triunghi (punând bet, ele cap la cap). Pentru fiecare latură a triunghiului, putem folosi unul
sau mai multe bet, e. Triunghiul trebuie să aibă aria strict pozitivă.
Câte arii distincte posibile poate avea un asemenea triunghi?
A. 8193 B. 22 C. 55558 D. 11495 E. 105693 F. 234126 G. 17293
H. 16639 (CORECT) I. 132 J. 49763
Explicat, ie:
Pentru început, nu este fezabil să calculăm acest număr fără un instrument algoritmic, a s, a
că vom încerca să construim un algoritm care să rezolve problema.
Primul pas necesar pentru a rezolva problema este să formăm muchii folosind be t, ele.
În continuare, vom prezenta o metodă bazată pe backtracking pentru a genera toate
împărt, irile posibile ale be t, elor în trei muchii. Vom atribui fiecărui băt, un număr 0, 1, 2 sau
3:
• 0 reprezintă că băt, ul nu participă la formarea niciunei muchii,
• 1 indică faptul că băt, ul participă la formarea muchiei 1,
• 2 indică participarea la muchia 2,
• 3 indică participarea la muchia 3.
Astfel, mai este necesar doar să generăm to t, i vectorii de lungime 10, ale căror elemente
iau valori cuprinse între 0 s, i 3. Apoi, ne interesează doar lungimile acestor muchii. Prin
urmare, muchia i va avea lungimea egală cu suma lungimilor tuturor bet, elor cărora le-a
fost atribuit i în acest array.
Odată ce am împărt, it be t, ele în muchii, trebuie să determinăm care combina t, ii de trei
93

Subiect și barem · pagina 94

Probleme de dificultate crescut˘a
muchii produc o solut, ie validă, adică formează un triunghi cu arie strict pozitivă. Pentru
ca trei laturi de lungimi a, b, c să formeze un triunghi, este necesar ca următoarele relat, ii să
fie îndeplinite:
• a < b + c
• b < a + c
• c < a + b
Acum mai este necesar să calculăm aria pentru triunghiurile care respectă relat, iile de mai
sus. Putem face acest lucru folosind formula lui Heron: pentru un triunghi cu laturi de
lungimi a, b s, i c, aria este dată de:
Aria = pp · (p − a) · (p − b) · (p − c)
unde p este semi-perimetrul definit ca:
p = a + b + c
2
În final, trebuie doar să numărăm câte arii distincte ob t, inem. Pentru a evita erorile de
aproximare la compararea numerelor, vom considera valoarea ariei la pătrat, astfel încât să
eliminăm radicalul. Chiar dacă vom efectua calcule cu valori zecimale, termeni pe care
îi înmult, im vor avea cel mult .5 după virgulă, deoarece împărt, im doar p, care este un
număr întreg, la 2. Prin urmare, aceste numere pot fi reprezentate fără aproximări în calcule.
O implementare a solut, iei descrise mai sus în limbajul C++ este următoarea:
int bete[] = {3, 4, 5, 8, 10, 12, 14, 32, 57, 64};
int a[10];
map<double, int> mp;
void mapeazaAria(int a, int b, int c) {
double p = a + b + c;
p /= 2;
double arie = p * (p - a) * (p - b) * (p - c);
mp[arie] = 1;
}
void verifica() {
int m1 = 0, m2 = 0, m3 = 0;
for(int i = 0; i < 10; i++) {
if(a[i] == 1) m1 += bete[i];
if(a[i] == 2) m2 += bete[i];
if(a[i] == 3) m3 += bete[i];
}
if(m1 < m2 + m3 && m2 < m1 + m3 && m3 < m1 + m2) mapeazaAria(m1, m2, m3);
}
void genereazaMuchii(int n) {
for(int i = 0; i <= 3; i++) {
a[n] = i;
if(n == 9) verifica();
94

Subiect și barem · pagina 95

Concursul MateInfoUB, Sect, iunea Informatic˘a
else genereazaMuchii(n + 1);
}
}
În func t, ia genereazaMuchii() vom genera toate împărt, irile în muchii descrise mai sus,
urmând să rulăm o verificare. Dacă condit, iile lungimilor sunt îndeplinite, putem mapa
aria. Pentru acest lucru, folosim structura map din C++. Această structură ne permite să
atribuim unei chei o valoare s, i ret, ine perechi de tip cheie-valoare folosind un arbore de
căutare, având complexitate O(log n) pentru căutarea sau adăugarea unei chei, unde n este
numărul de chei prezente în mapă. Astfel, pentru fiecare arie, marcăm faptul că aceasta
apare. Tot ce trebuie să facem este să apelăm genereazaMuchii(0) s, i să afis, ăm mp.size(),
această metodă returnând numărul de chei prezente într-o mapă.
Complexitatea totală de timp va fi O(n · 22n), deoarece complexitatea mapei este log2(22n),
care este 2n, astfel încât aceasta nu cres, te complexitatea teoretică de timp.
La final, ne este afis, at rezultatul 16639, care este s, i răspunsul corect. Prin urmare, varianta
H este corectă.
Problema 3
Fie S suma tuturor elementelor tuturor submult, imilor cu 617 elemente ale mult, imii
{1, 2, 3, . . . , 1234}. Câte cifre are S?
A. 325 B. 376 (CORECT) C. 392 D. 404 E. 415 F. 427 G. 440 H. 455 I. 467
J. 489
Explicat, ie:
Pentru început, numărul de submul t, imi este foarte mare, prin urmare un calcul direct
este dificil. În schimb, putem observa că o submul t, ime are suma cuprinsă între 190653 s, i
761995, prin urmare are 6 cifre.
A doua observat, ie care ne interesează este să aflăm câte cifre va avea numărul de submult, imi.
Vom avea 1234
617

 submul t, imi, iar acest lucru poate fi determinat folosind o resursă online,
precum aceasta. Aici ni se oferă reprezentarea s, tiin t, ifică a rezultatului, în cazul în care
acesta este prea mare. Astfel, putem afla că valoarea căutată are 369 de cifre.
De altfel, putem scrie cod pentru a calcula această valoare. De s, i limbajul C++ nu este
recomandat, deoarece ar trebui să efectuăm calcule pe numere mari, inclusiv împăr t, iri care
sunt dificile, limbajul Python ne oferă o alternativă foarte bună. După cum vom vedea, în
a doua modalitate de a rezolva problema.
Acum mai trebuie să facem observat, ia că un număr x cu a cifre, înmult, it cu un număr y
cu b cifre, va avea mereu a + b sau a + b + 1 cifre. Putem demonstra acest lucru folosind
reprezentarea s, tiint, ifică a unui număr. Pentru un număr x cu a cifre, putem să-l scriem ca
x = u · 10a, unde u este un număr cu o cifră înainte de virgulă.
De asemenea, putem scrie y, care are b cifre, sub forma: y = w ·10b. Astfel, x ·y = u ·w ·10(a+b).
Cum u · w este un număr mai mic decât 100, acesta poate adăuga cel mult o cifră în plus.
Acum s, tim că suma S va avea fie 375, fie 376 cifre. Deoarece 376 este singura op t, iune
posibilă, rezultă că varianta B este corectă.
95

Subiect și barem · pagina 96

Probleme de dificultate crescut˘a
O altă modalitate care ne permite să calculăm suma S exact este următoarea, pentru
început, ne interesează în câte submul t, imi apare fiecare număr de la 1 la 1234. Acest lucru
este echivalent cu a fixa un număr i s, i a alege încă 616 numere din 1233, astfel putem
reduce suma S la:
S =
1234
∑
i=1
i ·
1233
616

= 617 · 1235 ·
1233
616

unde 1233
616

 reprezintă combinări de 1233 luate câte 616.
Acum putem calcula această valoare cu us, urin t, ă în limbajul Python. Este o op t, iune bună
deoarece ne permite să lucrăm cu numere arbitrar de mari, fără riscul de a produce
overflow, deoarece limbajul se ocupă automat de toată logica necesară. O implementare în
Python este următoarea:
import math
def combination(n, k):
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
val = 617 * 1234 * combination(1234, 616)
ans = 0
while val != 0:
ans += 1
val //= 10
print(ans)
Pentru început, importăm modulul math, care ne permite să calculăm factorialul unui
număr. Apoi, vom calcula valoarea sumei S, urmând să determinăm câte cifre are aceasta.
Programul returnează valoarea 376, care este s, i răspunsul corect, prin urmare varianta B
este corectă.
Problema 4
Alex are vedenii. Cum stă pe Facebook să citească update-uri de la prieteni în loc să învet, e
pentru examenul de mâine, acesta începe să vadă cuvântul "picat" printre postări.
Dat fiind un s, ir de caractere s format din literele mici ale alfabetului englez (fără diacritice)
s, i semne de punctua t, ie, reprezentând o postare, o apari t, ie a cuvântului "picat" este
determinată de numerele a1 < a2 < a3 < a4 < a5, astfel încât:
• s[a1] = p
• s[a2] = i
• s[a3] = c
• s[a4] = a
• s[a5] = t
Două apari t, ii se consideră diferite dacă cel put, in unul dintre numerele a1, a2, a3, a4 sau a5
este diferit în cele două aparit, ii. Alex tocmai a citit următoarea postare:
azi am putut în sfârs, it ca din întâmplare sa vizitez muzeul cunoscut al satului: când am păs, it acolo
am simt, it ca totul este minunat.
96

Subiect și barem · pagina 97

Concursul MateInfoUB, Sect, iunea Informatic˘a
Câte aparit, ii ale cuvântului "picat" există în această postare?
A. 665 B. 714 C. 1923 D. 2154 E. 1315 F. 1276 G. 956 H. 1672 (CORECT)
I. 1024 J. 1948
Explicat, ie:
Din valorile mari ale variantelor de răspuns, observăm că un calcul fără un instrument
algoritmic nu este fezabil. Prin urmare, vom scrie un scurt fragment de cod pentru a
rezolva problema.
Pentru început, o solut, ie bazată pe backtracking este prea lentă din cauza lungimii mari a
s, irului. În schimb, vom construi o solut, ie bazată pe programare dinamică în felul următor.
Fie două s, iruri s s, i t trebuie să determinăm toate aparit, iile lui t în s, exact ca în enunt, . Vom
defini funct, ia d p(i, j), unde aceasta reprezintă în câte moduri putem forma prefixul lui t
de lungime j, folosind primele i caractere ale lui s. Init, ial, avem d p(0, 0) = 1, iar tranzit, iile
sunt următoarele:
d p(i, j) =



d p(i − 1, j) + d p(i − 1, j − 1) dacă s[i] = t[ j],
d p(i − 1, j) altfel.
Prima tranzit, ie creează noi solu t, ii folosind al i-lea caracter din s, iar a doua copiază solut, iile
obt, inute la pasul anterior.
Acum va trebui să implementăm programarea dinamică descrisă mai sus s, i să o rulăm
pentru s s, i t din enunt, . O implementare în limbajul C++ este următoarea:
int getAns() {
string s = "$azi am putut in sfarsit ca din intamplare sa vizitez muzeul \
cunoscut al satului: cand am pasit acolo am simtit ca totul este minunat.";
string t = "$picat";
int n = s.length(), m = t.length();
int dp[n + 5][m + 5];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
dp[i][j] += dp[i - 1][j];
if(j > 0 && s[i] == t[j]) dp[i][j] += dp[i - 1][j - 1];
}
}
return dp[n][m];
}
Func t, ia getAns() începe prin init, ializarea s, irurilor s s, i t. Vom adăuga un caracter $ la
început, pentru ca acestea să fie indexate de la 1. Apoi, ini t, ializăm valorile d p cu 0 s, i
setăm d p[0][0] = 1. Parcurgem tranzit, iile descrise mai sus s, i returnăm d p[n][m], unde n este
lungimea lui s, iar m este lungimea lui t.
Func t, ia returnează valoarea 1672, care este s, i răspunsul corect. Prin urmare, varianta H
este corectă.
97

Subiect și barem · pagina 98

Probleme de dificultate crescut˘a
Problema 5
Alex întâlnes, te doi oameni. Pe unul dintre cei doi îl cheamă Matei. Alex s, tie acest lucru,
dar nu s, tie pe care dintre ei îl cheamă Matei. De asemenea, unul dintre cei doi spune
mereu adevărul s, i celălalt minte mereu. Alex s, tie s, i el lucrul acesta, dar, din nou, nu s, tie
cine minte s, i cine spune adevărul.
Alex are în minte 5 întrebări pe care vrea să le folosească pentru a afla dacă Matei minte
sau nu:
1. Matei minte?
2. Es, ti Matei?
3. Ce ar spune celălalt dacă l-as, întreba dacă Matei minte?
4. Ce ai spune dacă te-as, întreba dacă Matei minte?
5. Este adevărat că 1 + 1 = 2?
Alex dores, te să pună exact o întrebare dintre cele 5 pentru a-l identifica pe Matei. Pe care
dintre cele 5 întrebări le poate folosi?
A. întrebarea 1
B. întrebările 1 s, i 5
C. întrebarea 2
D. întrebările 1 s, i 4
E. întrebările 2, 3 s, i 4 (CORECT)
Explicat, ie:
Vom analiza pe rând întrebările:
• Dacă vom adresa prima întrebare, indiferent dacă Matei minte sau nu, vom primi un
"Da" s, i un "Nu" ca răspuns. Prin urmare, această întrebare nu ne ajută cu nimic.
• La a doua întrebare, dacă Matei minte, vom primi ca răspuns "Nu" de la ambele
persoane. În schimb, dacă Matei nu minte, vom primi "Da" de la ambele persoane.
Prin urmare, această întrebare ne permite să determinăm dacă Matei minte sau nu.
• Când întrebăm "Matei minte?", dacă Matei minte, el va răspunde cu "Nu", iar cealaltă
persoană cu "Da". Apoi, când întrebăm ce ar spune celălalt, Matei va răspunde "Nu",
iar a doua persoană va răspunde tot "Nu". Dacă Matei nu minte, el ar spune "Nu",
iar cealaltă persoană "Da". Când sunt întreba t, i ce ar spune celălalt, acest caz se
transformă în "Da" s, i "Da". Prin urmare, s, i cu această întrebare putem determina
dacă Matei minte.
• La a patra întrebare, când Matei minte, răspunsurile "Nu" s, i "Da" de la întrebarea
"Matei minte?" sunt transformate în "Da" s, i "Da". În schimb, dacă Matei nu minte,
răspunsurile devin "Nu" s, i "Nu". Astfel, s, i această întrebare permite să facem
distinct, ia.
• Cât despre a cincea întrebare, indiferent dacă Matei minte sau nu, vom primi ca
răspuns un "Da" s, i un "Nu". Acest lucru este din nou inutil.
În concluzie, cu ajutorul întrebărilor 2, 3 s, i 4, putem face distinct, ia dacă Matei minte
sau nu. Prin urmare, răspunsul corect este E.
Problema 6
Care va fi output-ul următoarei secvent, e de cod la apelul funct, iei g()?
long long f(long long a, long long b) {
if (a == 0)
return 0;
else if (a & 1)
98

Subiect și barem · pagina 99

Concursul MateInfoUB, Sect, iunea Informatic˘a
return (b + f(a ^ 1, b)) % 137;
else
return f(a >> 1, b << 1);
}
void g() {
long long suma = 0;
for (long long i = 0; i < 2LL * 1000LL * 1000LL * 1000LL; i++) {
suma += f(i, i);
suma %= 137;
}
cout << "Suma este " << suma << '\n';
}
A. Suma este 0
B. Suma este 1
C. Suma este 4 (CORECT)
D. Suma este 8
E. Suma este 16
F. Suma este 32
G. Suma este 64
H. Suma este 128
I. Suma este 256
J. Suma este 512
Explicat, ie:
Pentru moment, vom ignora operat, ia de modulo 137. Analizând func t, ia f , observăm
că, dacă cel mai nesemnificativ bit din variabila a este 1, vom adăuga valoarea lui b la
rezultatul final. Ulterior, vom executa f (a ⊕ 1, b), ceea ce face ca a să devină par.
În cazul în care a este par, observăm că îl împărt, im la 2, efectuat printr-un shift la dreapta,
ceea ce ne mută la bitul următor. În acela s, i timp, înmul t, im valoarea lui b cu 2. Astfel,
deducem că valoarea lui b va fi mereu egală cu valoarea ini t, ială a lui b, înmult, ită cu
valoarea bitului curent al lui a.
Combinând aceste cazuri, concluzionăm că funct, ia f realizează o înmult, ire a parametrilor
a s, i b, toate opera t, iile fiind efectuate modulo 137. Trecând la analiza func t, iei g, este evident
că aceasta calculează suma pătratelor numerelor de la 0 la 1999999999.
Avem următoarele trei opt, iuni:
• Prima op t, iune: Copiem funct, ia f într-un mod naiv. Este mult mai simplu să
observăm că func t, ia f are complexitate O(log(n)). De s, i această implementare ar rula
mai încet, execu t, ia ei s-ar încheia în câteva minute. Aceasta este o solu t, ie naivă,
utilă în cazul în care nu observăm explicit ce face funct, ia f , dar care poate rezolva
problema.
• A doua op t, iune: Înlocuim linia "suma += f(i, i);" cu "suma += i * i;". Astfel, execut, ia
devine mult mai rapidă, deoarece nu mai apelăm funct, ia f , economisind un log(n).
Aceasta este o solu t, ie mult mai rapidă s, i mai sigură decât a treia, des, i nu este optimă
din punct de vedere al timpului.
• A treia opt, iune: Utilizăm formula sumei pătratelor, anume:
n
∑
i=0
i2 = n · (n + 1) · (2n + 1)
6 .
99

Subiect și barem · pagina 100

Probleme de dificultate crescut˘a
Trebuie să fim atent, i la împăr t, irile cu 2 s, i 3(factorii primi ai lui 6) pentru a evita
erorile de calcul, obt, inând astfel răspunsul în complexitate O(1), o implementare în
limbajul C++ este următoarea:
int getAns() {
long long n = 1999999999;
long long term1 = n, term2 = n + 1, term3 = 2 * n + 1;
if(n % 2 == 0) term1 /= 2;
else term2 /= 2;
if(term1 % 3 == 0) term1 /= 3;
else if(term2 % 3 == 0) term1 /= 3;
else term3 /= 3;
return (((term1 * term2) % 137) * term3) % 137;
}
Oricare dintre cele trei opt, iuni va returna rezultatul 4. Prin urmare, răspunsul corect este
C.
Problema 7
Ema are 22 de cuburi astfel: 7 verzi, 8 albastre s, i 7 ro s, ii. Ea ar vrea să vadă câte turnulet, e
poate forma cu ele fără ca un cub verde să fie plasat imediat peste un cub ros, u.
În câte moduri diferite poate construi turnule t, e de acest tip folosind toate cuburile? Două
moduri sunt considerate diferite dacă s, irurile de culori, citite de la primul cub de jos, sunt
diferite.
A. 23519245 B. 1097450640 C. 41409225 (CORECT) D. 37268302 E. 10803075
F. 194276877 G. 298507535 H. 107567859 I. 251890065 J. 462058202
Explicat, ie:
Pentru început, nu avem o metodă us, oară de a calcula valoarea cerută folosind combina-
torică, a s, a că este necesar să scriem cod. Observăm că varianta de răspuns cu valoarea
maximă este 1.097.450.640, ceea ce nu reprezintă un număr extrem de mare. Acest lucru
sugerează că, dacă am construi o solu t, ie bazată pe backtracking, aceasta ar rula destul de
rapid.
O posibilă idee de backtracking ar fi să definim o funct, ie care t, ine evident, a numărului de
cuburi ros, ii, verzi s, i albastre rămase. De asemenea, ne interesează s, i culoarea ultimului
cub plasat.
Fie f (v, a, r, u), unde:
• v reprezintă numărul de cuburi verzi rămase,
• a reprezintă numărul de cuburi albastre rămase,
• r reprezintă numărul de cuburi ros, ii rămase,
• u reprezintă culoarea ultimului cub plasat.
Putem avansa în următoarele moduri:
• Dacă ultimul cub plasat nu este ros, u s, i avem cuburi verzi disponibile (v > 0), apelăm
f (v − 1, a, r, verde).
100