Pregătire cu un profesor

MateInfoUB
20 Mai 2023
Facultatea de Matematicˇa-Informaticˇa
Agar
Runda Finalˇa
Romˆanˇa (Oficial)
Agar
ˆIntr-un agar se afl˘a n microbi. Fiecare microb poate fi caracterizat prin indexul s˘au i (0 ≤ i < n)
s, i puterea sa pi.
Un microb i poate mˆanca microbul j dac˘a s, i numai dac˘a:
• Cei doi microbi sunt diferit, i: i̸ = j.
• Microbul i este cel put, in la fel de puternic ca microbul j: pi ≥ pj .
• Microbul i nu are o putere mai mare de dublul puterii microbului j (nici ˆın lumea micro-
bilor nu este frumos ca cei puternici s˘a ˆıi atace pe cei slabi): pi ≤ 2pj .
De exemplu, un microb cu puterea 9 poate mˆanca un microb cu puterea ˆıntre 5 s, i 9 s, i poate fi
mˆancat de un microb cu puterea ˆıntre 9 s, i 18.
O mult, ime de microbi se numes, te anihilatoare dac˘a este posibil ca microbii s˘a se m˘anˆance ˆıntre
ei astfel ˆıncˆat s˘a r˘amˆan˘a un singur microb.
Atent, ie: O secvent, ˘a este anihilatoare dac˘a exist˘a CEL PUT, IN un scenariu ˆın care microbii
se m˘anˆanc˘a ˆıntre ei pˆan˘a r˘amˆane unul singur. De exemplu, mult, imea de microbi cu puterile 3,
7 s, i 4 este anihilatoare, pe cˆand mult, imea de microbi cu puterile 3 s, i 7 nu este.
Oamenii de s, tiint, ˘a vor s˘a efectueze m diferite experimente asupra microbilor, s, i consider˘a
diferite scenarii, fiecare scenariu fiind caracterizat de doi indici a s, i b (0 ≤ a ≤ b < n). Pentru
un scenariu particular (a, b), oamenii de s, tiint, ˘a izoleaz˘a tot, i microbii cu indice i cuprins ˆıntre
a s, i b (inclusiv), urmˆand s˘a testeze dac˘a mult, imea izolat˘a de microbi este anihilatoare.
Atent, ie: Cele m scenarii sunt pur teoretice s, i nu se influent, eaz˘a unul pe altul. Astfel, putet, i
considera c˘a pentru fiecare scenariu tot, i virus, ii sunt ˆınc˘a ˆın viat, ˘a.
Date de Intrare
Pe prima linie se dau numerele n s, i m, care reprezint˘a num˘arul de microbi, respectiv num˘arul de
scenarii pe care le consider˘a oamenii de s, tiint, ˘a. Urm˘atoarea linie cont, ine n numere p0, p1, ..., pn−1.
Urm˘atoarele m linii cont, in cˆate dou˘a numere a s, i b, care reprezint˘a parametrii scenariilor.
Date de Ies, ire
Pentru fiecare din cele m experimente, s˘a se afis, eze cˆate o linie care s˘a cont, in˘a ”DA” dac˘a
secvent, a este anihilatoare s, i ”NU” ˆın caz contrar.
Constrˆangeri
• 1 ≤ n, m ≤ 105.
• 1 ≤ pi ≤ 105, pentru orice 0 ≤ i < n.
1 of 2

Subiect · pagina 2

Subtask-uri
1. (20 de puncte) 1 ≤ n, m ≤ 1000.
2. (20 de puncte) 1 ≤ pi ≤ 32, pentru orice 0 ≤ i < n.
3. (50 de puncte) Toate scenariile au a = 0. Altfel spus, intervalele alese de oamenii de
s, tiint, ˘a sunt prefixe.
4. (10 puncte) Nicio constrˆangere suplimentar˘a.
Exemplu
Input Standard (cin) Output Standard (cout)
3 3
3 7 4
0 1
0 2
1 2
NU
DA
DA
5 5
5 2 4 11 10
0 0
0 1
0 2
0 3
0 4
DA
NU
DA
NU
DA
2 of 2

Subiect · pagina 3

