Despre acest subiect
primăvară · Etapa a II-a
Sursa documentelor: FMI UniBuc – MateInfoUB 2023. Pentru acest subiect nu este disponibil un barem public.
Se încarcă profesorii disponibili…
Subiect și barem
Sursa: FMI UniBuc – MateInfoUB 2023
Acest subiect nu are un barem public asociat.
Concurs de pregătire · Informatică · 2023
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 · 7 pagini
Subiect · pagina 1
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 2Subiect · 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
Continuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
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.
