Pregătire cu un profesor

A. Cazane
Lucifer, împaratul iadului, este încurcat. Design-ul init, ial al iadului era bun, dar populat, ia pămân-
tului în cres, tere continuă îi dă toate planurile peste cap, de aceea vă cere ajutorul.
În iad tocmai s-a deschis o sect, iune nouă, în care există N cazane, cu capacităt, ile de a1, a2, . . . , aN
oameni. Init, ial sect, iunea este goală, dar pe parcursul a M zile sunt adus, i noi păcătos, i, care trebuie
pus, i în cazane, fără a depăs, i capacitatea lor maximă. În dimineat, a zilei i (1 ≤ i ≤ M ) sunt adus, i
pi păcătos, i.
Fiecare cazan trebuie păzit ca păcătos, ii să nu scape. Din cauza aceasta, Lucifer dores, te ca numărul
de cazane folosit în fiecare zi să fie cât mai mic.
Care este numărul minim de cazane care trebuie folosite în fiecare zi?
Date de intrare
Pe prima linie se găsesc numerele N s, i M cu semnificat, ia din enunt, .
Pe următoarea linie se găsesc N valori: a1, a2, . . . , aN cu semnificat, ia din enunt, .
Pe următoarea linie se găsesc M valori: p1, p2, . . . , pM cu semnificat, ia din enunt, .
Date de ies, ire
Se vor afis, a M numere, al i-lea număr reprezentând numărul minim de cazane necesare la sfârs, itul
zilei i.
Restrict, ii s, i precizări
• 1 ≤ N, M ≤ 1000
• 1 ≤ ai, pi ≤ 1000
• ∑ pi ≤ ∑ ai
• Datele de intrare s, i ies, ire sunt furnizate prin intrarea s, i ies, irea standard (cin s, i cout în C++,
scanf s, i printf în C ).
Subtask-uri
# Punctaj Restrict, ii suplimentare
1 26 M = 1
2 18 ai = aj , pentru orice 1 ≤ i, j ≤ N
3 56 Nicio restrict, ie suplimentară
Exemplu
Intrare Ies, ire
5 6
5 3 4 10 1
9 3 2 2 3 1
1 2 2 3 3 4
1

Subiect · pagina 2

B. Felinare
Strada lui Matei poate fi reprezentată pe o axă, unde casele sunt numerotate de la 1 la N .
În dreptul fiecărei case se află un felinar, în dreptul casei i (1 ≤ i ≤ N ) găsindu-se un felinar cu
puterea fi, unde fi este un număr natural. Felinarul i este capabil să ilumineze toate casele din
intervalul închis [i − fi, i + fi]. În mod particular, dacă fi = 0, atunci felinarul i nu poate ilumina
decât casa i.
Care este numărul minim de felinare ce trebuie aprinse, astfel încât toate cele N case să fie ilumi-
nate?
Date de intrare
Pe prima linie se găses, te numărul N cu semnificat, ia din enunt, .
Pe următoarea linie se găsesc N valori: f1, f2, . . . , fN cu semnificat, ia din enunt, .
Date de ies, ire
Se va afis, a un singur număr, respectiv numărul minim de felinare cu ajutorul cărora poate fi iluminat
tot oras, ul.
Restrict, ii s, i precizări
• 0 ≤ fi ≤ N
• 1 ≤ N ≤ 105
• Datele de intrare s, i ies, ire sunt furnizate prin intrarea s, i ies, irea standard (cin s, i cout în C++,
scanf s, i printf în C ).
Subtask-uri
# Punctaj Restrict, ii suplimentare
1 37 1 ≤ N ≤ 15
2 51 1 ≤ N ≤ 1000
3 12 Nicio restrict, ie suplimentară
Exemplu
Intrare Ies, ire
15
1 3 2 3 0 0 5 3 0 0 0 1 2 1 1
3
Explicat, ie: Se vor aprinde felinarele 4, 7 s, i 13.
2

Subiect · pagina 3

