Candale Silviu (silviu) 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!
Sesiunea iunie-iulie 2024
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 106 numere naturale din intervalul [10,104], 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.
Sesiunea specială, mai 2024
Fișierul numere.in conține un șir de cel mult 106 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.
Simulare martie 2024
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 106 numere naturale din intervalul [1,103], 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).
Sesiunea august 2023
Fișierul date.in conține pe prima linie două numere naturale din intervalul [1,106], m și n, iar pe următoarele două linii numere naturale din intervalul [0,102): 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
8 9 1 0 4 1 5 3 5 5 1 1 1 7 5 3 5 3 0
se afișează pe ecran numărul 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).
Sesiunea iunie-iulie 2023
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 106 numere naturale din intervalul [10,104), 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).
Sesiunea specială, mai 2023
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 106 numere întregi din intervalul [-109,109], 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 bac.txt 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.
Simulare, martie 2023
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 106 numere naturale din intervalul [0,104], 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
Sesiunea august 2022
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^6\) numere naturale din intervalul \([0, 10^9]\). 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.
Sesiunea specială, mai 2022
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^6\) numere naturale din intervalul \([1,10^6]\), 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.
Sesiunea iunie-iulie 2022
Fișierul bac.txt conține numere naturale din intervalul\( [1,10^9]\), astfel: pe prima linie două numere, x și y (x<y), iar pe a doua linie un șir de cel mult \(10^6\) 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 conține numerele
2 9 1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 21 21
atunci pe ecran se afișează valoarea 6.
Simulare 2022
Se citește de la tastatură un număr natural, \(n\) ( \( n \in [1,10^9]\)), ș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^p\) 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^2=2025\) este divizor al lui 1∙2∙3∙..∙14=87178291200).
Sesiunea 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).
Sesiunea 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