MateInfoUB
20 Mai 2023
Facultatea de Matematicˇa-Informaticˇa
Cadouri
Runda Finalˇa
Romˆanˇa (Oficial)
Cadouri
Cei n copii din clasa lui Matei organizeaz˘a o serbare de Cr˘aciun. Unii copii au fost deosebit de
mult ajutat, i de alt, i copii pentru teme, as, a c˘a doresc s˘a ˆıi mult, umeasc˘a oferindu-le cadouri.
Mai concret, un copil i (0 ≤ i < n) va face una din urm˘atoarele dou˘a act, iuni:
• Va veni cu mˆainile in buzunar, f˘ar˘a s˘a aduc˘a niciun cadou.
• Cum a fost deosebit de mult ajutat de un coleg, ˆıi va oferi un cadou.
Pentru a reprezenta situat, ia din clas˘a, notam vi = j dac˘a copilul i ˆıi aduce un cadou copilului
j. Dac˘a un copil i nu aduce niciun cadou, atunci vi = −1. Evident, un copil nu ˆıs, i poate face
singur un cadou.
Pentru a sc˘apa mai repede de g˘asitul cadourilor, copiii se vor ˆımp˘art, i ˆın grupuri. Tot, i copiii
din cadrul unui grup se vor aduna ˆımpreun˘a s, i vor conveni o singur˘a idee de cadou, urmˆand s˘a
ˆıl achizit, ioneze fiecare s, i s˘a ˆıl ofere mai departe destinatarilor. Copiii care nu dau cadouri nu
fac parte din niciun grup.
Totus, i, aces, tia vor s˘a se asigure c˘a niciun copil nu va primi dou˘a sau mai multe cadouri identice.
ˆIn plus, niciun copil nu s, i-ar dori s˘a primeasc˘a cadoul pe care ˆınsus, i acesta l-a oferit altui coleg.
Mai exact, pentru orice copil i (0 ≤ i < n), cadoul oferit de acesta trebuie s˘a fie diferit de
cadourile primite, iar cadourile primite s˘a fie distincte ˆıntre ele. Ar fi foarte dezam˘agitor s˘a
primes, ti de Cr˘aciun un cadou pe care l-ai oferit chiar tu, sau de mai multe ori aceeas, i cadou!
Care este num˘arul minim de grupuri care se pot forma, astfel ˆıncˆat tot, i copiii s˘a fie fericit, i?
Date de Intrare
Pe prima linie se d˘a numarul n de copii. Pe urm˘atoarea linie se dau n numere: v0, v1, ..., vn−1.
Dac˘a vi = −1, atunci copilul i nu va face niciun cadou. Altfel, copilul i va oferi un cadou
copilului vi.
Date de Ies, ire
Se afis, eaz˘a n numere. Al i-lea num˘ar reprezint˘a indicele grupului celui de-al i-lea copil.
Grupurile trebuie indexate de la 0. Dac˘a un copil nu face parte din niciun grup, valoarea
corespunz˘atoare afis, at˘a trebuie s˘a fie egal˘a cu −1.
Dac˘a sunt mai multe solut, ii valide, se va accepta oricare dintre ele.
1 of 2

Subiect · pagina 4

Constrˆangeri
• 1 ≤ n ≤ 105.
• −1 ≤ vi < n, pentru orice 0 ≤ i < n.
• Pentru orice 0 ≤ i < n, vi̸ = i.
Subtask-uri
1. (20 de puncte) Pentru fiecare 0 ≤ i < n, vi ∈ {−1, i − 1}. Mai mult, 1 ≤ n ≤ 100.
2. (20 de puncte) S, irul v0, v1, ..., vn−1 este o permutare a numerelor de la 0 la n − 1.
3. (20 de puncte) 1 ≤ n ≤ 1000.
4. (40 de puncte) Nicio constrˆangere suplimentar˘a.
Exemplu
Input Standard (cin) Output Standard (cout)
5
2 0 -1 0 3
1 0 -1 2 1
4
1 2 3 0
0 1 0 1
3
-1 -1 -1
-1 -1 -1
2 of 2

Subiect · pagina 5

