Etichete: nicio etichetă

Acest articol conține o listă cu probleme propuse pentru examenul de bacalaureat la care se cer soluții eficiente din punct de vedere a memoriei utilizate și/sau a timpului de execuție (punctul III.3).
Problemele pot fi filtrate folosind butoanele din stânga!

Sesiune august-septembrie 2021

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^5\): 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).

Sesiune iunie-iulie 2021

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 \in [100,999] \)), iar pe a doua linie un şir de cel mult \(10^5\) numere naturale din intervalul \([0,10^9]\). 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 bac.txt conține numerele

210
3445 210 893210 1245 1210 3210 15210 67120 20210 12

pe ecran se afișează 3210 15210.

Subiecte antrenament, 2021, testul 12

Fișierul bac.txt conține un șir de cel mult \(10^5\) numere naturale din intervalul \([1,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran cea mai mare poziție pe care ar putea-o ocupa primul termen al șirului aflat în fișier în șirul format cu aceleași valori, ordonat descrescător. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul bac.txt conține numerele 15 7 15 17 6 4 21 seafișează pe ecran 4 (15 se află pe a treia și pe a patra poziție în șirul 21, 17, 15, 15, 7, 6, 4).

Subiecte antrenament, 2021, testul 11

Se consideră șirul 1, 3, 7, 13, 21, 31, 43… definit astfel: \(f_0=1\), iar \(f_n=f_{n-1} + 2 \cdot n\), dacă n≥1 (unde n este un număr natural). Se citesc de la tastatură două numere naturale din intervalul \([1,10^9]\), 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

Subiecte antrenament, 2021, testul 10

Fişierul bac.txt conține un șir de cel mult \(10^5\) numere naturale din intervalul \([1,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran cea mai mică poziție pe care ar putea-o ocupa primul termen al șirului aflat în fișier în șirul format cu aceleași valori, ordonat crescător. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul conține 15 7 15 17 6 4

se afișează pe ecran 4 (15 se află pe a patra și pe a cincea poziție în șirul 4, 6, 7, 15, 15, 17).

Subiecte antrenament, 2021, testul 9

Fișierul numere.txt conține cel mult \(10^5\) numere naturale din intervalul \([1,10^9]\), câte unul pe fiecare linie.

Se cere să se afișeze pe ecran cel mai mare număr care se poate forma cu toate cifrele care apar în numerele din fișier, ca în exemplu.

Proiectați un algoritm eficient din punctul de vedere al timpului de executare.

Exemplu: dacă fișierul conține:

263
39628
79
887308

se afișează

9988887766333220

Subiecte antrenament, 2021, testul 8

Fișierul bac.txt conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\).
Se cere să se determine și să se afișeze pe ecran, separate printr-un spațiu, ultimele două numere impare (nu neapărat distincte) din șirul aflat în fișier, sau mesajul nu exista, dacă nu există două astfel de numere.Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul conține valorile 122 1635 628 1413 1647 900 3001 4252 se afișează pe ecran 1647 3001

Subiecte antrenament, 2021, testul 7

Fișierul bac.txt conține cel mult \(10^6\) cifre, separate prin câte un spațiu.

Se cere să se afișeze pe ecran, separate prin câte un spațiu, toate cifrele pare care apar în fișier sau mesajul nu exista, dacă nu există astfel de cifre. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.

Exemplu: dacă fișierul conține cifrele 3 3 0 8 2 1 2 1 3 7 1 5 2 7 1 0 3 2 3 pe ecran se afișează, de exemplu în ordine crescătoare, cifrele 0 0 2 2 2 2 8

Subiecte antrenament, 2021, testul 6

Fișierul bac.in conține un șir de cel puțin patru și cel mult \(10^5\) numere întregi nenule din intervalul \([-10^9,10^9]\), dintre care trei sunt negative, iar restul pozitive. Numerele sunt separate prin câte un spațiu. O secvență este formată din termeni aflați pe poziții consecutive în șir, iar lungimea secvenței este egală cu numărul de termeni ai acesteia.

Se cere să se afișeze pe ecran lungimea unei secvențe din șirul aflat în fișier care conține o singură valoare negativă și un număr maxim de valori pozitive. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul conține numerele 15 21 -61 9 870 -23 11 5 8 -81 5 14 pe ecran se afișează 6 (corespunzător secvențelor 9 870 -23 11 5 8 sau 11 5 8 -81 5 14).

Subiecte antrenament, 2021, testul 5

Fişierul bac.txt conține numere naturale din intervalul \([2,10^6]\): pe prima linie \(n\), iar pe a doua linie un șir de \(n\) numere, separate prin câte un spațiu. Se cere să se afișeze pe ecran, pentru fiecare număr natural \(i\) (\(i ∊ [1,n]\)), cea mai mare dintre primele \(i\) valori ale șirului aflat în fișier. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.

Exemplu: dacă fișierul conține

12
4 6 3 7 8 1 6 2 7 9 10 8

se afișează pe ecran

4 6 6 7 8 8 8 8 8 9 10 10

Subiecte antrenament, 2021, testul 3

Două numere naturale sunt numite z-prietene dacă au aceeași cifră a zecilor.

Fișierul bac.in conține un șir de cel mult \(10^6\) numere naturale din intervalul \([10,10^9]\), separate prin câte un spațiu.

Se cere să se afișeze pe ecran pozițiile din șir pe care se află termeni precedați de un număr maxim de valori z-prietene cu ei. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.

Exemplu: dacă fișierul conține numerele 726 358 98 157 20 49 128 879 659 271 pe ecran se afișează numerele 7 9 (termenii 128, respectiv 659 respectă proprietatea cerută).

Subiecte antrenament, 2021, testul 2

Fișierul bac.in conține un șir de cel mult \(10^6\) numere întregi din intervalul \([-10^9,10^9]\), separate prin câte un spațiu. Cel puțin un număr din șir este pozitiv.

Se cere să se afișeze pe ecran lungimea maximă a unei secvențe a șirului care fie începe, fie se încheie cu un număr pozitiv. O secvență este formată din termeni aflați pe poziții consecutive în șir, iar lungimea secvenței este egală cu numărul de termeni ai acesteia. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul conține numerele -15 -7 4 -7 21-5 -200 -26 52 -24 -7 -9 -20 pe ecran se afișează 11 (corespunzător secvenței 4 -7 21 -5 -200 -26 52 -24 -7 -9 -20).

Subiecte antrenament, 2021, testul 1

Fișierul bac.in conține cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran, în ordine descrescătoare, cele mai mari două numere de două cifre distincte care NU se află în fișier. Numerele afișate sunt separate printr-un spațiu, iar dacă nu există două astfel de numere, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.

Exemplu: dacă fișierul bac.in conține numerele 12 235 123 67 98 6 96 94 123 67 98 100 se afișează pe ecran, în această ordine,numerele 97 95.

Subect simulare, 2021

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^6\) 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ă).

Model subiect, 2021

Fișierul cheltuieli.in are cel mult \(10^6\) linii, fiecare linie conținând câte trei numere naturale din intervalul \([1,10^2]\), 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 următor

4  1 10
1 16  1
4  2  8
2  1  5
1  5  2

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)

