Pregătire cu un profesor

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 4

Subiect · 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 4

Deschide documentul original

Barem · document original

Textul acestui document nu este disponibil momentan. Poți consulta documentul în vizualizatorul de mai sus sau în sursa originală.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

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.

Pregătire cu un profesor

Subiect și barem

Concurs de pregătire · Informatică · 2024

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1