MateInfoUB
20 Mai 2023
Facultatea de Matematicˇa-Informaticˇa
ForkBomb
Runda Finalˇa
Romˆanˇa (Oficial)
Fork Bomb
Matei a aflat recent de funct, ia fork la un curs de sisteme de operare. Pentru a termina
laboratorul mai repede, el dores, te acum s˘a creeze un fork bomb, un program care creeaz˘a
procese prin funct, ia fork cu scopul de a crash-ui calculatorul.
ˆIn mod foarte simplificat, executarea instruct, iunii fork() de c˘atre un proces P funct, ioneaz˘a
dup˘a cum urmeaz˘a. Mai ˆıntˆai, se creeaz˘a un nou proces “copil” Q c˘aruia i se atribuie P ca
s, i proces “p˘arinte”. Mai apoi, P s, i Q ˆıs, i continu˘a execut, ia ˆın paralel din dreptul instruct, iunii
fork() aferente. Pentru a putea diferent, ia ˆıntre procesul p˘arinte s, i cel copil, valoarea returnat˘a
de funct, ia fork() este 1 dac˘a procesul aferent este procesul copil s, i 0 dac˘a este vorba de procesul
p˘arinte.
Din fericire, Matei lucreaz˘a cu un limbaj foarte simplu, care are doar dou˘a instruct, iuni posibile:
• Instruct, iunea fork(), care, as, a cum ˆıi indic˘a numele, fork-uies, te procesul ˆın cadrul acelei
instruct, iuni.
• Instruct, iunea IF fork() THEN [...] ELSE [...] ENDIF, care permite execut, ia co-
dului ˆın mod condit, ionat. Cele dou˘a blocuri marcate prin puncte de suspensie pot cont, ine
0 sau mai multe instruct, iuni, care se vor executa ˆın ordine.
Un exemplu de folosire al programului este:
IF fork() THEN
ELSE
fork()
IF fork() THEN
fork()
ELSE
ENDIF
ENDIF
Execut, ia acestui program se realizeaz˘a cum urmeaz˘a:
Procesul principal P0 creeaz˘a un proces copil P1 care va intra pe ramura THEN a instruct, iunii
IF s, i va termina execut, ia. Procesul p˘arinte P0 ˆıns˘a va intra pe ramura ELSE s, i va crea un nou
proces copil P2. Ambele procese P0 s, i P2 vor executa cea de-a doua instruct, iune condit, ional˘a
IF s, i vor crea fiecare cˆate dou˘a procese copil P3 s, i P4, care vor crea procesele copil P5 s, i P6
respectiv, dup˘a care ˆıs, i vor termina execut, ia. Procesele P0 s, i P2 vor intra pe ramura ELSE s, i ˆıs, i
vor termina execut, ia.
Matei a observat ca in laboratorul unde se afl˘a, calculatoarele crash-uiesc dac˘a s, i numai dac˘a
exist˘a un arbore al proceselor specific. Altfel spus, arborele generat de procesele fork-uite tre-
buie s˘a aib˘a o structur˘a specific˘a.
Not˘a: Pentru mai multe detalii, dac˘a suntet, i pe un calculator care ruleaz˘a Linux, putet, i rula
ˆıntr-un terminal comanda man fork.
1 of 2

Subiect · pagina 6

Date de Intrare
Pe prima linie se d˘a num˘arul n de procese din arborele specific.
Pe urm˘atoarele n − 1 linii se dau cˆate dou˘a numere ai s, i bi, reprezentˆand o relat, ie de p˘arinte-
copil ˆıntre ai s, i bi (0 ≤ ai < bi < n). Procesul identificat prin nodul 0 reprezint˘a procesul
principal. Se garanteaz˘a c˘a datele de intrare descriu un arbore valid.
Date de Ies, ire
Se afis, eaz˘a un num˘ar arbitrar de linii, care s˘a cont, in˘a un program corect care s˘a genereze ar-
borele cerut. Mai exact, pentru programul afis, at, trebuie s˘a existe o etichetare a celor n procese
cu numere de la 0 la n − 1 astfel ˆıncˆat procesul principal s˘a aib˘a eticheta 0, iar procesele cu
etichetele ai s, i bi s˘a fie ˆın relat, ie tat˘a-fiu, pentru toate perechile (ai, bi) din datele de intrare.
Programul poate cont, ine una sau mai multe instruct, iuni s, i poate fi formatat prin oricˆate spat, ii
sau caractere “newline”. Dac˘a exist˘a mai multe solut, ii posibile, se va aceepta oricare dintre
ele.
Constrˆangeri
• 2 ≤ n ≤ 100.
• Programul generat nu poate efectua mai mult de 105 instruct, iuni (ˆın total, pentru toate
procesele generate)
Subtask-uri
1. (25 de puncte) Arborele care trebuie generat este un lant, .
2. (25 de puncte) Se garanteaz˘a existent, a unei solut, ii care s˘a nu foloseasc˘a instruct, iunea IF
(dar, in mod evident, se accept˘a s, i solut, ii care folosesc instruct, iunea IF).
3. (50 de puncte) Nicio constrˆangere suplimentar˘a.
Exemplu
Input Standard (cin) Output Standard (cout)
7
0 1
0 2
2 3
0 4
3 5
4 6
IF fork() THEN
ELSE
fork()
IF fork() THEN
fork()
ELSE
ENDIF
ENDIF
4
0 1
0 3
1 2
fork()
fork()
2 of 2

