La o firmă de curierat, în prima lună nu s-a livrat niciun pachet, în cea de-a doua lună s-au livrat 3 pachete, apoi numărul de pachete livrate în fiecare lună a fost egal cu suma dintre numărul de pachete livrate în luna precedentă și dublul valorii absolute a diferenței dintre numărul de pachete livrate în cele două luni precedente, obținând astfel șirul numărului de pachete livrate: 0 3 9 21 45 93 189 381 ....
Se citesc de la tastatură două numere naturale din intervalul [0,10⁹], reprezentând numărul de pachete livrate de firma de curierat în ultima și respectiv penultima lună, și se cere să se scrie în fișierul bac.txt, în ordine descrescătoare, separate prin câte un spațiu, numărul de pachete livrate în fiecare lună. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă se citesc valorile 189 și 93, fișierul conține numerele: 189 93 45 21 9 3 0
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează trei valori corespunzătoare ultimelor trei numere din șir (x, y, z, în această ordine), care se actualizează la fiecare pas; inițial se afișează, în ordinea cerută, valorile date, apoi la fiecare pas se determină valoarea curentă (x) pe baza valorilor ultimelor două numere afișate (x=[(3∙y-z)/2]), procedeu care se încheie după ce s-a afișat valoarea 0.
3. b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea scrierii, scriere în fișier, conform cerinței - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, citire a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă utilizează trei valori corespunzătoare ultimelor trei numere din șir (x, y, z, în această ordine), care se actualizează la fiecare pas; inițial se afișează, în ordinea cerută, valorile date, apoi la fiecare pas se determină valoarea curentă (x) pe baza valorilor ultimelor două numere afișate (x=[(3∙y-z)/2]), procedeu care se încheie după ce s-a afișat valoarea 0.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
De-a lungul timpului, o persoană a participat la mai multe concursuri de șah și de go. Un rezultat motivant corespunde unei poziții mai bune (cu un număr mai mic) în clasamentul unui concurs, comparativ cu poziția obținută la concursul anterior de același tip.
Fișierul bac.txt conține un șir de cel mult 10⁴ numere naturale, reprezentând rezultatele obținute la concursurile la care a participat, în ordine cronologică: pentru fiecare dintre rezultate, câte o pereche formată din poziția ocupată în clasamentul concursului corespunzător (un număr din intervalul [1,300]), urmată de valoarea 1, dacă acesta a fost concurs de șah, sau de valoarea 2, dacă acesta a fost concurs de go. Fiecare pereche se află pe câte o linie a fișierului, cu valorile separate printr-un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două valori naturale, reprezentând, în această ordine, numărul de rezultate motivante obținute la concursurile de șah, respectiv la cele de go. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele alăturate, pe ecran se afișează 3 2
6 1
8 2
7 1
5 2
3 1
4 1
5 1
1 2
4 2
1 1
2 1
1 1
pentru că la șah a obținut trei rezultate motivante (poziția 3 după poziția 7, poziția 1 după poziția 5 și poziția 1 după poziția 2), iar la go două rezultate motivante (poziția 5 după poziția 8, poziția 1 după poziția 5).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
SUBIECTUL al III-lea
3. a. Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului, conform cerinței (*) - 1p.
- elemente de eficiență justificate, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă determină, pe măsura citirii datelor, cele două numere cerute (ns și ng), și memorează poziția în clasamentul ultimului concurs de șah (ups, inițializată cu -1), respectiv de go (upg, inițializată cu -1); la fiecare pas se citesc câte două valori, p și c, și după caz, se incrementează ns (dacă c=1 și p<ups) și ng (dacă c=2 și p<upg) și se actualizează ups (dacă c=1) și upg (dacă c=2).
SUBIECTUL al III-lea
3. b. Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- valori determinate, conform cerinței (*),(**) - 5p.
- eficiență a algoritmului, conform cerinței (***) - 1p.
- variabile declarate, afișare a datelor conform cerinței, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge toți pașii necesari rezolvării, dar cu detalii care nu conduc la rezultatul cerut.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă determină, pe măsura citirii datelor, cele două numere cerute (ns și ng), și memorează poziția în clasamentul ultimului concurs de șah (ups, inițializată cu -1), respectiv de go (upg, inițializată cu -1); la fiecare pas se citesc câte două valori, p și c, și după caz, se incrementează ns (dacă c=1 și p<ups) și ng (dacă c=2 și p<upg) și se actualizează ups (dacă c=1) și upg (dacă c=2).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Fișierul text bac.txt conține un șir de cel mult 10⁶ triplete de numere naturale din intervalul [1,10²], numerele din fiecare triplet reprezentând lungimile laturilor câte unui triunghi. Fiecare triplet se află pe câte o linie a fișierului, iar numerele care îl compun sunt separate prin câte un spațiu.
Într-un triunghi dreptunghic pătratul lungimii ipotenuzei este egal cu suma pătratelor lungimilor celor două catete.
Se cere să se afișeze pe ecran numărul maxim de triunghiuri dreptunghice din fișier care au aceeași lungime a ipotenuzei. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele alăturate, pe ecran se afișează 3
(sunt trei triunghiuri de tipul cerut cu ipotenuza 25: două au catetele 7, respectiv 24, și unul are catetele 15, respectiv 20).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
3. a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează un vector de apariții v, în care vᵢ este numărul de triunghiuri dreptunghice din fișier care au lungimea ipotenuzei egală cu i. Pe măsura citirii datelor din fișier, pentru fiecare triplet se identifică cea mai mare valoare/latură (i) și, dacă tripletul respectă proprietatea specifică pentru triunghi dreptunghic, se incrementează vᵢ. Numărul cerut este cea mai mare valoare memorată în vectorul v.
b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier, conform cerinței - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un vector de apariții v, în care vᵢ este numărul de triunghiuri dreptunghice din fișier care au lungimea ipotenuzei egală cu i. Pe măsura citirii datelor din fișier, pentru fiecare triplet se identifică cea mai mare valoare/latură (i) și, dacă tripletul respectă proprietatea specifică pentru triunghi dreptunghic, se incrementează vᵢ. Numărul cerut este cea mai mare valoare memorată în vectorul v.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
3. Un tânăr pasionat de călătorii are o listă cu muzee virtuale și, pentru fiecare, câte un singur interval orar, în care acesta poate fi vizitat online, gratuit. Tânărul dispune zilnic de același interval orar pentru vizite; un muzeu este convenabil dacă poate fi vizitat online gratuit în timpul disponibil și dacă pentru vizită îi poate aloca cel puțin o oră. Muzeele din listă sunt numerotate cu valori naturale consecutive, începând cu 1, și cel puțin unul este convenabil.
Fișierul text bac.in conține cel mult 10⁵ linii, iar pe fiecare linie câte o pereche de numere, reprezentând limitele câte unui interval orar: pe prima linie intervalul orar de care tânărul dispune zilnic, iar pe fiecare dintre următoarele linii, intervalul orar de vizitare gratuită pentru câte un muzeu, în ordinea din listă. Limitele intervalelor sunt ore fixe, numere naturale din intervalul [8,22], iar cele aflate pe aceeași linie a fișierului sunt în ordine strict crescătoare și sunt separate printr-un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două valori, reprezentând numărul de muzee convenabile, respectiv numărul de ordine al ultimului astfel de muzeu din lista tânărului.
Utilizați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține valorile alăturate, atunci pe ecran se afișează numerele 3 4.
(pot fi vizitate trei muzee cu numerele de ordine 1, 2 și 4, în intervalele 16–18, 17–19, respectiv 18–19).
16 19
15 18
17 21
19 21
18 20
12 13
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
SUBIECTUL al III-lea, 3.a.
Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă citește prima pereche din fișier (h1, h2), apoi, pe măsura citirii celorlalte perechi, se incrementează numărul de ordine al muzeului (nrCrt) și se calculează intersecția [v1,v2] dintre intervalul [h1,h2] și intervalul de timp determinat de perechea curentă [crt1,crt2], unde v1=max(h1,crt1) și v2=min(h2,crt2); dacă intersecția permite cel puțin o oră de vizită (v1<v2) se incrementează contorul cerut (nrVizitate) și se actualizează numărul de ordine al muzeului cerut (ultim=nrCrt).
SUBIECTUL al III-lea, 3.b.
Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier conform cerinței - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă citește prima pereche din fișier (h1, h2), apoi, pe măsura citirii celorlalte perechi, se incrementează numărul de ordine al muzeului (nrCrt) și se calculează intersecția [v1,v2] dintre intervalul [h1,h2] și intervalul de timp determinat de perechea curentă [crt1,crt2], unde v1=max(h1,crt1) și v2=min(h2,crt2); dacă intersecția permite cel puțin o oră de vizită (v1<v2) se incrementează contorul cerut (nrVizitate) și se actualizează numărul de ordine al muzeului cerut (ultim=nrCrt).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
La o centrală solară se monitorizează stocul zilnic de energie produsă și stocul total calculat pentru fiecare perioadă. Zilele de monitorizare sunt numerotate cu valori naturale consecutive, în ordine cronologică, începând cu ziua 1. O perioadă este formată din cel puțin două zile de monitorizare, consecutive, iar stocul total calculat pentru ea este suma stocurilor zilnice corespunzătoare. O zi este validată dacă stocul zilnic este cel puțin egal cu limita zilnică, minZ; o perioadă este validată dacă stocul total calculat pentru ea este cel puțin egal cu limita stabilită pentru perioade, minP, fiecare zi a perioadei este validată, iar perioada este maximală în raport cu această proprietate (nu i se mai poate adăuga nicio zi validată).
Fișierul text bac.in conține cel mult 10⁶ numere naturale din intervalul [1,10³]: pe prima linie minZ și minP, reprezentând limitele precizate pentru validare, iar pe a doua linie stocurile zilnice de energie produse în zile consecutive, în ordinea monitorizării. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran, pentru fiecare perioadă de producție validată, corespunzătoare datelor din fișier, câte un triplet de numere, reprezentând prima și ultima zi a perioadei, respectiv stocul total calculat pentru ea. Valorile din fiecare triplet se afișează pe câte o linie a ecranului, separate prin câte un spațiu, iar dacă nu există nicio astfel de perioadă, se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține valorile alăturate,
10 40
65 9 20 25 12 14 7 3 11 15 12 8 19 50 21
se afișează pe ecran
3 6 71
13 15 90
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3. a.
Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă citește primele două valori din fișier (minZ și minP), apoi, pe măsura citirii stocurilor zilnice, se incrementează numărul zilei curente (ziCrt), iar dacă stocul curent citit (x) corespunde unei zile validate (x≥minZ), se actualizează următoarele date corespunzătoare perioadei curente:
- prima zi (prima=ziCrt) - doar dacă stocul total al acestei perioade este nul (dacă stocCrt=0);
- ultima zi (ultima=ziCrt);
- stocul total (stocCrt=stocCrt+x);
Dacă ziua nu este validată (x<minZ) sau dacă s-a încheiat citirea, se afișează tripletul cerut (prima, ultima și stocCrt), dacă stocul total determinat corespunde unei perioade validate (stocCrt≥minP și ultima-prima≥1), apoi se reinițializează aceste trei valori cu 0.
SUBIECTUL al III-lea, 3. b.
Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier, conform cerinței - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, tratare a cazului nu exista, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă citește primele două valori din fișier (minZ și minP), apoi, pe măsura citirii stocurilor zilnice, se incrementează numărul zilei curente (ziCrt), iar dacă stocul curent citit (x) corespunde unei zile validate (x≥minZ), se actualizează următoarele date corespunzătoare perioadei curente:
- prima zi (prima=ziCrt) - doar dacă stocul total al acestei perioade este nul (dacă stocCrt=0);
- ultima zi (ultima=ziCrt);
- stocul total (stocCrt=stocCrt+x);
Dacă ziua nu este validată (x<minZ) sau dacă s-a încheiat citirea, se afișează tripletul cerut (prima, ultima și stocCrt), dacă stocul total determinat corespunde unei perioade validate (stocCrt≥minP și ultima-prima≥1), apoi se reinițializează aceste trei valori cu 0.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Fișierul numere.in conține un șir de cel mult 10⁶ numere naturale din intervalul [0,99]. Numerele din fișier sunt separate prin câte un spațiu.
Se cere să se determine primul și ultimul număr din șir care conțin cea mai mare cifră ce apare în scrierea numerelor din fișier. Numerele determinate se afișează pe ecran, în ordinea apariției lor în șir, separate printr-un spațiu. Dacă nu există două astfel de numere pe poziții distincte, se afișează pe ecran mesajul nu exista.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 34 5 38 30 87 70 11 8 82 25 se afișează pe ecran 38 82,
dacă fișierul conține numerele 34 5 38 30 87 70 11 8 38 25 se afișează pe ecran 38 38,
iar dacă fișierul conține numerele 34 5 38 30 se afișează pe ecran nu exista.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3.a.
Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului, conform cerinței (*) - 1p.
- elemente de eficiență justificate, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă citește datele din fișier și, pe măsura parcurgerii lor determină cifra maximă întâlnită (cifMax), și primul și ultimul număr dintre cele citite care conțin această cifră (p, respectiv u). Pentru fiecare număr citit x se determină cifra maximă, cm (maximul dintre x%10 și [x/10]) și, dacă cm>cifMax se actualizează cifMax, p și u (cifMax←cm, p←x, u←-1), iar dacă cm=cifMax, se actualizează u (u←x). După parcurgerea tuturor numerelor, se afișează p și u sau mesajul indicat (dacă u=-1).
SUBIECTUL al III-lea, 3.b.
Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- determinare a valorilor, conform cerinței (*),(**) - 5p.
- utilizare a unui algoritm eficient, conform cerinței (***) - 1p.
- declarare a variabilelor, afișare a datelor conform cerinței, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar (de complexitate O(n)), care utilizează eficient memoria.
O soluție posibilă citește datele din fișier și, pe măsura parcurgerii lor determină cifra maximă întâlnită (cifMax), și primul și ultimul număr dintre cele citite care conțin această cifră (p, respectiv u). Pentru fiecare număr citit x se determină cifra maximă, cm (maximul dintre x%10 și [x/10]) și, dacă cm>cifMax se actualizează cifMax, p și u (cifMax←cm, p←x, u←-1), iar dacă cm=cifMax, se actualizează u (u←x). După parcurgerea tuturor numerelor, se afișează p și u sau mesajul indicat (dacă u=-1).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
De-a lungul unui traseu montan este utilizată o succesiune de marcaje turistice, care trebuie urmate în acea ordine. Pentru fiecare marcaj se cunoaște cota (înălțimea, măsurată în metri) la care este plasat.
Numim scară într-un traseu o secvență de marcaje aflate pe poziții consecutive în cadrul traseului, care au drept cote numere consecutive, ordonate strict crescător. O scară este formată din cel puțin două marcaje, iar lungimea acesteia este egală cu numărul de marcaje care o compun.
Fișierul bac.txt conține un șir de cel mult 10⁶ numere naturale din intervalul [10,10⁴], separate prin câte un spațiu, reprezentând cotele marcajelor turistice din cadrul unui traseu, în ordinea în care se succed în acesta. Se cere să se afișeze pe ecran, separate prin câte un spațiu, în ordine strict crescătoare, cotele corespunzătoare marcajelor unei scări de lungime maximă pe acest traseu. Dacă în cadrul traseului există mai multe astfel de scări, se afișează doar cotele corespunzătoare marcajelor uneia dintre ele, iar dacă nu există nicio scară, pe ecran se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 500 600 601 405 569 570 700 701 625 626 627 520
atunci pe ecran se afișează 625 626 627
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3.a. Pentru răspuns corect: 2p.
- coerență a descrierii algoritmului (*): 1p.
- justificare a elementelor de eficiență: 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă parcurge o dată fișierul, memorând pentru scara curentă și pentru cea căutată lungimea (lgCrt, respectiv lgMax, inițial egale cu 0) și ultimul termen (ultCrt, inițializat cu 0, respectiv ultMax) ale acestora; dacă numărul x citit din fișier la pasul curent face parte din scara curentă (x=ultCrt+1) se actualizează lgCrt, altfel se actualizează datele privind o nouă scară, deci lgCrt=1. La fiecare pas se actualizează ultCrt=x și, după caz, lgMax și ultMax. Se afișează lgMax numere consecutive, primul dintre acestea fiind ultMax-lgMax+1. Mesajul se afișează dacă lgMax<2.
SUBIECTUL al III-lea, 3.b. Pentru program corect: 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier: 1p.
- determinare a valorilor cerute (*),(**): 5p.
- utilizare a unui algoritm eficient (***): 1p.
- declarare a variabilelor, afișare a datelor și tratare a cazului nu exista, corectitudine globală a programului¹): 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă parcurge o dată fișierul, memorând pentru scara curentă și pentru cea căutată lungimea (lgCrt, respectiv lgMax, inițial egale cu 0) și ultimul termen (ultCrt, inițializat cu 0, respectiv ultMax) ale acestora; dacă numărul x citit din fișier la pasul curent face parte din scara curentă (x=ultCrt+1) se actualizează lgCrt, altfel se actualizează datele privind o nouă scară, deci lgCrt=1. La fiecare pas se actualizează ultCrt=x și, după caz, lgMax și ultMax. Se afișează lgMax numere consecutive, primul dintre acestea fiind ultMax-lgMax+1. Mesajul se afișează dacă lgMax<2.
¹) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Șirul 0, 0, 1, 4, 13, 38, 105, 280, 729 ....
este definit astfel: f₁=f₂=0, f₃=1, fₙ=4·fₙ₋₁−3·fₙ₋₂−2·fₙ₋₃ (unde n este un număr natural n≥4).
Se citesc de la tastatură trei numere naturale x, y și z (x≤y<z≤10⁹), valorile a trei termeni aflați pe poziții consecutive în șirul dat, și se cere să se scrie în fișierul bac.txt, în ordine descrescătoare, separați prin câte un spațiu, toți termenii șirului care sunt mai mici sau egali cu z. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă se citesc numerele 38 105 280 fișierul conține numerele 280 105 38 13 4 1 0 0
Identificatorii utilizați în rezolvări trebuie să respecte precizările din enunț (bold), iar în lipsa unor precizări explicite, notațiile trebuie să corespundă cu semnificațiile asociate acestora (eventual în formă prescurtată). Datele de intrare se consideră corecte, validarea lor nefiind necesară.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă memorează ultimii trei termeni afișați pe poziții consecutive, în ordine descrescătoare, z, y și x (z>y≥x) și determină termenul curent (crt) pe baza celor trei termeni afișați anterior, cu formula crt=[(4·y-3·x-z)/2]; inițial se afișează, în ordine descrescătoare, cei trei termeni citiți, apoi, la fiecare pas, se determină și se afișează termenul curent și se actualizează cei trei termeni z, y și x; algoritmul se încheie după afișarea a două valori 0.
b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea scrierii, scriere în fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar (de complexitate O(n)), care utilizează eficient memoria.
O soluție posibilă memorează ultimii trei termeni afișați pe poziții consecutive, în ordine descrescătoare, z, y și x (z>y≥x) și determină termenul curent (crt) pe baza celor trei termeni afișați anterior, cu formula crt=[(4·y-3·x-z)/2]; inițial se afișează, în ordine descrescătoare, cei trei termeni citiți, apoi, la fiecare pas, se determină și se afișează termenul curent și se actualizează cei trei termeni z, y și x; algoritmul se încheie după afișarea a două valori 0.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Intervalul [x,y] se numește p-interval pentru un șir de valori întregi, dacă oricare dintre primii p termeni ai șirului aparține intervalului, iar numărul de valori întregi distincte din interval este minim.
Exemplu: pentru șirul 2, 7, −1, 8, 3, 10 există [2,2] ca 1-interval, [−1,8] ca 4-interval și 5-interval etc.
Fișierul bac.in conține un șir de cel mult 10⁶ numere întregi din intervalul [−10⁹,10⁹], separate prin câte un spațiu.
Se cere să se afișeze pe ecran cea mai mică și cea mai mare valoare a lui p (p≥2) cu proprietatea că (p−1)-interval este identic cu p-interval pentru șirul aflat în fișier. Valorile afișate pot fi egale, iar dacă nu există nicio astfel de valoare, pe ecran se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele 2 7 1 8 3 10 6 −3 −2 13, se afișează pe ecran 5 9 (intervale conform cerinței se obțin pentru valorile 5, 7 și 9 ale lui p), iar dacă fișierul conține numerele 2 7 1 0 8 10 −3 13, se afișează pe ecran nu exista.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
Reguli generale:
SUBIECTUL al III-lea, 3. a.
Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului, conform cerinței (*) - 1p.
- elemente de eficiență justificate, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă determină, pe măsura citirii datelor, valorile minime și maxime curente (minc, maxc, inițializate cu 10⁹+1, respectiv cu −10⁹−1) dintre cele citite, poziția curentă în șir (p), precum și valorile cerute pmin și pmax. Pentru fiecare valoare citită (x), p este incrementat; dacă x∈[minc,maxc], atunci se actualizează, după caz, pmin (la prima apariție a unui astfel de caz) sau pmax (la fiecare apariție a unui astfel de caz), care primesc valoarea curentă a lui p; dacă x∉[minc,maxc], se actualizează, după caz, minc (dacă x<minc) sau maxc (dacă x>maxc). Valorile cerute sunt pmin și pmax.
SUBIECTUL al III-lea, 3. b.
Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- valori determinate, conform cerinței (*),(**) - 5p.
- eficiență a algoritmului, conform cerinței (***) - 1p.
- variabile declarate, afișare a datelor conform cerinței, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă determină, pe măsura citirii datelor, valorile minime și maxime curente (minc, maxc, inițializate cu 10⁹+1, respectiv cu −10⁹−1) dintre cele citite, poziția curentă în șir (p), precum și valorile cerute pmin și pmax. Pentru fiecare valoare citită (x), p este incrementat; dacă x∈[minc,maxc], atunci se actualizează, după caz, pmin (la prima apariție a unui astfel de caz) sau pmax (la fiecare apariție a unui astfel de caz), care primesc valoarea curentă a lui p; dacă x∉[minc,maxc], se actualizează, după caz, minc (dacă x<minc) sau maxc (dacă x>maxc). Valorile cerute sunt pmin și pmax.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Un număr natural x este numit prefix al unui număr natural y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la dreapta sa, și este numit sufix al lui y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la stânga sa.
Exemplu: 15 este prefix pentru 154 sau 1521, este sufix pentru 3415 sau 5115, dar nu este nici prefix, nici sufix pentru 15.
Fișierul bac.txt conține maximum 10⁶ numere naturale din intervalul [10,10⁴), separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul valorilor de două cifre care apar de același număr de ori ca sufix, respectiv ca prefix al numerelor din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul
342 1684 2134 5434 111 98 98 3405 3412 7016 8634 1010 102 310
se afișează pe ecran: 4 (pentru valorile 10, 11, 16, 34).
Identificatorii utilizați în rezolvări trebuie să respecte precizările din enunț (bold), iar în lipsa unor precizări explicite, notațiile trebuie să corespundă cu semnificațiile asociate acestora (eventual în formă prescurtată). Datele de intrare se consideră corecte, validarea lor nefiind necesară.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
Reguli generale:
SUBIECTUL al III-lea, 3. a. Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului, conform cerinței (*) - 1p.
- elemente de eficiență justificate, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează doi vectori de frecvență, pf și sf, în care pf[i] memorează numărul de apariții ale prefixului i în numerele din fișier, iar sf[i] memorează numărul de apariții ale sufixului i în numerele din fișier. Pe parcursul citirii datelor, se determină, pentru fiecare număr x citit (x>99), sufixul (x%100), respectiv prefixul ([x/10] sau [x/100], în funcție de numărul de cifre ale lui x) și se actualizează corespunzător cei doi vectori de frecvență. După citirea tuturor numerelor se contorizează toate valorile x∈[10,99] pentru care sf[x]=pf[x] și sf[x]≠0.
SUBIECTUL al III-lea, 3. b. Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- valoare determinată, conform cerinței (*),(**) - 5p.
- eficiență a algoritmului, conform cerinței (***) - 1p.
- variabile declarate, afișare a datelor conform cerinței, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează doi vectori de frecvență, pf și sf, în care pf[i] memorează numărul de apariții ale prefixului i în numerele din fișier, iar sf[i] memorează numărul de apariții ale sufixului i în numerele din fișier. Pe parcursul citirii datelor, se determină, pentru fiecare număr x citit (x>99), sufixul (x%100), respectiv prefixul ([x/10] sau [x/100], în funcție de numărul de cifre ale lui x) și se actualizează corespunzător cei doi vectori de frecvență. După citirea tuturor numerelor se contorizează toate valorile x∈[10,99] pentru care sf[x]=pf[x] și sf[x]≠0.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Fișierul date.in conține pe prima linie două numere naturale din intervalul [1,10⁶], m și n, iar pe următoarele două linii numere naturale din intervalul [0,10²): pe a doua linie un șir A, de m numere, iar pe a treia linie un șir B, de n numere. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul maxim de perechi de forma (pa,pb) (pa∈[1,m], pb∈[1,n]), cu proprietatea că termenul de pe poziția pa din șirul A are aceeași valoare cu termenul de pe poziția pb din șirul B și că fiecare poziție, corespunzătoare șirului A, respectiv șirului B, apare în cel mult o pereche, ca în exemplu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele alăturate, se afișează pe ecran 6 (de exemplu, pentru perechile (1,1), (2,9), (4,2), (5,5), (6,6), (7,7) sau pentru perechile (1,2), (2,9), (4,1), (5,7), (6,8), (8,5)).
8 9
1 0 4 1 5 3 5 5
1 1 1 7 5 3 5 3 0
Identificatorii utilizați în rezolvări trebuie să respecte precizările din enunț (bold), iar în lipsa unor precizări explicite, notațiile trebuie să corespundă cu semnificațiile asociate acestora (eventual în formă prescurtată). Datele de intrare se consideră corecte, validarea lor nefiind necesară.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
3. a. Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului, conform cerinței (*) - 1p.
- elemente de eficiență justificate, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează doi vectori de frecvență, fie aceștia a și b, unde aᵢ este numărul aparițiilor valorii i în primul șir, iar bᵢ este numărul aparițiilor valorii i în al doilea șir; vectorii sunt completați pe măsura citirii datelor din fișier, iar numărul afișat se obține ulterior prin însumarea valorilor min(aᵢ,bᵢ).
3. b. Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- valoare determinată, conform cerinței (*),(**) - 5p.
- eficiență a algoritmului, conform cerinței (***) - 1p.
- variabile declarate, afișare a datelor conform cerinței, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează doi vectori de frecvență, fie aceștia a și b, unde aᵢ este numărul aparițiilor valorii i în primul șir, iar bᵢ este numărul aparițiilor valorii i în al doilea șir; vectorii sunt completați pe măsura citirii datelor din fișier, iar numărul afișat se obține ulterior prin însumarea valorilor min(aᵢ,bᵢ).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Numim secvență progresivă a unui șir crescător de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că fiecare termen apare în subșir de un număr de ori egal cu valoarea sa. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir crescător de cel mult 10⁶ numere naturale din intervalul [1,10⁶], astfel încât orice termen al șirului apare de un număr de ori cel mult egal cu valoarea sa. Numerele sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran lungimea maximă a unei secvențe progresive din șirul aflat în fișier.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele
1 2 2 3 4 4 4 4 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8
atunci pe ecran se afișează valoarea 10.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a) Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă parcurge datele din fișier memorând ultimele două valori citite (fie ele x, y), lungimea secvenței curente de valori egale (fie ea ny) și lungimea secvenței progresive curente (lgcrt); pentru fiecare pereche (x,y) pentru care x=y se incrementează ny; la finalul fiecărei secvențe de valori egale (x≠y), dacă ny=x se actualizează corespunzător lgcrt și, după caz, lungimea maximă cerută, iar altfel, dacă ny<x, se reinițializează lgcrt cu 0. Pentru ultima secvență de valori egale se actualizează datele la final.
b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar care utilizează eficient memoria.
O soluție posibilă parcurge datele din fișier memorând ultimele două valori citite (fie ele x, y), lungimea secvenței curente de valori egale (fie ea ny) și lungimea secvenței progresive curente (lgcrt); pentru fiecare pereche (x,y) pentru care x=y se incrementează ny; la finalul fiecărei secvențe de valori egale (x≠y), dacă ny=x se actualizează corespunzător lgcrt și, după caz, lungimea maximă cerută, iar altfel, dacă ny<x, se reinițializează lgcrt cu 0. Pentru ultima secvență de valori egale se actualizează datele la final.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Fișierul bac.txt conține numere naturale din intervalul [1,10⁹], astfel: pe prima linie două numere, x și y (x<y), iar pe a doua linie un șir de cel mult 10⁶ numere, ordonate crescător. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de valori distincte din șirul aflat pe a doua linie a fișierului care aparțin intervalului [x,y]. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul are conținutul alăturat, pe ecran se afișează 6.
Conținutul fișierului:
2 9
1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 21 21
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
Reguli generale:
SUBIECTUL al III-lea, 3. a)
Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
Se memorează ultimele două valori citite, în această ordine, ant și crt, precum și numărul cerut, nr.
O soluție posibilă inițializează numărul ant cu 0 și parcurge datele din fișier citind valoarea curentă crt (eventual cât timp crt≤y), incrementând numărul nr pentru fiecare valoare distinctă din șir (crt≠ant) din intervalul cerut (crt≥x și crt≤y); valoarea ant se actualizează la fiecare pas.
SUBIECTUL al III-lea, 3. b)
Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar care utilizează eficient memoria.
Se memorează ultimele două valori citite, în această ordine, ant și crt, precum și numărul cerut, nr.
O soluție posibilă inițializează numărul ant cu 0 și parcurge datele din fișier citind valoarea curentă crt (eventual cât timp crt≤y), incrementând numărul nr pentru fiecare valoare distinctă din șir (crt≠ant) din intervalul cerut (crt≥x și crt≤y); valoarea ant se actualizează la fiecare pas.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Numim secvență paritară a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași paritate, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir de cel puțin două și cel mult 10⁶ numere naturale din intervalul [0,10⁹]. Numerele sunt separate prin câte un spațiu, iar în șir există cel puțin doi termeni cu aceeași paritate pe poziții consecutive.
Se cere să se afișeze pe ecran numărul secvențelor paritare de lungime maximă din șirul aflat în fișier, precum și această lungime maximă. Numerele afișate sunt separate printr-un spațiu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele
2 3 5 1 7 9 8 4 4 11 15 17 21 11 6 11 15 17 21 11 6 5 2 6 4 0 16
atunci pe ecran se afișează valorile 4 5
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
3. a) Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă parcurge datele din fișier și memorează în variabilele x și y ultimii doi termeni citiți; dacă x%2≠y%2, inițializează lungimea secvenței curente, iar dacă x%2=y%2, incrementează lungimea secvenței curente și actualizează, după caz, lungimea maximă și incrementează sau inițializează numărul secvențelor cerute.
3. b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar care utilizează eficient memoria.
O soluție posibilă parcurge datele din fișier și memorează în variabilele x și y ultimii doi termeni citiți; dacă x%2≠y%2, inițializează lungimea secvenței curente, iar dacă x%2=y%2, incrementează lungimea secvenței curente și actualizează, după caz, lungimea maximă și incrementează sau inițializează numărul secvențelor cerute.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Se consideră șirul 1, 3, 7, 13, 21, 31, 43 ... definit astfel: f₀=1, iar fₙ=fₙ₋₁+2·n, dacă n≥1 (unde n este un număr natural).
Se citesc de la tastatură două numere naturale din intervalul [1,10⁹], x și y (x<y), reprezentând doi termeni aflați pe poziții consecutive în șirul dat, și se cere să se scrie în fișierul text bac.out, separați prin câte un spațiu, toți termenii șirului mai mici sau egali cu y, în ordine inversă a apariției lor în șir.
Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie și al timpului de executare.
Exemplu: dacă x=21 și y=31, fișierul conține valorile
31 21 13 7 3 1
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a) Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă determină valoarea lui n, corespunzătoare termenului fₙ=y, pe baza expresiei n=(y-x)/2; se generează termenii șirului mai mici decât y pe baza relației fₙ=x=y-2·(n+1), unde x, y și n se actualizează corespunzător, la fiecare pas.
O altă soluție posibilă nu utilizează deloc valoarea lui x, ci deduce formula termenului general ca fiind fₙ=1+n·(n+1) și determină valoarea lui n corespunzătoare termenului fₙ=y rezolvând ecuația n²+n-y+1=0; se generează termenii fₙ ai șirului pe baza formulei deduse, unde n se actualizează corespunzător, la fiecare pas.
3. b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea scrierii, scriere în fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, citire a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar care utilizează eficient memoria.
O soluție posibilă determină valoarea lui n, corespunzătoare termenului fₙ=y, pe baza expresiei n=(y-x)/2; se generează termenii șirului mai mici decât y pe baza relației fₙ=x=y-2·(n+1), unde x, y și n se actualizează corespunzător, la fiecare pas.
O altă soluție posibilă nu utilizează deloc valoarea lui x, ci deduce formula termenului general ca fiind fₙ=1+n·(n+1) și determină valoarea lui n corespunzătoare termenului fₙ=y rezolvând ecuația n²+n-y+1=0; se generează termenii fₙ ai șirului pe baza formulei deduse, unde n se actualizează corespunzător, la fiecare pas.
¹⁾ Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Numărul natural a se numește sufix al numărului natural b dacă a este egal cu b sau dacă b se poate obține din a prin alipirea la stânga a unor noi cifre.
Fișierul bac.txt conține pe prima linie un număr natural x (x∈[100,999]), iar pe a doua linie un șir de cel mult 10⁵ numere naturale din intervalul [0,10⁹]. Numerele din șir sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran ultimii doi termeni ai șirului, aflați pe poziții consecutive în acesta, care îl au drept sufix pe numărul x. Numerele sunt afișate în ordinea în care apar în șir, separate printr-un spațiu, iar dacă nu există doi astfel de termeni, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține numerele alăturate, atunci pe ecran se afișează 3210 15210.
Conținutul fișierului din exemplu:
210
3445 210 893210 1245 1210 3210 15210 67120 20210 12
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a) Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă citește prima valoare din fișier (x), apoi, pe măsura citirii celorlalte valori, memorează valoarea curentă (crt), și penultima valoare citită (ant), precum și ultimele două numere cu proprietatea cerută (pu și u, inițializate cu -1); ant se actualizează la fiecare pas (ant=crt), iar pu și u se actualizează doar dacă crt mod 1000=x și ant mod 1000=x (pu=ant și u=crt).
b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar care utilizează eficient memoria.
O soluție posibilă citește prima valoare din fișier (x), apoi, pe măsura citirii celorlalte valori, memorează valoarea curentă (crt), și penultima valoare citită (ant), precum și ultimele două numere cu proprietatea cerută (pu și u, inițializate cu -1); ant se actualizează la fiecare pas (ant=crt), iar pu și u se actualizează doar dacă crt mod 1000=x și ant mod 1000=x (pu=ant și u=crt).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Numim pereche asemenea (x,y) două numere naturale cu cel puțin două cifre, x și y, cu proprietatea că ultimele două cifre ale lui x sunt egale cu ultimele două cifre ale lui y, dispuse eventual în altă ordine.
Fișierul numere.in conține numere naturale din intervalul [10,10⁵]: pe prima linie două numere na și nb, pe a doua linie un șir A de na numere, iar pe a treia linie un șir B de nb numere. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de perechi asemenea (x,y), cu proprietatea că x este un termen al șirului A, iar y este un termen al șirului B. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
9 7
112 20 42 112 5013 824 10012 55 155
402 1024 321 521 57 6542 255
se afișează pe ecran numărul
13
deoarece sunt 13 perechi asemenea: (112,321), (112,521), (20,402), (42,1024), (42,6542), (112,321), (112,521), (824,1024), (824,6542), (10012,321), (10012,521), (55,255), (155,255).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a) Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează un vector de frecvență v în care vᵢ reprezintă numărul de valori x din șirul A pentru care i=x%100 (i∈[0,99]). Vectorul v se actualizează pe măsura parcurgerii celei de a doua linii a fișierului. Se determină numărul cerut nr pe măsura parcurgerii numerelor de pe a treia linie a fișierului: pentru fiecare număr curent y din șirul B se determină ultimele două cifre ale sale, c1 și c2 și numerele i și j, unde i=c1*10+c2, iar j=c2*10+c1, apoi se adună la nr valoarea vᵢ și, dacă i≠j, se adună la nr și vⱼ.
O altă soluție utilizează câte un vector de frecvență pentru fiecare șir, va și vb, cu aceeași semnificație ca mai sus. Vectorii se completează pe măsura citirii fiecărui șir, iar numărul cerut se obține la final, prin parcurgerea vectorului vb și pentru fiecare i∈[0,99], se determină ultimele două cifre ale sale, c1 și c2 și numărul j, unde j=c2*10+c1, apoi se adună la nr valoarea vbᵢ·vaᵢ și, dacă i≠j, se adună la nr și vbᵢ·vaⱼ.
b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un vector de frecvență v în care vᵢ reprezintă numărul de valori x din șirul A pentru care i=x%100 (i∈[0,99]). Vectorul v se actualizează pe măsura parcurgerii celei de a doua linii a fișierului. Se determină numărul cerut nr pe măsura parcurgerii numerelor de pe a treia linie a fișierului: pentru fiecare număr curent y din șirul B se determină ultimele două cifre ale sale, c1 și c2 și numerele i și j, unde i=c1*10+c2, iar j=c2*10+c1, apoi se adună la nr valoarea vᵢ și, dacă i≠j, se adună la nr și vⱼ.
O altă soluție utilizează câte un vector de frecvență pentru fiecare șir, va și vb, cu aceeași semnificație ca mai sus. Vectorii se completează pe măsura citirii fiecărui șir, iar numărul cerut se obține la final, prin parcurgerea vectorului vb și pentru fiecare i∈[0,99], se determină ultimele două cifre ale sale, c1 și c2 și numărul j, unde j=c2*10+c1, apoi se adună la nr valoarea vbᵢ·vaᵢ și, dacă i≠j, se adună la nr și vbᵢ·vaⱼ.
¹⁾ Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Se citește de la tastatură un număr natural, n (n∈[1,10⁹]), și se cere să se scrie în fișierul text bac.txt cel mai mare număr natural p cu proprietatea că numărul 26ᵖ este divizor al numărului obținut prin calcularea produsului 1·2·3·...·n.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă n=28, atunci fișierul conține numărul 2 (26²=676 este divizor al lui 1·2·3·..·28 = 304888344611713860501504000000)
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă are în vedere că 26=13·2 și parcurge numerele naturale din intervalul [2,n], determinând pentru fiecare număr curent k, din acest interval, numărul t de apariții ale lui 13, în descompunerea în factori primi a lui k, și realizând pe parcurs suma tuturor valorilor t determinate (p). Valoarea cerută este p.
O altă soluție posibilă determină valoarea p astfel:
p=[n/13]+[n/13²]+[n/13³]+[n/13⁴]+ ...+0
Se citește de la tastatură un număr natural, n (n∈[1,10⁹]), și se cere să se scrie în fișierul text bac.txt cel mai mare număr natural p cu proprietatea că numărul 26ᵖ este divizor al numărului obținut prin calcularea produsului 1·2·3·...·n.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă n=28, atunci fișierul conține numărul 2 (26²=676 este divizor al lui 1·2·3·..·28 = 304888344611713860501504000000)
Identificatorii utilizați în rezolvări trebuie să respecte precizările din enunț (bold), iar în lipsa unor precizări explicite, notațiile trebuie să corespundă cu semnificațiile asociate acestora (eventual în formă prescurtată). Datele de intrare se consideră corecte, validarea lor nefiind necesară.
b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea scrierii, scriere în fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, citire a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm cel mult liniar care utilizează eficient memoria.
O soluție posibilă are în vedere că 26=13·2 și parcurge numerele naturale din intervalul [2,n], determinând pentru fiecare număr curent k, din acest interval, numărul t de apariții ale lui 13, în descompunerea în factori primi a lui k, și realizând pe parcurs suma tuturor valorilor t determinate (p). Valoarea cerută este p.
O altă soluție posibilă determină valoarea p astfel:
p=[n/13]+[n/13²]+[n/13³]+[n/13⁴]+ ...+0
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Fișierul bac.txt conține numere naturale din intervalul [1,10⁹]: pe prima linie două numere, x și y (x<y), iar pe a doua linie un șir de cel mult 10⁶ numere, ordonate crescător, separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de valori pare distincte, din șirul aflat pe a doua linie a fișierului, care aparțin intervalului [x,y]. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul are conținutul alăturat, pe ecran se afișează 3.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
Se memorează ultimele două valori citite, în această ordine, ant și crt, precum și numărul cerut, nr.
O soluție posibilă inițializează numărul ant cu 0 și parcurge datele din fișier citind valoarea curentă crt (eventual cât timp crt≤y), incrementând numărul nr pentru fiecare valoare pară distinctă din șir (crt≠ant) din intervalul cerut (crt≥x și crt≤y); valoarea ant se actualizează la fiecare pas.
3. b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar care utilizează eficient memoria.
Se memorează ultimele două valori citite, în această ordine, ant și crt, precum și numărul cerut, nr.
O soluție posibilă inițializează numărul ant cu 0 și parcurge datele din fișier citind valoarea curentă crt (eventual cât timp crt≤y), incrementând numărul nr pentru fiecare valoare pară distinctă din șir (crt≠ant) din intervalul cerut (crt≥x și crt≤y); valoarea ant se actualizează la fiecare pas.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
3. Șirul 1, 2, 2, 5, 4, 11, 8, 23, 16, 47....
este definit astfel: f₀=1, iar pentru orice n, număr natural strict pozitiv, fₙ=3·fₙ₋₁ − 1, dacă n este impar, sau fₙ=2·fₙ₋₂, dacă n este par.
Se citește de la tastatură un număr natural x (x∈[4,10⁹]), termen al șirului dat. Se cere să se scrie în fișierul bac.txt, în ordinea inversă apariției în șir, separați prin câte un spațiu, atât termenul citit, cât și toți cei care îl preced în șir pe acesta, ca în exemplu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă x=8, fișierul conține numerele 8 11 4 5 2 2 1
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a. Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă scrie valoarea x și o actualizează la [x/2]·3-1, doar dacă aceasta este pară, apoi, la fiecare pas scrie câte o pereche de termeni, x și [(x+1)/3], și actualizează valoarea lui x la [(x-1)/2]. Generarea se repetă cât timp x≥2.
3. b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea scrierii, scriere în fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, citire a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge toți pașii necesari rezolvării, dar cu detalii care nu conduc la rezultatul cerut.
(***) Se acordă punctajul numai pentru un algoritm liniar (de complexitate O(n)), care utilizează eficient memoria.
O soluție posibilă scrie valoarea x și o actualizează la [x/2]·3-1, doar dacă aceasta este pară, apoi, la fiecare pas scrie câte o pereche de termeni, x și [(x+1)/3], și actualizează valoarea lui x la [(x-1)/2]. Generarea se repetă cât timp x≥2.
¹⁾ Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
La o expoziție auto se află, în șir, mașini de epocă, fiecare având câte un cod, format prin alipirea, în această ordine, a două numere naturale nenule: identificatorul colecționarului care deține mașina, respectiv anul fabricației acesteia.
Fișierul bac.txt conține numere naturale: pe prima linie un număr x (x∈[1880,1950]), reprezentând un an calendaristic, iar pe a doua linie cel mult 10⁵ numere din intervalul [10⁴,10⁹], reprezentând codurile mașinilor, în ordinea din șirul în care sunt expuse. Numerele aflate pe aceeași linie în fișier sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran identificatorii colecționarilor care dețin ultimele două mașini, din șirul celor expuse, ambele fiind fabricate în anul x și aflate în șir pe poziții consecutive, ca în exemplu. Numerele, nu neapărat distincte, sunt afișate în ordinea în care mașinile corespunzătoare apar în șir, separate printr-un spațiu, iar dacă nu există două astfel de mașini, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fișierul conține numerele
1925
31885 21925 8931925 31925 121900 11925 31925 151925 61950 201925 121880
atunci pe ecran se afișează 3 15
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3. a.
Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă citește prima valoare din fișier (x), apoi, pe măsura citirii celorlalte valori, memorează codul curent (crt) și penultimul cod (ant) citite, precum și ultimii doi identificatori cu proprietatea cerută (pu și u, inițializați cu -1); ant se actualizează la fiecare pas (ant=crt), iar pu și u se actualizează doar dacă ant mod 10000=crt mod 10000=x (pu=[ant/10000] și u=[crt/10000]).
SUBIECTUL al III-lea, 3. b.
Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă citește prima valoare din fișier (x), apoi, pe măsura citirii celorlalte valori, memorează codul curent (crt) și penultimul cod (ant) citite, precum și ultimii doi identificatori cu proprietatea cerută (pu și u, inițializați cu -1); ant se actualizează la fiecare pas (ant=crt), iar pu și u se actualizează doar dacă ant mod 10000=crt mod 10000=x (pu=[ant/10000] și u=[crt/10000]).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Pentru o paradă a modei sunt pregătite seturi de bijuterii, un set fiind format din cercei și pandantiv, cu câte cel puțin două pietre prețioase și semiprețioase. Sunt utilizate nouă tipuri de pietre, numerotate de la 1 la 9, iar orice bijuterie are o etichetă, număr natural în care fiecare cifră corespunde unei pietre din montură, în ordinea descrescătoare a importanței în cadrul modelului. Un set este potrivit dacă cele mai importante două pietre ale fiecărei bijuterii din set sunt de același tip, chiar dacă nu în aceeași ordine a importanței.
Fișierul bijuterii.in conține numere naturale din intervalul [10,999]: pe prima linie două numere nc și np, reprezentând numărul de cercei, respectiv de pandantive disponibile, pe a doua linie un șir de nc numere, reprezentând etichetele cerceilor, iar pe a treia linie un șir de np numere, reprezentând etichetele pandantivelor. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă se poate forma cel puțin un set potrivit de bijuterii, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele alăturate, se afișează pe ecran mesajul DA
(două dintre cele 14 seturi potrivite se pot forma din cerceii cu eticheta 258 și fiecare dintre pandantivele cu etichetele 259, respectiv 52, pentru toate aceste bijuterii pietrele de tipurile 2 și 5 fiind cele mai importante).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
SUBIECTUL al III-lea, 3.a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează un vector de apariții pentru cercei, ac, în care acᵢ (i∈[11,99]) este 1 dacă există cel puțin o bijuterie (cercei) cu codul x pentru care i=[x/10] (dacă x∈[111,999]) sau i=x (dacă x∈[11,99]). Vectorul ac se completează pe măsura citirii datelor referitoare la cercei, iar la parcurgerea datelor referitoare la pandantive, pentru fiecare etichetă, p, se determină primele două cifre ale sale, p1 și p2 și numerele i și j, unde i=p1*10+p2, iar j=p2*10+p1, iar rezultatul este DA, în cazul în care există cel puțin o valoare p pentru care acᵢ sau acⱼ sunt nenule, sau este NU, în caz contrar.
SUBIECTUL al III-lea, 3.b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-verificare a proprietății cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un vector de apariții pentru cercei, ac, în care acᵢ (i∈[11,99]) este 1 dacă există cel puțin o bijuterie (cercei) cu codul x pentru care i=[x/10] (dacă x∈[111,999]) sau i=x (dacă x∈[11,99]). Vectorul ac se completează pe măsura citirii datelor referitoare la cercei, iar la parcurgerea datelor referitoare la pandantive, pentru fiecare etichetă, p, se determină primele două cifre ale sale, p1 și p2 și numerele i și j, unde i=p1*10+p2, iar j=p2*10+p1, iar rezultatul este DA, în cazul în care există cel puțin o valoare p pentru care acᵢ sau acⱼ sunt nenule, sau este NU, în caz contrar.
¹⁾ Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
La o loterie se generează aleatoriu un șir de numere naturale și pentru fiecare număr generat, se inversează ordinea cifrelor. Dintre valorile distincte obținute se extrag trei numere, în această ordine: cel mai mic, cel mai mare dintre cele rămase, apoi cel mai mic dintre cele rămase.
Fișierul text bac.in conține cel mult 10⁶ numere naturale din intervalul [1001,9999], cu cifra unităților nenulă, separate prin câte un spațiu, reprezentând termenii șirului generat aleatoriu în vederea extragerii.
Scrieți un program C/C++ care afișează pe ecran cele trei numere, în ordinea extragerii acestora. Numerele afișate sunt separate prin câte un spațiu, iar dacă nu există trei astfel de numere distincte, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul conține numerele 1114 3212 3217 2855 7309 2131 2131 1238 7893
se afișează pe ecran, în această ordine, numerele 1312 9037 2123
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3.a. Pentru răspuns corect - 2p.
-descriere coerentă a algoritmului (*) - 1p.
-justificare a elementelor de eficiență, conform cerinței - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă determină, pe măsura citirii datelor din fișier, cele mai mici două valori, respectiv cea mai mare valoare dintre cele distincte, obținute după inversarea cifrelor (min1, min2 și max, min1<min2<max). Pentru fiecare valoare x citită se determină valoarea obținută prin inversarea ordinii cifrelor (y); dacă y<min1, se actualizează atât min2, cât și min1 (min2=min1, min1=y), altfel, dacă y>min1 și y<min2, se actualizează min2 (min2=y), iar altfel dacă y>max și y>min2 se actualizează max (max=y).
3.b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier, conform cerinței - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor și tratare a cazului nu exista, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul parcurge pașii necesari rezolvării, dar cu detalii care conduc la o rezolvare parțială.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă determină, pe măsura citirii datelor din fișier, cele mai mici două valori, respectiv cea mai mare valoare dintre cele distincte, obținute după inversarea cifrelor (min1, min2 și max, min1<min2<max). Pentru fiecare valoare x citită se determină valoarea obținută prin inversarea ordinii cifrelor (y); dacă y<min1, se actualizează atât min2, cât și min1 (min2=min1, min1=y), altfel, dacă y>min1 și y<min2, se actualizează min2 (min2=y), iar altfel dacă y>max și y>min2 se actualizează max (max=y).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
La un concurs se acordă premiile I, al II-lea și al III-lea. Fiecare premiant este recompensat cu câte o carte, care are un preț egal pentru toți cei cu același premiu. Prețurile cărților alese pentru premiile I, al II-lea și al III-lea sunt stabilite astfel încât să fie în ordine strict descrescătoare, iar pentru fiecare premiu să se ia în considerare cel mai mare preț pentru care există suficiente cărți propuse, în condițiile precizate.
Fișierul bac.txt conține pe prima linie trei numere naturale din intervalul [1,20], n1, n2 și n3, reprezentând numărul concurenților care primesc premiile I, al II-lea, respectiv al III-lea, iar pe a doua linie un șir de cel mult 10⁶ numere naturale din intervalul [10,10³], separate prin câte un spațiu, fiecare număr reprezentând prețul unei cărți propuse pentru premiere.
Se cere să se afișeze pe ecran, separate prin câte un spațiu, în ordine strict descrescătoare, prețurile cărților alese, corespunzătoare celor trei premii, iar dacă nu există trei astfel de prețuri, se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține valorile
3 2 4
500 100 25 100 200 100 20 10 200 100 75 52 52 15 52 20 20 10 30 20 15 100
se afișează pe ecran, în această ordine, numerele 100 52 20.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3. a)
Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului (*) - 1p.
- justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează un vector de apariții, ap, unde apₚ memorează numărul de apariții ale prețului p în șirul celor propuse. Pe măsura citirii datelor din fișier se actualizează apₚ pentru fiecare valoare p citită. Valorile cerute, x, y și z (x>y>z, inițializate cu valori nule), se determină prin parcurgerea vectorului de apariții în ordine descrescătoare a lui p și memorând primele prețuri p adecvate pentru fiecare premiu, astfel: dacă apₚ≥n1 și încă nu s-a determinat un preț pentru premiul I (x=0), atunci x=p; dacă apₚ≥n2 și s-a determinat un preț pentru premiul I, dar nu și pentru premiul al II-lea (x≠0, dar y=0), atunci y=p; dacă apₚ≥n3 și s-a determinat un preț pentru premiul al II-lea, dar nu și pentru premiul al III-lea (y≠0, dar z=0), atunci z=p. Algoritmul se încheie dacă z≠0 sau dacă s-a încheiat parcurgerea vectorului de apariții. Dacă după parcurgerea vectorului de apariții z=0, atunci se afișează mesajul indicat.
SUBIECTUL al III-lea, 3. b)
Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- determinare a valorilor cerute (*),(**) - 5p.
- utilizare a unui algoritm eficient (***) - 1p.
- declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un vector de apariții, ap, unde apₚ memorează numărul de apariții ale prețului p în șirul celor propuse. Pe măsura citirii datelor din fișier se actualizează apₚ pentru fiecare valoare p citită. Valorile cerute, x, y și z (x>y>z, inițializate cu valori nule), se determină prin parcurgerea vectorului de apariții în ordine descrescătoare a lui p și memorând primele prețuri p adecvate pentru fiecare premiu, astfel: dacă apₚ≥n1 și încă nu s-a determinat un preț pentru premiul I (x=0), atunci x=p; dacă apₚ≥n2 și s-a determinat un preț pentru premiul I, dar nu și pentru premiul al II-lea (x≠0, dar y=0), atunci y=p; dacă apₚ≥n3 și s-a determinat un preț pentru premiul al II-lea, dar nu și pentru premiul al III-lea (y≠0, dar z=0), atunci z=p. Algoritmul se încheie dacă z≠0 sau dacă s-a încheiat parcurgerea vectorului de apariții. Dacă după parcurgerea vectorului de apariții z=0, atunci se afișează mesajul indicat.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Un șir se numește de tip api dacă numărul de apariții ale fiecărui termen este mai mic sau egal cu acel termen și are o paritate egală cu a acestuia.
Fișierul bac.in conține un șir de cel mult 10⁶ numere naturale din intervalul [1,10³], separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă șirul este de tip api, sau mesajul NU în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 6 27 2 6 27 6 6 14 14 2 27 se afișează pe ecran DA
(termenul par 6 apare de 4 ori, 4 fiind tot număr par și 4≤6, termenii pari 2 și 14 apar de câte 2 ori, 2 fiind tot număr par și 2≤2, respectiv 2≤14, iar termenul impar 27 apare de 3 ori, 3 fiind tot număr impar și 3≤27).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
3. a. Pentru răspuns corect - 2p.
- descriere coerentă a algoritmului (*) - 1p.
- justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
b. Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- verificare a proprietății cerute (*),(**) - 5p.
- utilizare a unui algoritm eficient (***) - 1p.
- declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un vector de apariții, ap, unde apᵢ memorează numărul de apariții ale valorii i în șirul dat. Pe măsura citirii datelor din fișier se actualizează apᵢ pentru fiecare valoare i citită. După citirea tuturor termenilor șirului se parcurg toate elementele tabloului apᵢ, pentru verificarea proprietății cerute: variabila ok (inițial ok=1) se actualizează corespunzător (ok=0) dacă există o valoare i care a apărut în șir (apᵢ≠0), dar apᵢ%2≠i%2 sau apᵢ>i. După parcurgerea vectorului de apariții se afișează mesajul DA, dacă ok=1 sau NU, în caz contrar.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
O pereche de numere naturale (x,y) se numește p-ordonată dacă x și y au paritate diferită, cu x>y, sau dacă x și y au aceeași paritate.
Exemplu: (7,4), (8,7), (7,9) sunt perechi p-ordonate, dar (7,8), (8,9) nu sunt perechi p-ordonate.
Un șir, format din 2·n numere naturale, se numește p-ordonat dacă perechile de forma (x,y) sunt p-ordonate, pentru orice x, dintre primii n termeni ai șirului, și orice y, dintre ultimii n termeni ai șirului.
Fișierul bac.txt conține numere naturale din intervalul [0,10⁶]: pe prima linie un număr nenul, n, iar pe a doua linie un șir de 2·n numere, separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, în cazul în care șirul aflat în fișier este p-ordonat, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul are unul dintre conținuturile de mai jos, se afișează pe ecran mesajul DA.
5
22 37 21 8 15 2 3 14 4 5
5
22 36 20 8 14 44 42 4 2 5
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
a) Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă determină, pe măsura citirii datelor, cel mai mic număr par (p1), respectiv cel mai mic număr impar (i1), dintre primele n numere din șir, precum și cel mai mare număr par (p2), respectiv cel mai mare număr impar (i2) dintre ultimele n numere din șir. Inițial, p1=i1=1000001, p2=i2=-1. Șirul are proprietatea cerută dacă p1>i2 și i1>p2
b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-verificare a proprietății cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă determină, pe măsura citirii datelor, cel mai mic număr par (p1), respectiv cel mai mic număr impar (i1), dintre primele n numere din șir, precum și cel mai mare număr par (p2), respectiv cel mai mare număr impar (i2) dintre ultimele n numere din șir. Inițial, p1=i1=1000001, p2=i2=-1. Șirul are proprietatea cerută dacă p1>i2 și i1>p2
¹ Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Pentru a studia un metal, s-a urmărit comportamentul său într-o succesiune de pași, la fiecare pas metalul fiind supus unei anumite temperaturi. Pașii sunt numerotați cu valori naturale consecutive, începând de la 1. Un pas se numește reprezentativ dacă la niciunul dintre pașii anteriori nu este utilizată o temperatură strict mai mare decât la acest pas. Dacă există o secvență de pași consecutivi la care se utilizează aceeași temperatură, se consideră reprezentativ doar primul pas din secvență.
Fișierul bac.txt conține cel mult 10⁶ numere naturale din intervalul [0,10⁴], separate prin câte un spațiu, reprezentând temperaturile la care este supus metalul, în ordinea pașilor corespunzători. Se cere să se afișeze pe ecran, separați prin câte un spațiu, pașii reprezentativi pentru datele din fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține numerele 7 4 9 10 10 10 3 9 2 10 10 8 2 30
se afișează pe ecran 1 3 4 10 14
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3.a.
Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a unor elemente de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă determină, pe măsura citirii din fișier, valoarea ultimei temperaturi reprezentative (tr) și poziția acesteia (ptr), pe baza temperaturii curente (x) și a poziției acesteia (px), care se actualizează la fiecare pas. Poziția curentă px se afișează doar dacă se întâlnește o temperatură mai mare decât tr (x>tr), sau dacă temperatura curentă este egală cu tr (x=tr), dar cele două valori nu sunt pe poziții consecutive în șir (px>ptr+1); valoarea lui ptr se actualizează pentru fiecare x≥tr (ptr←px), iar valoarea lui tr se actualizează pentru fiecare x>tr (tr←x).
SUBIECTUL al III-lea, 3.b.
Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar, care utilizează eficient memoria.
O soluție posibilă determină, pe măsura citirii din fișier, valoarea ultimei temperaturi reprezentative (tr) și poziția acesteia (ptr), pe baza temperaturii curente (x) și a poziției acesteia (px), care se actualizează la fiecare pas. Poziția curentă px se afișează doar dacă se întâlnește o temperatură mai mare decât tr (x>tr), sau dacă temperatura curentă este egală cu tr (x=tr), dar cele două valori nu sunt pe poziții consecutive în șir (px>ptr+1); valoarea lui ptr se actualizează pentru fiecare x≥tr (ptr←px), iar valoarea lui tr se actualizează pentru fiecare x>tr (tr←x).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Numim secvență par-încadrată a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, subșir care începe și se termină cu aceeași valoare, pară. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir de cel puțin două și cel mult 10⁶ numere naturale din intervalul [0, 9]. Numerele sunt separate prin câte un spațiu, iar în șir există cel puțin doi termeni pari egali.
Se cere să se determine secvențele par-încadrate din acest șir care au lungime maximă și să se afișeze pe prima linie a ecranului lungimea maximă determinată, iar pe următoarea linie, pentru fiecare astfel de secvență, valoarea primului său termen. Numerele de pe a doua linie sunt afișate în ordine strict crescătoare, separate prin câte un spațiu.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul bac.txt conține numerele
5 1 3 2 4 3 3 2 8 9 7 3 4 6 6 0 8
atunci pe ecran se afișează valorile:
9
4 8
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
SUBIECTUL al III-lea, 3. a)
Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează doi vectori de apariții, p și u, în care pentru fiecare valoare pară i citită din fișier se actualizează pᵢ, prima poziție pe care este întâlnită valoarea i, respectiv uᵢ, ultima poziție pe care este întâlnită valoarea i. Lungimea cerută este cea mai mare valoare a expresiei uᵢ−pᵢ+1 pentru orice i∈{0,2,4,6,8}, iar numerele cerute corespund valorilor pare i pentru care se obține lungimea maximă menționată.
SUBIECTUL al III-lea, 3. b)
Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează doi vectori de apariții, p și u, în care pentru fiecare valoare pară i citită din fișier se actualizează pᵢ, prima poziție pe care este întâlnită valoarea i, respectiv uᵢ, ultima poziție pe care este întâlnită valoarea i. Lungimea cerută este cea mai mare valoare a expresiei uᵢ−pᵢ+1 pentru orice i∈{0,2,4,6,8}, iar numerele cerute corespund valorilor pare i pentru care se obține lungimea maximă menționată.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Se citește de la tastatură un număr natural, n (n∈[1,10⁹]), și se cere să se scrie în fișierul text bac.txt cel mai mare număr natural p cu proprietatea că numărul 45ᵖ este divizor al numărului obținut prin evaluarea produsului 1∙2∙3∙...∙n.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă n=14, fișierul conține numărul 2 (45²=2025 este divizor al lui 1∙2∙3∙..∙14=87178291200)
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
3. a) Pentru răspuns corect: 2p.
-coerență a descrierii algoritmului (*): 1p.
-justificare a elementelor de eficiență: 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă are în vedere că 45=3²∙5 și parcurge numerele naturale din intervalul [2,n], determinând pentru fiecare număr curent k numărul t de apariții ale lui 3, respectiv numărul c de apariții ale lui 5, în descompunerea în factori primi a lui k, și realizând pe parcurs suma tuturor valorilor t determinate (st), respectiv suma tuturor valorilor c determinate (sc).
Valoarea cerută este min([st/2],sc).
O altă soluție posibilă determină valorile st și sc astfel:
st=[n/3]+[n/3²]+[n/3³]+[n/3⁴]+ ...+0
sc=[n/5]+[n/5²]+[n/5³]+[n/5⁴]+ ...+0
Valoarea cerută este min([st/2],sc).
3. b) Pentru program corect: 8p.
-operații cu fișiere: declarare, pregătire în vederea scrierii, scriere în fișier: 1p.
-determinare a valorii cerute (*),(**): 5p.
-utilizare a unui algoritm eficient (***): 1p.
-declarare a variabilelor, citire a datelor, corectitudine globală a programului¹⁾: 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm cel mult liniar care utilizează eficient memoria.
O soluție posibilă are în vedere că 45=3²∙5 și parcurge numerele naturale din intervalul [2,n], determinând pentru fiecare număr curent k numărul t de apariții ale lui 3, respectiv numărul c de apariții ale lui 5, în descompunerea în factori primi a lui k, și realizând pe parcurs suma tuturor valorilor t determinate (st), respectiv suma tuturor valorilor c determinate (sc).
Valoarea cerută este min([st/2],sc).
O altă soluție posibilă determină valorile st și sc astfel:
st=[n/3]+[n/3²]+[n/3³]+[n/3⁴]+ ...+0
sc=[n/5]+[n/5²]+[n/5³]+[n/5⁴]+ ...+0
Valoarea cerută este min([st/2],sc).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Fișierul cheltuieli.in are cel mult 10⁶ linii, fiecare linie conținând câte trei numere naturale din intervalul [1,10²], reprezentând, în această ordine, date despre câte o achiziție: tipul produsului cumpărat, numărul de produse de acest tip cumpărate, respectiv prețul unui astfel de produs la acel moment. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran cea mai mare sumă cheltuită pentru toate produsele de același tip, precum și numărul de tipuri de produse pentru care s-a obținut această sumă.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul cheltuieli.in are conținutul alăturat, se afișează pe ecran: 26 2
(s-a cheltuit suma maximă 26 pentru produsele de tipul 1 și 4: 26=16·1+5·2=1·10+2·8)
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
3. a. Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează un tablou, s, în care s[i]=suma cheltuită în total pentru produsele de tipul i. Pe măsura citirii datelor din fișier, pentru fiecare triplet x, y, z citit se actualizează s[x] prin adunare la valoarea sa actuală a produsului y*z. La final se determină valoarea maximă memorată în tabloul s, precum și numărul de apariții ale acestei valori.
b. Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorilor cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un tablou, s, în care s[i]=suma cheltuită în total pentru produsele de tipul i. Pe măsura citirii datelor din fișier, pentru fiecare triplet x, y, z citit se actualizează s[x] prin adunare la valoarea sa actuală a produsului y*z. La final se determină valoarea maximă memorată în tabloul s, precum și numărul de apariții ale acestei valori.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
La proiectarea unui site web se utilizează elemente grafice realizate pe baza unor modele. Fiecare model este de formă pătrată și oricare două modele distincte au dimensiuni diferite ale laturilor. Toate elementele grafice realizate pe baza unui anumit model au aceeași formă și aceleași dimensiuni ca ale acestuia. În vederea asigurării elementelor grafice necesare, pentru fiecare model dintre cele utilizate se plătește o taxă unică de proiectare, de 10 lei, iar pentru fiecare element grafic realizat pe baza acelui model se plătește o sumă în lei, egală cu valoarea suprafeței acestuia (aria pătratului), calculată în centimetri pătrați.
Fișierul bac.in conține un șir de cel mult 10⁶ numere naturale din intervalul [1,10], separate prin câte un spațiu, reprezentând dimensiunile laturilor tuturor elementelor grafice utilizate, date în centimetri; fiecare termen al șirului corespunde unui element grafic distinct. Se cere să se afișeze pe ecran suma totală plătită pentru asigurarea elementelor grafice necesare. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 1 7 2 1 1 2 1 7 2
se afișează pe ecran valoarea 144
(10 lei pentru modelul de lățime 1 cm și câte 1·1 lei pentru fiecare dintre cele patru elemente grafice care îl au la bază, 10 lei pentru modelul de lățime 2 cm și câte 2·2 lei pentru fiecare dintre cele trei elemente grafice care îl au la bază, respectiv 10 lei pentru modelul de lățime 7 cm și câte 7·7 lei pentru fiecare dintre cele două elemente grafice care îl au la bază).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
a) Pentru răspuns corect - 2p.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă utilizează un vector de frecvență, a, inițial cu toate elementele nule, unde aₓ este egal cu numărul termenilor egali cu x din șirul aflat în fișier. Pe măsura citirii datelor din fișier, pentru fiecare valoare x citită, se actualizează aₓ. La final, se parcurge vectorul de frecvență și, pentru fiecare număr întreg x (x∈[1,10]) pentru care aₓ≠0, se adaugă la sumă valoarea expresiei 10+x²·aₓ.
b) Pentru program corect - 8p.
-operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
-determinare a valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor, corectitudine globală a programului¹⁾ - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
(**) Se acordă numai 3p. dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date de intrare.
(***) Se acordă punctajul numai pentru un algoritm liniar.
O soluție posibilă utilizează un vector de frecvență, a, inițial cu toate elementele nule, unde aₓ este egal cu numărul termenilor egali cu x din șirul aflat în fișier. Pe măsura citirii datelor din fișier, pentru fiecare valoare x citită, se actualizează aₓ. La final, se parcurge vectorul de frecvență și, pentru fiecare număr întreg x (x∈[1,10]) pentru care aₓ≠0, se adaugă la sumă valoarea expresiei 10+x²·aₓ.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
