Despre acest subiect
primăvară · Etapa a II-a
Sursa documentelor: FMI UniBuc – MateInfoUB 2024. Verifică răspunsurile cu baremul după ce rezolvi subiectul.
Se încarcă profesorii disponibili…
Subiect și barem
Sursa: FMI UniBuc – MateInfoUB 2024
Concurs de pregătire · Informatică · 2024
Facultatea de Matematică și Informatică · UniBuc
Înapoi la arhivăSubiectul și baremul în format text
Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.
Subiect · 10 pagini
Subiect · pagina 1
MateInfoUB 19 Mai 2024 Facultatea de Matematicˇa-Informaticˇa R^ame Pane Runda Finalˇa Romˆanˇa (Oficial) Gourmet∗ 1: Rˆame pane Chef Constantin a primit comand˘a de M rˆame pane, specialitatea casei. El se uit˘a ˆın cuf˘arul de rˆame s, i observ˘a c˘a are la dispozit, ie N rˆame, de lungimi ˆıntregi r1, r2, . . . , rN . Chef iscusit, Constantin poate t˘aia rˆamele ˆın buc˘at, i mai mici de lungime ˆıntreag˘a. Apoi acesta pr˘ajes, te cˆate o rˆam˘a (sau bucat˘a de rˆam˘a) pentru fiecare dintre cei M oaspet, i. Satisfact, ia unui oaspete este dat˘a de lungimea rˆamei primite iar satisfact, ia lui Constantin, om empatic, este minimul satisfact, iilor tuturor client, ilor s˘ai. Dac˘a taie s, i distribuie rˆamele ˆın mod optim, care este satisfact, ia maxim˘a pe care o poate avea Chef Constantin? Date de Intrare Pe prima linie se dau dou˘a numere N s, i M , cu semnificat, ia din enunt, . Urm˘atoarea linie cont, ine N numere: r1, r2, . . . , rN . Date de Ies, ire Pe singura linie se va afis, a un singur num˘ar, satisfact, ia maxim˘a a lui Chef Constantin. Dac˘a nu exist˘a nicio ˆımp˘art, ire posibil˘a, atunci satisfact, ia lui este 0. Constrˆangeri • 1 ≤ N, M ≤ 105. • ∀1 ≤ i ≤ N, 1 ≤ ri ≤ 106. Subtask-uri 1. (15 puncte) M = 2. ∗Preparatele gourmet se definesc ca fiind acele preparate de bun˘a calitate, preg˘atite cu foarte mult˘a grij˘a s, i prezentate ˆıntr-un mod artistic. 1 of 2
Subiect · pagina 2
2. (15 puncte) N = 2. 3. (40 puncte) 1 ≤ N, M ≤ 103, ∀1 ≤ i ≤ N, 1 ≤ ri ≤ 103. 4. (30 de puncte) Nicio constrˆangere suplimentar˘a. Exemplu Input Standard (cin) Output Standard (cout) 1 2 255 127 10 6 15 43 72 59 18 8 24 97 61 27 43 2 of 2
Subiect · pagina 3
MateInfoUB 19 Mai 2024 Facultatea de Matematicˇa-Informaticˇa Prajitur˘a cu Mujdei Runda Finalˇa Romˆanˇa (Oficial) Gourmet 2: Pr˘ajitur˘a cu mujdei Chef Alexandru a primit o comand˘a pentru specialitatea casei: o port, ie zdrav˘an˘a de pr˘ajitur˘a cu mujdei. Pentru pr˘ajitur˘a, el are nevoie de exact X litri de mujdei. Chef Alexandru are la dispozit, ie dou˘a castroane A s, i B, de capacitate CA, respectiv CB litri, ambele init, ial goale. Chef Alexandru poate face urm˘atoarele operat, ii: • UMPLE [A/B] - umple complet castronul A sau B cu CA, respectiv CB litri de mujdei; • GOLESTE [A/B] - goles, te complet castronul A sau B; • VARSA [A/B] IN [B/A] - vars˘a cˆat mai mult mujdei posibil din castronul A (sau B) ˆın castronul B (sau A). Dac˘a castronul surs˘a are x litri de mujdei s, i castronul destinat, ie are y litri liberi, atunci Chef Alexandru va v˘arsa exact min(x, y) litri. Chef Alexandru v˘a cere ajutorul: g˘asit, i o serie de cel mult 106 operat, ii ˆın urma c˘arora se vor afla exact X litri de mujdei ˆıntr-unul dintre cele dou˘a castroane. Atent, ie: Orice solut, ie valid˘a este acceptat˘a, nu este necesar s˘a minimizat, i lungimea acesteia! Date de intrare Pe singura linie din fis, ierul de intrare se dau trei numere naturale CA, CB s, i X separate prin cˆate un spat, iu, avˆand semnificat, ia din enunt, . Date de ies, ire Dac˘a nu exist˘a solut, ie, atunci pe singura linie din fis, ierul de ies, ire afis, at, i ”IMPOSIBIL”. Dac˘a exist˘a o solut, ie, atunci afis, at, i pe prima linie num˘arul de operat, ii necesare, iar pe urm˘atoarele linii, ˆın ordine, afis, at, i operat, iile efectuate. Constrˆangeri • 1 ≤ X < CA, CB ≤ 100.000. 1 of 2
Subiect · pagina 4
Subtask-uri 1. (20 de puncte) X = 1, CA = 2 s, i CB ≤ 10. 2. (20 de puncte) 1 ≤ CA, CB ≤ 10. 3. (30 de puncte) 1 ≤ CA, CB ≤ 1000. 4. (30 de puncte) Nicio constrˆangere suplimentar˘a. Exemplu Input Standard (cin) Output Standard (cout) 3 2 1 2 UMPLE A VARSA A IN B 1110 10101 110 IMPOSIBIL 10 6 4 6 UMPLE B VARSA B IN A UMPLE A UMPLE B GOLESTE B VARSA A IN B 2 of 2
Subiect · pagina 5
MateInfoUB 19 Mai 2024 Facultatea de Matematicˇa-Informaticˇa R˘acituri cu piure Runda Finalˇa Romˆanˇa (Oficial) Gourmet 3: R˘acituri cu piure Teo se duce la cantina lui favorit˘a (cea de la ASE) ca s˘a guste din noua gam˘a de alimente - r˘acituri cu piure. La bufetul de r˘acituri, el are la alegere R tipuri de r˘acituri. Al i-lea tip (0 ≤ i < R) cost˘a ri lei. Pentru fiecare tip de r˘acitur˘a, Teo, cu o probabilitate de 1 2 , ˆıs, i pune ˆın farfurie o r˘acitur˘a. La bufetul de piure, el are la alegere P tipuri de piure. Piureul se vinde la volum, as, a c˘a pentru al i-lea tip de piure (0 ≤ i < P ), Teo se poate servi cu piure ˆın valoare de 0, 1, . . . , pi lei. Pentru fiecare tip de piure, Teo se serves, te uniform aleatoriu cu o cantitate permis˘a de piure. Cantina ofer˘a urm˘atoarea reducere: dac˘a pret, ul total al alimentelor alese de Teo este strict mai mare decˆat suma de X lei, atunci Teo primes, te o reducere de 50%. Care este, ˆın medie, pret, ul pl˘atit de Teo? Date de intrare Pe prima linie din fis, ierul de intrare se afl˘a numerele R, P s, i X cu semnificat, ia din enunt, . Pe a doua linie se afl˘a R numere ˆıntregi: r0, r1, . . . , rR−1. Pe a treia linie se afl˘a P numere ˆıntregi: p0, p1, . . . , pP −1. Date de ies, ire Pe singura linie din fis, ierul de ies, ire afis, at, i r˘aspunsul, modulo 109 + 7. Dac˘a r˘aspunsul este egal cu fract, ia A B , afis, at, i num˘arul A ∗ B−1(modulo 109 + 7). Constrˆangeri • 1 ≤ P, R ≤ 100. • 1 ≤ pi, ri ≤ 103. • 1 ≤ X ≤ 2 ∗ 105. 1 of 2
Subiect · pagina 6
Subtask-uri 1. (20 de puncte) P = 0, R ≤ 20 s, i X = 2 · 105 (niciodat˘a nu se aplic˘a reducerea). 2. (20 de puncte) P = 0, R ≤ 20. 3. (20 de puncte) P = 0. 4. (20 de puncte) ∀0 ≤ i < P, pi ≤ 5. 5. (20 de puncte) Nicio constrˆangere suplimentar˘a. Atas, amente ˆIn sect, iunea ”Downloads” a interfet, ei de concurs putet, i desc˘arca un fis, ier C++ care imple- menteaz˘a operat, ii de baz˘a ale aritmeticii modulare. Acesta este util mai ales dac˘a nu at, i mai lucrat cu not, iunea de invers modular. Exemplu Input Standard (cin) Output Standard (cout) 5 3 10 2 7 6 2 6 6 7 10 142806425 10 10 100 26 27 72 11 6 30 60 90 28 15 60 68 38 48 22 65 19 75 17 1 413422235 2 of 2
Subiect · pagina 7
MateInfoUB 19 Mai 2024 Facultatea de Matematicˇa-Informaticˇa Cornis, oni Afumat, i Runda Finalˇa Romˆanˇa (Oficial) Gourmet 4: Cornis, oni afumat, i ˆIn anul de glorie 2051 ChatGPT 42, maestru arheolog, a descoperit o carte de ret, ete, o r˘am˘as, it, ˘a a civilizat, iei umane, exterminat˘a de aproape 26 de ani. Maestrul vrea acum s˘a recreeze o delicates˘a uman˘a: cornis, oni afumat, i. El are de urmat N pas, i, dar este put, in derutat: ret, eta, ca orice ret, et˘a scris˘a ˆın 2024 care se respect˘a, vorbes, te de copil˘aria autorului, apoi de ingrediente, apoi de o p˘at, anie haioas˘a a autorului etc. Pentru a putea recrea ret, eta, robot, elul nostru are de sortat pas, ii s, i v˘a cere ajutorul. Cei N pas, i de urmat, reprezentat, i prin numere de la 0 la N − 1, s, i salvat, i ˆın vectorul V (elementele V [0], . . . , V [N − 1]), se afl˘a ˆıntr-o ordine aleatorie (o permutare) s, i trebuie sortat, i ˆın ordine cresc˘atoare. Robot, elul poate t, ine minte 5 numere ˆın variabilele A, B, C, D s, i E (init, ial, toate variabilele au valoarea 0). Adit, ional, variabilele constante Z s, i N cont, in valoarea 0, respectiv N , numarul de pas, i de urmat. Instruct, iunile pe care le poate efectua robotul sunt: • IF_LESS_GOTO r1 r2 x – dac˘a valoarea variabilei r1 este mai mic˘a decˆat valoarea vari- abilei r2, atunci urm˘atoarea operat, ie pe care o execut˘a robotul este x; • IF_DIFF_GOTO r1 r2 x – dac˘a valoarea lui r1 este diferit˘a de valoarea lui r2, atunci urm˘atoarea operat, ie pe care o execut˘a robotul este x; • IF_SAME_GOTO r1 r2 x – dac˘a valoarea lui r1 este egal˘a cu valoarea lui r2, atunci urm˘atoarea operat, ie pe care o execut˘a robotul este x; • ASSIGN r1 r2 – se salveaz˘a ˆın r1 valoarea lui r2. Variabila r1 trebuie s˘a fie ne- constant˘a (i.e. diferit˘a de Z s, i N ). • INC r s, i DEC r – se cres, te sau se scade valoarea salvat˘a ˆın variabila ne-constant˘a r. • PLOAD r – ˆın variabila ne-constant˘a r se salveaz˘a pasul de la pozit, ia r (r devine V [r]). Valoarea lui r trebuie s˘a fie cuprins˘a ˆıntre 0 s, i N − 1. • PSWAP r1 r2 – se interschimb˘a valorile din V [r1] s, i V [r2] (i.e. V [r1] devine V [r2] s, i vice-versa). Valorile din r1 s, i r2 trebuie s˘a fie cuprinse ˆıntre 0 s, i N − 1 inclusiv. 1 of 4
Subiect · pagina 8
• END – se termin˘a execut, ia programului. Dup˘a ce execut˘a o operat, ie, robotul execut˘a urm˘atoarea operat, ie, mai put, in ˆın cazul ˆın care operat, ia specific˘a altceva. Dac˘a a ajuns la sf˘ars, itul operat, iilor sau s-a executat operat, ia END, execut, ia se termin˘a. Date de intrare Pe unica linie din fis, ierul de intrare se afl˘a num˘arul N , lungimea vectorului V . Date de ies, ire Se afis, eaz˘a un program care s˘a ordoneze vectorul V cu cei N pas, i ˆın ordine cresc˘atoare. Dac˘a exist˘a mai multe solut, ii posibile, atunci se va accepta oricare dintre ele. Atent, ie: pentru formatul exact ˆın care trebuie afis, ate operat, iile vedet, i exemplele. Constrˆangeri • 2 ≤ n ≤ 100.000. • Programul generat nu poate efectua mai mult de 5 · 106 operat, ii. • Programul generat nu poate avea mai mult de 1.000 de instruct, iuni. Subtask-uri 1. (10 de puncte) N = 3. 2. (15 de puncte) N = 4. 3. (15 de puncte) N ≤ 15. 4. (20 de puncte) N ≤ 100. 5. (20 de puncte) N ≤ 5.000. 6. (20 de puncte) Nicio constrˆangere suplimentar˘a. Atas, amente Pentru a simplifica testarea solut, iilor, ˆın sect, iunea ”Downloads” a interfet, ei de concurs putet, i desc˘arca un validator pentru solut, ia voastr˘a. 2 of 4
Subiect · pagina 9
Exemplu
Input Standard (cin) Output Standard (cout)
2 0. INC A
1. PLOAD A
2. PLOAD B
3. IF_LESS_GOTO B A 5
4. END
5. ASSIGN A Z
6. ASSIGN B Z
7. INC B
8. PSWAP A B
2 0. ASSIGN A N
1. DEC A
2. ASSIGN B Z
3. ASSIGN C A
4. ASSIGN D B
5. PLOAD C
6. PLOAD D
7. IF_DIFF_GOTO N Z 9
8. END
9. IF_LESS_GOTO C D 11
10. END
11. PSWAP A B
2 0. INC B
1. PLOAD A
2. PLOAD B
3. IF_LESS_GOTO A B 6
4. INC D
5. PSWAP C D
6. END
Consider˘am al doilea exemplu (N = 2):
0. ASSIGN A N
1. DEC A
2. ASSIGN B Z
3. ASSIGN C A
4. ASSIGN D B
5. PLOAD C
6. PLOAD D
7. IF_DIFF_GOTO N Z 9
8. END
9. IF_LESS_GOTO C D 11
10. END
11. PSWAP A B
Presupunem c˘a valoarea permut˘arii este V = { 1, 0 }. Operat, iile efectuate de robot sunt
3 of 4Subiect · pagina 10
urm˘atoarele:
1. Linia executat˘a este 0. ASSIGN A N.
V = { 1, 0 }
A = 2, B = 0, C = 0, D = 0, E = 0
2. Linia executat˘a este 1. DEC A.
V = { 1, 0 }
A = 1, B = 0, C = 0, D = 0, E = 0
3. Linia executat˘a este 3. ASSIGN C A.
V = { 1, 0 }
A = 1, B = 0, C = 1, D = 0, E = 0
4. Linia executat˘a este 4. ASSIGN D B.
V = { 1, 0 }
A = 1, B = 0, C = 1, D = 0, E = 0
5. Linia executat˘a este 5. PLOAD C.
V = { 1, 0 }
A = 1, B = 0, C = 0, D = 0, E = 0
6. Linia executat˘a este 6. PLOAD D.
V = { 1, 0 }
A = 1, B = 0, C = 0, D = 1, E = 0
7. Linia executat˘a este 7. IF_DIFF_GOTO N Z 9.
N este diferit de Z (2̸ = 0), as, a c˘a s˘arim la instruct, iunea 9.
V = { 1, 0 }
A = 1, B = 0, C = 0, D = 1, E = 0
8. Linia executat˘a este 9. IF_LESS_GOTO C D 11.
C este mai mic decˆat D, as, a c˘a s˘arim la instruct, iunea 11. V = { 1, 0 }
A = 1, B = 0, C = 0, D = 1, E = 0
9. Linia executat˘a este 11. PSWAP A B.
V = { 0, 1 }
A = 1, B = 0, C = 0, D = 1, E = 0
10. Execut, ia programului se opres, te, iar vectorul V = {0, 1} este sortat.
4 of 4Barem · document original
Textul acestui document nu este disponibil momentan. Poți consulta documentul în vizualizatorul de mai sus sau în sursa originală.
Deschide documentul originalContinuă pregătirea
Vezi arhiva completăAlte subiecte de la aceeași facultate
Examen de admitere · 2024Matematică, Informatică și Fizică · Varianta 1; broșură comunăDeschide fișa Examen de admitere · 2024Matematică, Informatică și Fizică · Varianta 2; broșură comunăDeschide fișa Examen de admitere · 2024Matematică, Informatică și Fizică · Varianta 3; broșură comunăDeschide fișa Examen de admitere · 2024Matematică, Informatică și Fizică · Varianta 4; broșură comunăDeschide fișa Concurs de pregătire · 2024Matematică · Etapa a II-aDeschide fișa Examen de admitere · 2025Matematică, 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 2024 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?
Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.
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.