Subiect · pagina 7

MateInfoUB
20 Mai 2023
Facultatea de Matematicˇa-Informaticˇa
Plangaciosi
Runda Finalˇa
Romˆanˇa (Oficial)
Bebelus, i Plˆang˘acios, i
ˆIntr-un hotel se afl˘a n camere pe acelas, i etaj. Cele n camere sunt dispuse ˆın linie. ˆIntr-o
sear˘a trebuie cazat, i m bebelus, i. Dup˘a cum bine se s, tie, bebelus, ii se apuc˘a s˘a plang˘a deseori ˆın
timpul nopt, ii s, i, de asemenea, ei se trezesc foarte us, or. Mai mult, dac˘a exist˘a vreun bebelus,
care plˆange la o camer˘a alaturat˘a, ˆıncepe s, i el s˘a plˆang˘a. Hotelul ˆıs, i dores, te din tot sufletul s˘a
evite react, ii ˆın lant, de plˆans s, i v˘a cere ajutorul.
ˆIn cˆate moduri putem as, eza cei m bebelus, i ˆın cele n camere astfel ˆıncˆat doi bebelus, i s˘a nu stea
ˆın camere al˘aturate?
Date de Intrare
Pe singura linie se dau dou˘a numere n s, i m separate printr-un spat, iu.
Date de Ies, ire
Pe singura linie se va afis, a un singur num˘ar, respectiv num˘arul de moduri de a as, eza bebelus, ii
ˆın camere modulo 1.000.000.007.
Constrˆangeri
• 1 ≤ m ≤ n ≤ 1000.
Subtask-uri
1. (20 de puncte) 1 ≤ n ≤ 1000, 1 ≤ m ≤ 2.
2. (10 puncte) 1 ≤ n ≤ 100, m = 3.
3. (20 de puncte) 1 ≤ m ≤ n ≤ 12.
4. (20 de puncte) 1 ≤ m ≤ n ≤ 100.
5. (30 de puncte) Nicio constrˆangere suplimentar˘a.
Exemplu
Input Standard (cin) Output Standard (cout)
6 3 4
10 8 0
512 64 988646651
1 of 1

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Examen de admitere · 2023Matematică, Informatică și Fizică · Varianta 1; broșură comunăDeschide fișa Examen de admitere · 2023Matematică, Informatică și Fizică · Varianta 2; broșură comunăDeschide fișa Examen de admitere · 2023Matematică, Informatică și Fizică · Varianta 3; broșură comunăDeschide fișa Examen de admitere · 2023Matematică, Informatică și Fizică · Varianta 4; broșură comunăDeschide fișa Concurs de pregătire · 2023Matematică · Etapa a II-aDeschide fișa Examen de admitere · 2024Matematică, Informatică și Fizică · Varianta 1; broșură comunăDeschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

Pagina prezintă concurs de pregătire din 2023 pentru Informatică, la Facultatea de Matematică și Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.

Există și barem sau răspunsuri pentru acest subiect?

Nu există un barem public asociat în inventarul verificat pentru acest document. ProfesorBun nu generează și nu inventează răspunsuri oficiale. Poți folosi subiectul pentru antrenament, dar corectarea trebuie făcută cu metodologia instituției, cu materiale oficiale suplimentare sau împreună cu un profesor.

Cum folosesc acest subiect în pregătirea pentru admitere?

Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.

Pregătire cu un profesor

Subiect și barem

Concurs de pregătire · Informatică · 2023

Despre acest subiect

Subiectul în format text

Subiect · pagina 1