Salut! Iată soluții eficiente pentru problemele avansate, folosind doar cele 3 biblioteci permise: <iostream>, <fstream> și <cmath>.
Problema 1: Divizorul 26^p în n!
#include <iostream>
#include <fstream>
using namespace std;
int main() {
long long n;
cin >> n;
// Calculăm puterea lui 13 în n! (26 = 2 × 13, iar 13 este limitatorul)
long long p = 0;
long long putere13 = 13;
while (putere13 <= n) {
p += n / putere13;
putere13 *= 13;
}
ofstream fout("bac.txt");
fout << p;
fout.close();
return 0;
}Eficiență: O(log₁₃ n) timp, O(1) memorie
Problema 2: Perioade Valide de Monitorizare
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("bac.in");
int minz, minP;
fin >> minz >> minP;
int ziua = 1;
int stanga = 1, suma = 0;
bool in_perioada = false;
bool exista = false;
int stoc;
while (fin >> stoc) {
if (stoc >= minz) {
suma += stoc;
if (!in_perioada && suma >= minP) {
in_perioada = true;
exista = true;
cout << stanga << " ";
}
ziua++;
} else {
if (in_perioada) {
cout << ziua - 1 << " " << suma << endl;
}
in_perioada = false;
suma = 0;
stanga = ziua + 1;
ziua++;
}
}
if (in_perioada) {
cout << ziua - 1 << " " << suma << endl;
}
if (!exista) {
cout << "nu exista" << endl;
}
fin.close();
return 0;
}Problema 3: Triunghiuri Dreptunghice cu Aceeași Ipotenuză
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main() {
ifstream fin("bac.txt");
int a, b, c;
// Folosim un vector de frecvență pentru ipotenuze (max 10^9 e prea mare)
// Vom folosi un algoritm care nu necesită întreg vectorul
// Dar trebuie să știm valoarea maximă a ipotenuzei
// Citim o dată pentru a găsi maximul
int max_ip = 0;
int temp_a, temp_b, temp_c;
ifstream fin2("bac.txt"); // A doua citire
// Prima citire pentru maxim
while (fin >> a >> b >> c) {
// Sortăm pentru a avea ipotenuza pe ultima poziție
if (a > b) { int t = a; a = b; b = t; }
if (b > c) { int t = b; b = c; c = t; }
if (a > b) { int t = a; a = b; b = t; }
if (a*a + b*b == c*c && c > max_ip) {
max_ip = c;
}
}
fin.close();
if (max_ip == 0) {
cout << 0;
return 0;
}
// Al doilea vector de frecvență
int* frec = new int[max_ip + 1](); // inițializat cu 0
// A doua citire pentru numărare
while (fin2 >> a >> b >> c) {
if (a > b) { int t = a; a = b; b = t; }
if (b > c) { int t = b; b = c; c = t; }
if (a > b) { int t = a; a = b; b = t; }
if (a*a + b*b == c*c) {
frec[c]++;
}
}
fin2.close();
int max_count = 0;
for (int i = 0; i <= max_ip; i++) {
if (frec[i] > max_count) {
max_count = frec[i];
}
}
cout << max_count;
delete[] frec;
return 0;
}Problema 4: Șir Recurent și Termeni ≤ z
#include <iostream>
#include <fstream>
using namespace std;
int main() {
int x, y, z;
cin >> x >> y >> z;
// Determinăm pozițiile aproximative (nu sunt necesare exact)
// Generăm termenii până depășim z
int f1 = 0, f2 = 0, f3 = 1;
// Vector pentru termenii ≤ z
int termeni[1000]; // presupunem că nu vor fi peste 1000
int n = 0;
termeni[n++] = 0; // f1
termeni[n++] = 0; // f2
termeni[n++] = 1; // f3
// Generăm mai departe
int fn;
do {
fn = 4*termini[n-1] - 3*termini[n-2] - 2*termini[n-3];
if (fn <= z) {
termeni[n++] = fn;
}
} while (fn <= z);
// Afișăm în ordine descrescătoare
ofstream fout("bac.txt");
for (int i = n-1; i >= 0; i--) {
fout << termeni[i] << " ";
}
fout.close();
return 0;
}Problema 5: Numărul Maxim de Perechi cu Valori Egale
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("date.in");
int m, n;
fin >> m >> n;
int frecA[101] = {0}; // numerele sunt în [0,100]
int frecB[101] = {0};
// Citim șirul A
for (int i = 0; i < m; i++) {
int x;
fin >> x;
frecA[x]++;
}
// Citim șirul B
for (int i = 0; i < n; i++) {
int x;
fin >> x;
frecB[x]++;
}
// Calculăm perechile
int perechi = 0;
for (int i = 0; i <= 100; i++) {
if (frecA[i] < frecB[i]) {
perechi += frecA[i];
} else {
perechi += frecB[i];
}
}
cout << perechi;
fin.close();
return 0;
}Problema 6: Secvențe Paritare de Lungime Maximă
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("bac.txt");
int numar, anterior;
int lung_curenta = 1, lung_maxima = 0;
int count_maxime = 0;
if (!(fin >> anterior)) {
cout << "0 0";
return 0;
}
while (fin >> numar) {
// Verificăm aceeași paritate
bool paritate_anterioara = (anterior % 2 == 0);
bool paritate_curenta = (numar % 2 == 0);
if (paritate_anterioara == paritate_curenta) {
lung_curenta++;
} else {
if (lung_curenta > lung_maxima) {
lung_maxima = lung_curenta;
count_maxime = 1;
} else if (lung_curenta == lung_maxima) {
count_maxime++;
}
lung_curenta = 1;
}
anterior = numar;
}
// Verificăm ultima secvență
if (lung_curenta > lung_maxima) {
lung_maxima = lung_curenta;
count_maxime = 1;
} else if (lung_curenta == lung_maxima) {
count_maxime++;
}
cout << count_maxime << " " << lung_maxima;
fin.close();
return 0;
}Problema 7: Cea mai Mare Cifră din Șir
#include <iostream>
#include <fstream>
using namespace std;
int cifra_maxima(int n) {
int max_cif = 0;
while (n > 0) {
int cifra = n % 10;
if (cifra > max_cif) {
max_cif = cifra;
}
n /= 10;
}
return max_cif;
}
int main() {
ifstream fin("numere.in");
int numar;
int cifra_max_global = -1;
int primul = -1, ultimul = -1;
while (fin >> numar) {
int cifra_local = cifra_maxima(numar);
if (cifra_local > cifra_max_global) {
cifra_max_global = cifra_local;
primul = numar;
ultimul = numar;
} else if (cifra_local == cifra_max_global) {
if (primul == -1) {
primul = numar;
}
ultimul = numar;
}
}
if (primul == -1 || primul == ultimul) {
cout << "nu exista";
} else {
cout << primul << " " << ultimul;
}
fin.close();
return 0;
}Problema 8: Pași Reprezentativi (Temperaturi)
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("bac.txt");
int temperatura;
int temperatura_maxima = -1;
int pas = 1;
int temperatura_anterioara = -1;
bool primul_afisat = false;
while (fin >> temperatura) {
if (temperatura > temperatura_maxima) {
temperatura_maxima = temperatura;
if (primul_afisat) cout << " ";
cout << pas;
primul_afisat = true;
}
// Verificăm dacă e prima apariție într-o secvență de valori egale
if (temperatura != temperatura_anterioara) {
temperatura_anterioara = temperatura;
}
pas++;
}
fin.close();
return 0;
}🎯 Reguli de Aur pentru Algoritmi Eficienți:
- Citire/O scriere secvențială – nu încărca tot în memorie
- Un singur parcurs când e posibil (O(n))
- Vectori de frecvență pentru valori mici (0-100, 0-1000)
- Two pointers pentru probleme cu secvențe
- Formule matematice în loc de brute force
💡 Exemplu: Suma primelor n numere
Ineficient (O(n)):
int suma = 0;
for(int i=1; i<=n; i++) suma += i;Eficient (O(1)):
int suma = n*(n+1)/2; // formulă matematicăSucces la implementare! Ai acum toate instrumentele pentru problemele complexe de la Bacalaureat. 🚀