C. Tren
Între oras, ul X s, i oras, ul Y există un sistem de cale ferată foarte complex. Oras, ul X este la vest fat, ă
de oras, ul Y. Atât gara din oras, ul X , cât s, i gara din oras, ul Y au câte N peroane, peronul 1 fiind
cel mai din nord s, i peronul N fiind cel mai din sud.
Există M s, ine instalate între cele două oras, e. S, ina i (1 ≤ i ≤ M ) conectează printr-o linie dreaptă
peronul ai din orasul X cu peronul bi din oras, ul Y.
Infrastructura începe să îmbătrânească, as, a că ai decis să renovezi s, inele, dar înainte de asta trebuie
să afli câte treceri la nivel (intersect, ii) există între ele. Altfel spus, dores, ti să afli câte perechi de
s, ine se intersectează (exceptând cele care se intersectează numai într-una din cele două gări).
Câte astfel de intersect, ii există?
Date de intrare
Pe prima linie se găsesc numerele N s, i M din enunt, . Pe următoarele M linii se va găsi descrierea
s, inelor. Pe linia i (1 ≤ i ≤ M ) se găsesc numerele ai s, i bi, cu semificat, iile din enunt, .
Date de ies, ire
Se va afis, a un singur număr, respectiv numărul de intersect, ii dintre s, inele de tren.
Restrict, ii s, i precizări
• 1 ≤ N, M ≤ 3 × 105
• 1 ≤ ai, bi ≤ N , pentru fiecare 1 ≤ i ≤ M
• 1 ≤ M ≤ N 2
• Nu vor există două s, ine conectate între aceeas, i pereche de peroane.
• Pot exista peroane fără s, ine asociate, atât din oras, ul X cât s, i din oras, ul Y.
• Datele de intrare s, i ies, ire sunt furnizate prin intrarea s, i ies, irea standard (cin s, i cout în C++,
scanf s, i printf în C ).
Subtask-uri
# Punctaj Restrict, ii suplimentare
1 18 1 ≤ N, M ≤ 50
2 16 1 ≤ N, M ≤ 2000
3 55 1 ≤ N ≤ 2000
4 11 Nicio restrict, ie suplimentară
Exemplu
Intrare Iesire
10 6
1 10
1 5
2 6
2 10
6 1
5 5
9
Explicat, ie: Cele 9 intersect, ii exprimate sub forma (i, j), adică s, ina i intersectează s, ina j, sunt:
(1, 3), (1, 5), (1, 6), (2, 5), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6).
3

Subiect · pagina 4

D. Vopsea
Matei are nevoie de vopsea neagră pentru a-s, i vopsi trotineta. Toată lumea s, tie că vopseaua neagră
se obt, ine amestecând aceeas, i cantitate de vopsea ros, ie, galbenă s, i albastră.
Matei are la dispozit, ie N gălet, i de vopsea deja amestecată. Vopseaua i (1 ≤ i ≤ N ) s-a obt, inut prin
amestecarea a ri litri de vopsea ros, ie, gi litri de vopsea galbenă s, i ai litri de vopsea albastră.
Matei dores, te să combine unele dintre aceste gălet, i (posibil niciuna), astfel încât vopseaua obt, inută
să fie neagră.
Care este cantitatea maximă (în litri) de vopsea neagră pe care o poate obt, ine?
Date de intrare
Pe prima linie se dă N , numărul de galet, i de vopsea.
Pe următoarele N linii se vor găsi câte 3 numere, pe linia i găsindu-se numerele ri, gi s, i ai.
Date de ies, ire
Se va afis, a un singur număr, respectiv cantitatea maximă de vopsea neagră pe care Matei o poate
obt, ine.
Restrict, ii s, i precizări
• 1 ≤ N ≤ 40
• 0 ≤ ri, gi, ai ≤ 106
• Datele de intrare s, i ies, ire sunt furnizate prin intrarea s, i ies, irea standard (cin s, i cout în C++,
scanf s, i printf în C ).
Subtask-uri
# Punctaj Restrict, ii suplimentare
1 27 1 ≤ N ≤ 20 , 1 ≤ S ≤ 50
2 36 1 ≤ N ≤ 30 , 1 ≤ S ≤ 100
3 37 Nicio restrict, ie suplimentară
Am notat S = max{∑N
i=1 ri, ∑N
i=1 gi, ∑N
i=1 ai}
Exemplu
Intrare Ies, ire
6
1 3 0
10 4 9
2 1 0
0 0 5
1 1 1
2 1 0
18
Explicat, ie: Dacă alegem gălet, ile 1, 3, 4, 5 s, i 6, atunci vom avea câte 6 litri de vopsea ros, ie,
galbenă s, i albastră, deci în total 18 litri de vopsea neagră.
4

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 1; broșură comunăDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 2; broșură comunăDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 3; broșură comunăDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 4; broșură comunăDeschide fișa Concurs de pregătire · 2022Matematică · Etapa a II-aDeschide fișa Examen de admitere · 2023Matematică, 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 2022 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ă · 2022

Despre acest subiect

Subiectul în format text

Subiect · pagina 1

Subiect · pagina 2

Subiect · pagina 3

Subiect · pagina 4

Alte subiecte de la aceeași facultate

Ce trebuie să știi despre acest subiect?