Sesiunea august-septembrie 2020

Fișierul bac.txt conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran, separate printr-un spațiu, două numere naturale a și b (a<b), astfel încât oricare termen al șirului care are exact două cifre să aparțină intervalului (a,b), iar valoarea expresiei b-a să fie minimă. Dacă șirul nu are niciun termen de două cifre, 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 valorile 7 2 40 5 11 15 10 122 18 350 se afișează pe ecran numerele 9 41.

Sesiunea iunie-iulie 2020

Un șir finit se numește palindromic dacă parcurgându-l termen cu termen, de la stânga la dreapta sau de la dreapta la stânga se obține același șir de valori.
Exemplu:șirul 12 13 16 13 12 este palindromic.

Fișierul bac.in conține un șir de cel mult \(10^6\) numere naturale din intervalul \([1,10^3]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, dacă numerele din șir pot fi rearanjate, astfel încât să formeze un șir palindromic, 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 100 30 100 30 500 30 30 se afișează pe ecran DA

Sesiunea specială 2020

Se numește vârf într-un șir de numere naturale un termen al șirului care este strict mai mare decât fiecare dintre cei doi termeni vecini cu el, aflați în șir pe poziția din stânga, respectiv din dreapta sa.

Fișierul bac.in conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran vârful din șirul aflat în fișier pentru care valoarea absolută a diferenței dintre cei doi vecini ai săi este minimă. Dacă există mai multe astfel de numere, se afișează cel mai mare dintre ele, iar dacă nu există niciun vârf, 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 șirul 2 7 10 5 6 2 1 3 20 17 9 11 7 3 10 6 2 se afișează pe ecran 11

Subiecte antrenament, 2020, testul 1

Se consideră șirul 1, 1, 2, 5, 13, 34, 89, 233, 610 …. definit astfel: \(f_1=f_2=1\), \(f_n=3 \cdot f_{n-1}-f_{n-2}\)(unde \(n\) este un număr natural \(n≥3\)).

Se citesc de la tastatură două numere naturale \(x\) și \(y\) (\(x≤y≤10^9\)), valorile a doi termeni aflați pe poziții consecutive în şirul dat, şi se cere să se scrie în fişierul text 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 \(y\). Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.

Exemplu: dacă se citesc numerele 89 233 fişierul bac.txt va conţine numerele 233 89 34 13 5 2 1 1

Subiecte antrenament, 2020, testul 2

Fişierul bac.in conţine un şir de numere naturale distincte, din intervalul [\(1,10^9]\). Numerele din şir sunt separate prin câte un spaţiu şi cel puţin trei dintre ele au penultima cifră 2 și ultima cifră 0. Se cere să se afișeze pe ecran cele mai mari trei numere din şir cu proprietatea că au penultima cifră 2 și ultima cifră 0. Numerele determinate sunt afişate în ordine crescătoare, separate prin câte un spaţiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.

Exemplu: dacă fişierul conţine numerele 9731 50 112 20 8 16 8520 3 2520 1520 pe ecran se vor afişa, în această ordine, numerele: 1520 2520 8520

Subiecte antrenament, 2020, testul 3

Fişierul bac.in conţine un şir de cel mult \(10^6\) numere întregi din intervalul \([-10^9,10^9]\), separate prin câte un spaţiu. Cel puţin un număr din șir este negativ.

Se cere să se afişeze pe ecran lungimea maximă a unei secvenţe a şirului care fie începe, fie se încheie cu un număr negativ. O secvenţă este formată din termeni aflaţi pe poziţii consecutive în şir, iar lungimea secvenței este egală cu numărul de termeni ai acesteia. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.

Exemplu: dacă fişierul conţine numerele 12 25 -6 7 80 -75 101 -6 52 -124 87 99 210 pe ecran se afişează 11 (corespunzător secvenţei -6 7 80 -75 101 -6 52 -124 87 99 210).

Subiecte antrenament, 2020, testul 4

Fişierul bac.txt conţine, în ordine descrescătoare, cel puţin două şi cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spaţiu. Se cere să se afişeze pe ecran, în ordine strict descrescătoare, separate prin câte un spaţiu, numai numerele care apar în fişier de exact două ori. Dacă nu există niciun astfel de număr, 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 100 50 50 50 49 49 36 16 16 12 10 10 9 7 7 pe ecran se afişează, în această ordine, numerele 49 16 10 7

Subiecte antrenament, 2020, testul 5

Fișierul bac.txt conține un șir de cel mult \(10^6\) numere întregi din intervalul \([-10^3,10^3]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran suma maximă obținută adunând numere de pe poziții consecutive în șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul bac.txt conține valorile 4 -6 7 2 -1 4 -10 -3 9 2 -2 se afișează pe ecran numărul 12

Subiecte antrenament, 2020, testul 6

Se citesc de la tastatură două numere naturale din intervalul [1,81], p1 și p2, și se cere scrierea în fișierul bac.out a tuturor numerelor naturale cu exact 7 cifre, pentru care produsul primelor două cifre este egal cu p1, cele trei cifre din mijloc sunt egale între ele, iar produsul ultimelor două cifre este egal cu p2. Numerele apar în fișier în ordine strict descrescătoare, fiecare pe câte o linie. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă p1=12, iar p2=8, atunci 2633324 și 3400018 sunt două dintre cele 160 de numere cuproprietatea cerută (2∙6=3∙4=12 și 2∙4=1∙8=8).

Subiecte antrenament, 2020, testul 7

Fișierul bac.txt conține un șir de cel mult \(10^6\) numere întregi din intervalul \([-10^3,10^3]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran suma minimă obținută adunând numere de pe poziții consecutive în șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul bac.txt conține valorile -4 6 -7 -2 1 -4 10 3 -9 -2 2 se afișează pe ecran numărul -12

Subiecte antrenament, 2020, testul 8

Fișierul bac.in conține un șir de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spațiu. Se cere să se afișeze pe ecran pozițiile din șir pe care se află termeni precedați de un număr maxim de valori care au cifra unităților egală cu cifra unităților lor. Numerele afișate sunt 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.in conține numerele 112 12 5 25 88 15 2 19 32 179 35 621 pe ecran se afișează numerele de mai jos 9 11 (termenii 32, respectiv 35 respectă proprietatea cerută).

Subiecte antrenament, 2020, testul 9

Numim k-secvență într-un șir de numere naturale, o succesiune de termeni aflați pe poziții consecutive în șir, cu proprietatea că sunt divizibili cu numărul natural nenul k. Lungimea secvenței este egală cu numărul de termeni ai săi.

Fișierul bac.txt conține numere naturale din intervalul \([0,10^9]\): pe prima linie un număr nenul k, iar pe a doua linie un șir de cel mult \(10^6\) numere, separate prin câte un spațiu. Cel puțin un termen din șir este divizibil cu k. Se cere să se afișeze pe ecran două valori, separate printr-un spațiu, reprezentând lungimea maximă a unei k-secvențe din șirul aflat în fișier, respectiv numărul de astfel de secvențe. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul conține

5
2 10 5 20 21 0 10 60 15 3 9 20 20 5 45

se afișează 4 2

Subiecte antrenament, 2020, testul 10

Un șir format din cel puțin trei termeni formează o progresie aritmetică de rație r dacă diferența dintre oricare termen al acestuia și cel aflat pe poziția consecutivă în șir este egală cu r.

Fișierul text bac.txt conține un șir de cel puțin trei și cel mult \(10^6\) numere întregi din intervalul \([-10^8,10^8]\). Numerele sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran rația unei secvențe din șir cu număr maxim de termeni, secvență care formează o progresie aritmetică. Dacă există mai multe astfel de secvențe de lungime maximă se afișează rația cea mai mare, iar dacă nu există nicio astfel de secvență, 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 4 9 14 19 18 16 8 5 3 1 -1 -3 -5 -7 pe ecran se afișează valoarea -2 (corespunzătoare secvenței 5 3 1 -1 -3 -5 -7).

Subiecte antrenament, 2020, testul 11

Fişierul bac.txt conţine un şir crescător de cel mult \(10^6\) numere naturale din intervalul \([0,10^9]\), separate prin câte un spaţiu. Se cere să se afişeze pe ecran fiecare număr distinct din şir, urmat de numărul de apariţii ale acestuia în şir. Numerele afișate sunt separate prin câte un spațiu. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fişierul bac.txt conține numerele 0 0 0 5 5 5 5 7 7 11 20 20 se afișează 0 3 5 4 7 2 11 1 20 2