Despre acest subiect
primăvară · Etapa a II-a
Sursa documentelor: FMI UniBuc – MateInfoUB 2022. Pentru acest subiect nu este disponibil un barem public.
Se încarcă profesorii disponibili…
Subiect și barem
Sursa: FMI UniBuc – MateInfoUB 2022
Acest subiect nu are un barem public asociat.
Concurs de pregătire · Informatică · 2022
Facultatea de Matematică și Informatică · UniBuc
Înapoi la arhivăSubiectul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect · 4 pagini
Subiect · pagina 1
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ă.
4Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
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.
