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 cu un pachet în plus față de dublul numărului de pachete livrate în luna precedentă, obținând astfel șirul numărului de pachete livrate: 0 3 7 15 31 63 127 255 ....
Se citește de la tastatură un număr natural din intervalul [0,10⁹], reprezentând numărul de pachete livrate de firma de curierat în ultima 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 citește valoarea 127, fișierul conține numerele: 127 63 31 15 7 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ă două valori corespunzătoare ultimelor două numere din șir (x, y în această ordine), care se actualizează la fiecare pas; inițial se afișează valoarea dată, apoi la fiecare pas se determină valoarea curentă (x) pe baza ultimului număr afișat (x=[(y-1)/2]), procedeu care se încheie după ce s-a afișat valoarea 3, apoi, după caz, se afișează 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ă două valori corespunzătoare ultimelor două numere din șir (x, y în această ordine), care se actualizează la fiecare pas; inițial se afișează valoarea dată, apoi la fiecare pas se determină valoarea curentă (x) pe baza ultimului număr afișat (x=[(y-1)/2]), procedeu care se încheie după ce s-a afișat valoarea 3, apoi, după caz, se afișează 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 numărul de rezultate motivante obținute la concursurile de șah.
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 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).
6 1
8 2
7 1
5 2
3 1
4 1
5 1
1 2
4 2
1 1
2 1
1 1
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.Arată baremul
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, numărul cerut (ns) și memorează poziția în clasamentul ultimului concurs de șah (ups, 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 se actualizează ups (dacă c=1).
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 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, numărul cerut (ns) și memorează poziția în clasamentul ultimului concurs de șah (ups, 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 se actualizează ups (dacă c=1).
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ă.
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 numărul de muzee convenabile. 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ă numărul 3.
(pot fi vizitate trei muzee, respectiv primul, al doilea și al patrulea, î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
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 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).
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 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, 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 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).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
3. 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 una sau mai multe 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, stocul total calculat pentru ea. Valorile se afișează pe câte o linie a ecranului, 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
65
71
90
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 primele două valori din fișier (minZ și minP), apoi, pe măsura citirii stocurilor zilnice, dacă stocul curent citit (x) corespunde unei zile validate (x≥minZ), se actualizează stocul total (stocCrt=stocCrt+x) al perioadei curente.
Dacă ziua nu este validată (x<minZ) sau dacă s-a încheiat citirea, se afișează stocul total determinat, dacă acesta corespunde unei perioade validate (stocCrt≥minP), apoi se reinițializează această valoare 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, dacă stocul curent citit (x) corespunde unei zile validate (x≥minZ), se actualizează stocul total (stocCrt=stocCrt+x) al perioadei curente.
Dacă ziua nu este validată (x<minZ) sau dacă s-a încheiat citirea, se afișează stocul total determinat, dacă acesta corespunde unei perioade validate (stocCrt≥minP), apoi se reinițializează această valoare 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 număr din șir care conține cea mai mare cifră ce apare în scrierea numerelor din fișier. Numărul determinat se afișează pe ecran. 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 2 12 34 5 38 30 87 70 11 8 82 25
se afișează pe ecran valoarea 38.
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, 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 număr dintre cele citite care conțin această cifră (p). 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 și p (cifMax←cm, p←x). După parcurgerea tuturor numerelor, se afișează p.
b. Pentru program corect - 8p.
- operații cu fișiere: declarare, pregătire în vederea citirii, citire din fișier - 1p.
- determinare a valorii, 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 număr dintre cele citite care conțin această cifră (p). 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 și p (cifMax←cm, p←x). După parcurgerea tuturor numerelor, se afișează p.
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 lungimea maximă a unei scări pe acest traseu. Dacă în cadrul traseului 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ă 3.
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) al scării curente; 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. Se afișează lgMax, iar 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 valorii cerute (*),(**) - 5p.
-utilizare a unui algoritm eficient (***) - 1p.
-declarare a variabilelor, afișare a datelor și tratarea 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 (de complexitate O(n)), 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) al scării curente; 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. Se afișează lgMax, iar mesajul se afișează dacă lgMax<2.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Șirul 2, 3, 5, 9, 17, 33, 65, 129 .... este definit astfel: f₁=2, f₂=3, fₙ=3·fₙ₋₁−2·fₙ₋₂ (unde n este un număr natural n≥3).
Se citesc de la tastatură două numere naturale x și y (x<y≤10⁹), valorile a doi termeni aflați pe poziții consecutive în șirul dat, și se cere să se scrie în fișierul bac.txt, în ordine strict descrescătoare, separați prin câte un spațiu, toți termenii șirului care sunt mai mici sau egali cu y. 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 33 65, fișierul conține numerele 65 33 17 9 5 3 2
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ță - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă memorează ultimii doi termeni afișați pe poziții consecutive, în ordine descrescătoare, y și x (y>x) și determină termenul curent (crt) pe baza celor doi termeni afișați anterior, cu formula crt=[(3·x-y)/2]; inițial se afișează, în ordine descrescătoare, cei doi termeni citiți, apoi, la fiecare pas, se determină și se afișează termenul curent și se actualizează cei doi termeni y și x; algoritmul se încheie după afișarea valorii 2.
O altă soluție posibilă memorează ultimul termen afișat (crt) și determină termenul curent pe baza acestuia, cu formula crt=[(crt+1)/2]; inițial se afișează, în ordine descrescătoare, cei doi termeni citiți, apoi, la fiecare pas, se determină și se afișează termenul curent, care se actualizează; algoritmul se încheie după afișarea valorii 2.
SUBIECTUL al III-lea
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, 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 doi termeni afișați pe poziții consecutive, în ordine descrescătoare, y și x (y>x) și determină termenul curent (crt) pe baza celor doi termeni afișați anterior, cu formula crt=[(3·x-y)/2]; inițial se afișează, în ordine descrescătoare, cei doi termeni citiți, apoi, la fiecare pas, se determină și se afișează termenul curent și se actualizează cei doi termeni y și x; algoritmul se încheie după afișarea valorii 2.
O altă soluție posibilă memorează ultimul termen afișat (crt) și determină termenul curent pe baza acestuia, cu formula crt=[(crt+1)/2]; inițial se afișează, în ordine descrescătoare, cei doi termeni citiți, apoi, la fiecare pas, se determină și se afișează termenul curent, care se actualizează; algoritmul se încheie după afișarea valorii 2.
¹) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
3. Un număr natural x este numit prefix al unui număr natural y dacă este egal cu y sau 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ă este egal cu y sau 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, și este sufix pentru 3415 sau 5115.
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 164 234 534 111 312 908 807 345 342 716 834 102 310
se afișează pe ecran: 4 (pentru valorile 10, 11, 16, 34).
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ă 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, sufixul (x%100), respectiv prefixul ([x/10]) ș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 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.
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, sufixul (x%100), respectiv prefixul ([x/10]) ș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 distincte, iar pe a treia linie un șir B, de n numere distincte. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul 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 5 (pentru perechile (1,1), (2,8), (4,2), (5,5), (6,7)).
7 8
1 0 4 2 5 3 8
1 2 6 9 5 7 3 0
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.
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ă un vector de frecvență, a, unde aᵢ este 1 dacă valoarea i apare într-un singur șir, este 2 dacă valoarea i apare în ambele șiruri sau este 0 altfel; vectorul este completat pe măsura citirii datelor din fișier, iar numărul afișat se obține ulterior, prin numărarea pozițiilor i pentru care aᵢ=2.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
3. Fișierul bac.txt conține numere naturale din intervalul [1,10⁹], astfel: pe prima linie numărul x, 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 [1,x]. 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ă 7
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
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.
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≤x), incrementând numărul nr pentru fiecare valoare distinctă din șir (crt≠ant) din intervalul cerut (crt≤x); 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≤x), incrementând numărul nr pentru fiecare valoare distinctă din șir (crt≠ant) din intervalul cerut (crt≤x); 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 determine și să se afișeze pe ecran lungimea maximă a unei secvențe paritare în ș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
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ă valoarea 5
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 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ă.
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.
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ă.
1) 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 ultimul termen al șirului care îl are drept sufix pe numărul x. Dacă nu există un astfel de termen, 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ă 20210.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Pagina din subiectul oficial.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ă citește prima valoare din fișier (x), apoi, pe măsura citirii celorlalte valori, memorează valoarea curentă (crt), precum și ultimul număr cu proprietatea cerută (u, inițializat cu -1); u se actualizează doar dacă crt mod 1000=x (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 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ă citește prima valoare din fișier (x), apoi, pe măsura citirii celorlalte valori, memorează valoarea curentă (crt), precum și ultimul număr cu proprietatea cerută (u, inițializat cu -1); u se actualizează doar dacă crt mod 1000=x (u=crt).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
Numim pereche asemenea (x,y) două numere naturale, x și y, cu proprietatea că ultima cifră a lui x este egală cu ultima cifră a lui y.
Fișierul numere.in conține numere naturale din intervalul [1,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
7 5
112 7 4 112 5013 824 10012
405 1024 321 52 6542
se afișează pe ecran numărul 8
deoarece sunt 8 perechi asemenea: (112,52), (112,6542), (4,1024), (112,52), (112,6542), (824,1024), (10012,52), (10012,6542).
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.
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.
O soluție posibilă utilizează un vector de frecvență v în care vᵢ reprezintă numărul de valori din șirul A care au ultima cifră egală cu i (i∈[0,9]). 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ă numărul i=y%10, apoi se adună la nr valoarea 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 simultană a celor doi vectori, adunând, pentru fiecare i∈[0,9], produsele vbᵢ·vaᵢ.
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 13ᵖ 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 (13²=169 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ă.
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ță - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
O soluție posibilă 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
SUBIECTUL al III-lea, 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ă 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.
3. Fișierul bac.txt conține numere naturale din intervalul [1,10⁹]: pe prima linie un număr, x, 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 sunt mai mari sau egale cu x. 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ă 4.
Conținutul fișierului:
5
1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 15 21 21
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.
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, incrementând numărul nr pentru fiecare valoare pară distinctă din șir (crt≠ant) din intervalul cerut (crt≥x); 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, incrementând numărul nr pentru fiecare valoare pară distinctă din șir (crt≠ant) din intervalul cerut (crt≥x); valoarea ant se actualizează la fiecare pas.
¹⁾ 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 identificatorul colecționarului care deține ultima mașină, din șirul celor expuse, fabricată în anul x. Dacă nu există o astfel de mașină, 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 121900 201925 31925 151925 61950 201925 121880
atunci pe ecran se afișează 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ță, 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 citit (crt), precum și ultimul identificator cu proprietatea cerută (u, inițializat cu -1); u se actualizează doar dacă crt mod 10000=x (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 citit (crt), precum și ultimul identificator cu proprietatea cerută (u, inițializat cu -1); u se actualizează doar dacă crt mod 10000=x (u=[crt/10000]).
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
3. 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ă cea mai importantă piatră a fiecărei bijuterii din set este de același tip.
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 18 seturi potrivite se pot forma din cerceii cu eticheta 258 și fiecare dintre pandantivele cu etichetele 259, respectiv 27, pentru toate aceste bijuterii piatra de tipul 2 fiind cea mai importantă).
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∈[1,9]) este 1 dacă există cel puțin o bijuterie (cercei) cu codul x pentru care i=[x/100] (dacă x∈[111,999]) sau i=x/10 (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ă prima cifră a sa, i, iar rezultatul este DA, în cazul în care există cel puțin o valoare p pentru care acᵢ este nenul, 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∈[1,9]) este 1 dacă există cel puțin o bijuterie (cercei) cu codul x pentru care i=[x/100] (dacă x∈[111,999]) sau i=x/10 (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ă prima cifră a sa, i, iar rezultatul este DA, în cazul în care există cel puțin o valoare p pentru care acᵢ este nenul, sau este NU, în caz contrar.
1) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
La un concurs se acordă premiile I și al II-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 și al II-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 două numere naturale din intervalul [1,20], n1 și n2, reprezentând numărul concurenților care primesc premiile I, respectiv al II-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 două premii, iar dacă nu există două 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
500 100 25 100 200 100 20 10 200 100 75 52 15 52 20 20 10 30 20 15 100
se afișează pe ecran, în această ordine, numerele 100 52.
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 și y (x>y, 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. Algoritmul se încheie dacă y≠0 sau dacă s-a încheiat parcurgerea vectorului de apariții. Dacă după parcurgerea vectorului de apariții y=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 și y (x>y, 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. Algoritmul se încheie dacă y≠0 sau dacă s-a încheiat parcurgerea vectorului de apariții. Dacă după parcurgerea vectorului de apariții y=0, atunci se afișează mesajul indicat.
¹) 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 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 2 27 8 2 27 2 2 14 14 8 27 se afișează pe ecran DA
(termenul par 2 apare de 4 ori, 4 fiind tot număr par, termenii pari 8 și 14 apar de câte 2 ori, 2 fiind tot număr par, iar termenul impar 27 apare de 3 ori, 3 fiind tot număr impar).
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.
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 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.
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), (7,9) sunt perechi p-ordonate, dar (7,8) nu este pereche p-ordonată.
Un șir, format din 2·n numere naturale, se numește ip-ordonat dacă primii n termeni sunt pari sau dacă toate perechile de forma (x,y) sunt p-ordonate, pentru orice x impar, 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 ip-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 43 14 4 5
5
22 36 20 8 14 44 43 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 impar (i1), dintre primele n numere din șir, precum și cel mai mare număr par (p2) dintre ultimele n numere din șir. Inițial, i1=1000001, p2=-1.
Șirul are proprietatea cerută dacă 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 impar (i1), dintre primele n numere din șir, precum și cel mai mare număr par (p2) dintre ultimele n numere din șir. Inițial, i1=1000001, p2=-1.
Șirul are proprietatea cerută dacă i1>p2
1) 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.
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 5 6 10 11 14
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 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) pe baza temperaturii curente (x). Poziția curentă (px), care se actualizează la fiecare pas, se afișează doar dacă se întâlnește o temperatură mai mare sau egală cu tr (x≥tr), când se actualizează, după caz, tr (tr←x).
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) pe baza temperaturii curente (x). Poziția curentă (px), care se actualizează la fiecare pas, se afișează doar dacă se întâlnește o temperatură mai mare sau egală cu tr (x≥tr), când se actualizează, după caz, 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 ecran această lungime. 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ă valoarea:
9
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ă 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}.
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.
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}.
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 9ᵖ 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 (9²=81 este divizor al lui 1·2·3·..·14=87178291200).
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
Arată baremul
Reguli generale:
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ă 9=3² ș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, în descompunerea în factori primi a lui k, și realizând pe parcurs suma tuturor valorilor t determinate (st). Valoarea cerută este [st/2].
O altă soluție posibilă determină valorile st astfel:
st=[n/3]+[n/3²]+[n/3³]+[n/3⁴]+ ...+0
Valoarea cerută este [st/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 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ă 9=3² ș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, în descompunerea în factori primi a lui k, și realizând pe parcurs suma tuturor valorilor t determinate (st). Valoarea cerută este [st/2].
O altă soluție posibilă determină valorile st astfel:
st=[n/3]+[n/3²]+[n/3³]+[n/3⁴]+ ...+0
Valoarea cerută este [st/2].
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. 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
(s-a cheltuit suma maximă 26 pentru produsele de tipul 1 și 4: 26=16·1+5·2=1·10+2·8).
4 1 10
1 16 1
4 2 8
2 1 5
1 5 2
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.
-coerență a descrierii algoritmului (*) - 1p.
-justificare a elementelor de eficiență - 1p.
(*) Se acordă punctajul chiar dacă algoritmul ales nu este eficient.
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.
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.
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.
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 30
(10 lei pentru modelul de latură 1 cm, 10 lei pentru modelul de latură 2 cm, respectiv 10 lei pentru modelul de latură 7 cm).
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.
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.
O soluție posibilă utilizează un vector caracteristic, a, inițial cu toate elementele nule, unde aₓ este egal cu 1 dacă există cel puțin un termen egal cu x în ș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 caracteristic și, pentru fiecare număr întreg x (x∈[1,10]) pentru care aₓ=1, se adaugă la sumă valoarea 10.
¹) Corectitudinea globală vizează structura, sintaxa, alte aspecte neprecizate în barem.
