#include <bits/stdc++.
h>
using namespace std;
int main() {
/*int a,b,c
cin >> a >> b >> c;
a *= 3; b += a; c = a + b;
cout << a << ' ' << b << ' ' << c;
/// O(6*n^0) = O(1)
/// 6 instructiuni */
/*
/// O(n)
int n; // n < 1000
int v[1000];
cin >> n;
for (int i=0;i<n;i++) {
cin >> v[i];
for (int i=0;i<n;i++) {
v[i] = v[i] + 1;
for (int i=0;i<n;i++) {
cout << v[i];
v[0]=1;
/// O(3n + 1) = O(n)
*/
/// O(n^2)
/* int A[100][100][100], n,m;
cin >> n >> m;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
for (int k=0;k<n;k++) {
cin >> A[i][j][k];
} /// n = 4 => op=4*4=16
for (int i=0;i<n;i++) {
A[i][i] = 0;
} /// n = 4 => op=4
/// O(N^2 + N) = O(N^2)
/// O(N*M) */
/// liniar
/*
int n,m;
int v[100], u[1000];
cin >> n >> m;
for (int i=0;i<n;i++) {
cin >> v[i];
for (int i=0;i<m;i++) {
cin >> u[i];
/// O(N + M) != O(N) != O(M)
*/
/*int n; cin >> n;
int d;
for (d=2; d<=n; d++) {
if (n%d==0) {
cout << ' ' << d << '\n';
}*/
/*int A[100][100];
int n;
cin >> n;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (i==j)
cout << A[i][j] << '\n';
for (int i=0;i<n;i++) {
cout << A[i][i] << ' ';
}*/
/*int a,b,c,d,f;
a=b=c=d=f=2;
if (a==2) {
int i=0;
// O(1) */
/*
int n; cin >> n;
int v[n];
/// timp = O(1); memorie = O(n);
*/
/*
int n,m; cin >> n >> m;
int A[n][m];
/// timp = O(1); memorie = O(n*m);
*/
/*
int n,m,k; cin >> n >> m >> k;
int A[n][m][m];
/// timp = O(1); memorie = O(n*m^2);
// n * (n-1) = O(n^2-n) = O(n^2) */
int n;
cin >> n;
int x;
cin >> x;
int max=x;
for (int i=1;i<n;i++)
if (x>max)
max=x;
cout << max;
/// timp = O(n); memorie = O(1);
/*int n;
cin >> n;
//int max=-1, min=10001;
int x;
cin >> x;
max=x, min=x;
for (int i=1;i<n;i++) {
cin >> x;
if (x > max) max=x;
if (x < min) min=x;
cout << min+max;
/// timp = O(n); memorie = O(1);*/
return 0;
}
I.
Fişierul [Link] conține, în ordine crescătoare, cel puțin două şi cel mult 10000 de
numere naturale. Numerele sunt separate prin câte un spaŃiu şi au cel mult 9 cifre fiecare.
Cel puțin un număr din fişier este par.
a) Scrieți un program C/C++ care citeşte toate numerele din fişier şi, printr-un algoritm
eficient din punct de vedere al timpului de executare şi al memoriei utilizate, determină şi
afişează pe ecran, în ordine strict crescătoare, separate prin câte un spațiu, toate
numerele pare care apar în fişier. Fiecare număr se va afişa o singură dată.
Exemplu: dacă fişierul are conținutul de mai jos
1 1 2 2 2 7 10 10 10 10 24
pe ecran se afişează, în această ordine, numerele 2 10 24.
b) Descrieți în limbaj natural (3-4 rânduri) algoritmul utilizat la punctul a) şi justificați
eficiența acestuia.
!!! Doar punctul b) !!!
timp: O(n)
Memorie O(1)
II.
Se citesc de la tastatură două numere naturale s1 şi s2 (0<s1≤18, 0≤s2≤18) şi se cere
scrierea în fişierul [Link], fiecare pe câte o linie, în ordine strict crescătoare, a tuturor
numerelor naturale cu exact 5 cifre, pentru care suma primelor două cifre este egală cu
s1, iar suma ultimelor două cifre este egală cu s2. Pentru determinarea numerelor
indicate se utilizează un algoritm eficient din punct de vedere al timpului de executare.
Exemplu: dacă s1=8, iar s2=7, atunci 35725 este unul dintre numerele care respectă
proprietatea cerută (3+5=8 şi 2+5=7).
a) Descrieți în limbaj natural algoritmul utilizat, justificând eficiența acestuia.
Timp: O( 1)
Memorie: O(1)
III.
Un număr natural cu cel puţin două cifre se numeşte x-ordonat dacă toate cifrele sale
sunt în ordine crescătoare şi valoarea absolută a diferenţei dintre oricare două cifre aflate
pe poziţii consecutive este egală cu x.
Exemple: numărul 2468 este 2-ordonat, numărul 147 este 3-ordonat; numerele 179 sau
131 nu sunt de tipul menţionat.
Se citeşte de la tastatură un număr natural x (1≤x≤8) şi se cere scrierea în fişierul
[Link] a tuturor numerelor naturale distincte x-ordonate. Fiecare număr este scris pe
câte o linie a fişierului.
Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de
vedere al timpului de executare.
a) Descrieţi în limbaj natural algoritmul utilizat, justificând eficienţa acestuia.
Timp: O( n) liniar
Memorie: O( 1) lucram doar pe variabile
IV.
Fişierul [Link] conține pe prima linie un număr natural n (3<n<1000), iar pe
următoarea linie, un şir de n numere naturale distincte, de cel mult nouă cifre fiecare.
Numerele din şir sunt separate prin câte un spaŃiu şi cel puțin două dintre ele au ultima
cifră egală cu 5.
a) Scrieți un program C/C++ care citeşte toate numerele din fişier şi, utilizând un algoritm
eficient din punct de vedere al timpului de executare şi al memoriei utilizate, determină şi
afişează pe ecran cele mai mari două numere din şir care au ultima cifră egală cu 5.
Numerele determinate sunt afişate în ordine crescătoare, separate printr-un spațiu.
Exemplu: dacă fişierul [Link] are conŃinutul
alăturat, pe ecran se vor afişa, în această ordine, numerele:
25 85
Afișsare:
10
97 5 11 1 8 6 85 3 25 15
b) Descrieți succint, în limbaj natural (3-4 rânduri), algoritmul utilizat la punctul a) şi
justificați eficiența acestuia.
Timp: O(n)
Memorie: O(1)
V.
Fişierul [Link] conține un şir de cel puŃin 11 şi cel mult un milion de numere naturale,
despărțite prin câte un spațiu. Fiecare număr are cel puțin două şi cel mult nouă cifre.
Primul termen al şirului are numărul de ordine 1, al doilea are numărul de ordine 2 etc.
Se citeşte şirul din fişier şi se cere ca, utilizând un algoritm eficient din punct de vedere al
timpului de executare, să se determine şi să se afişeze pe ecran numărul de ordine al unui
termen al şirului care este precedat în fişier de un număr maxim de valori care au cifra
zecilor egală cu a sa. Dacă sunt mai mulți termeni cu această proprietate, se afişează
numărul de ordine doar al unuia dintre ei.
Exemplu: dacă fişierul [Link] conține numerele
12 36 265 18 139 19 32 34 112 14 68
pe ecran se afişează 10 (numărul de ordine al termenului 14).
a) Descrieți în limbaj natural algoritmul utilizat, justificând eficienŃa acestuia.
Timp: O(n)
Memorie: O(1)