Concursul MateInfoUB 2021, sect, iunea Informatică

23 Mai 2021

Concursul constă în obt, inerea unui punctaj cât mai mare prin rezolvarea celor 20 de probleme propuse.
Fiecare problemă are un punctaj corespunzător gradului ei de dificultate. Cel mai probabil, nu vet, i avea
suficient timp să rezolvat, i toate problemele.

1 Probleme de dificultate scăzută

Problema 1
(2 puncte) Care este ultima cifră a celui mai mare număr de 7 cifre, divizibil cu 7, care cont, ine în
component, a sa doar cifre strict mai mici decât 7?
A. 0
B. 2
C. 3
D. 5
E. 6

Problema 2
(2 puncte) Care expresie implementează corect d nk e pentru toate perechile n, k de numere naturale
nenule? (dae reprezintă partea întreagă superioară a numărului real a, spre exemplu d2.8e = 3, n
**div** k reprezintă câtul împărt, irii lui n la k s, i n **mod** k reprezintă restul împârt, irii lui n la k).
A. n **div** k
B. (n + k) **div** k
C. (n + k − 1) **div** k
D. n **div** (k − 1)
E. (n **div** k) + (n **mod** k)

Problema 3
(2 puncte) Considerăm următorul cod scris în limbajul C++ / Pascal:

1
 Type MyArray = array [ 0 . . 9 9 9 9 ] of Integer ;

int f ( int t [ 1 0 0 0 0 ] , int n ) { function f ( t : MyArray ; n : Integer ) : Integer ;

int i = 0 , s = 0 ; var i , s , j : Integer ;
while ( i < n ) { begin
int j = i + 1 ; i := 0 ; s := 0 ;
while ( j < n && t [ i ] == t [ j ] ) while i < n do begin
j += 1 ; j := i + 1 ;
s += 1 ; while ( j < n ) and ( t [ i ] = t [ j ] ) do
i = j; j := j + 1 ;
} s := s + 1 ;
return s ; i := j ;
} end ;
f := s ;
end ;

Definit, ii: O subsecvent, ă a lui t este o listă de valori aflate pe pozit, ii consecutive crescătoare, e.g.,
[t[3], t[4], t[5]]. Un subs, ir al lui t este o listă de valori aflate pe pozit, ii ordonate crescător (nu neapărat
consecutive), e.g., [t[3], t[5], t[9]].
Presupunând că tabloul t este format din n numere ordonate crescător, precizat, i ce returnează f(t,
n):
A. numărul valorilor distincte din tabloul t
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 subşir din tabloul t format din valori egale
E. numărul valorilor care se repetă de cel put, in două ori din tabloul t

Problema 4
( 2 puncte) Într-o sală de conferint, e sunt mai multe persoane, fiecare având o rezervă suficient de mare
de cârt, i de vizită. S, tiind că oricare două persoane pot să facă schimb de cărt, i de vizită cel mult o dată
s, i s-au efectuat 23052021 de schimburi, care este numărul minim de persoane care se pot afla în sală?
A. 4801
B. 4802
C. 4803
D. 6790
E. 6791

Problema 5
(2 puncte) Pentru un graf G, un arbore part, ial este un graf conex, fără cicluri, cont, inând acelas, 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 :

2
A. 12
B. 11
C. 9
D. 15
E. 16

Problema 6
(2 puncte) 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 lui X la
împărt, irea cu 37?
A. 36
B. 4
C. 1
D. 35
E. 25

Problema 7
(2 puncte) Se dă următoarea adunare ERAM + M ARE = M ARET , 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
E. 30

Problema 8
(2 puncte) 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
D. 56
E. 62

3
Problema 9
(2 puncte) O mult, ime de numere naturale se numes, te 13-liberă dacă nu putem obt, ine numărul 13 ca
sumă a unor elemente distincte din mult, ime. Spre exemplu, mult, imea 1, 5, 7, 11 nu este 13-liberă fiindcă
1 + 5 + 7 = 13, dar mult, imea 1, 5, 6 este 13-liberă (notat, i că des, i 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
B. 4
C. 3
D. 6
E. 8

Problema 10
(2 puncte) 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
E. 31

4
2 Probleme de dificultate medie

Problema 11
(3 puncte) Vă amintit, i de Cristian cel neastâmpărat? Tatăl lui s-a hotărât să îl învet, e put, 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 secvent, ă de pas, 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
C. 66
D. 67
E. 68

Problema 12
(3 puncte) 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ă 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
C. 95
D. 96
E. 97

Problema 13
(3 puncte) 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 21 20
22 22 23 24 25 26 27
......................................................

Pentru un anumit nivel k, vrem să calculăm suma numerelor din interiorul tringhiului care se opres, te
la nivelul k. Spre exemplu, pentru nivelul k = 5 numerele din interiorul triunghiului creat sunt 5, 8, 9,

5
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 s, i 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
C. 2080520640767
D. 2084643884965
E. 2084643884966

Problema 14
(2 puncte) 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 cont, ine valoarea 0). Matricea se poate vizualiza aici: [Link]
(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
E. 3039

Problema 15
(3 puncte) Considerăm următorul algoritm de acoperire a unei sume de bani, folosind bancnotele disponi-
bile î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 solut, 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). Totus, i, există solut, ia {4, 5} care acoperă complet suma. Numim o astfel de
configurat, ie 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}. 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
D. 18
E. 23

6
Problema 16
(3 puncte) Câte dreptunghiuri distincte sunt în figura următoare?

+------+---+---+---+---+
| | | | | |
+--+---+ +---+ | |
| | | | | | |
+--+---+---+---+---+ |
| | | | |
+--+---+---+---+---+---+
| | | | |
+------+---+---+-------+

A. 43
B. 44
C. 45
D. 46
E. 47

7
3 Probleme de dificultate ridicată

Problema 17
(5 puncte) 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
J. 15839920

Problema 18
(5 puncte) În această problemă ne vom referi la date calendaristice care t, in cont de an, lună, zi, ora s, i
minut.
Spunem că o astfel de dată este robustă dacă putem deduce în mod unic la ce dată validă se referă o
mult, ime de numere, fără să s, tim corespondent, 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, 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], ziua în intervalul
corespunzator lunii respective conform calendarului anului 2021.
A. 27412
B. 29568
C. 35797
D. 37409
E. 44382
F. 44516
G. 46870
H. 512260
I. 525600
J. 535680

Problema 19
(5 puncte) Considerăm 7 copii (identificat, i prin numere de la 1 la 7) s, i relat, 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)}

8
În ziua 0, copilul 5 află de la profesoară un secret (că aceasta vrea să organizeze o onomastică 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ă s, i lui 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ârs, 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%
G. 76%
H. 85%
I. 94%
J. 100%

Problema 20
(5 puncte) Compania Grigorescu: Grile, grătare s, i grilaje are 7 angajat, 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 in cele 1440 de minute ale zilei. Angajat, ii vor să-s, i coordoneze alegerile
astfel încât oricare doi dintre ei să aibă cel put, 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 configurat, ie A diferă de o configurat, ie B dacă există cel put, in un angajat care s, i-a ales un anumit
interval în A s, i un interval diferit în B.
A. 82930407
B. 195773645
C. 231919841
D. 353129100
E. 371820425
F. 469187746
G. 715377483
H. 67843200
I. 802170567
J. 918401827