lectiipenet.ro

Algoritmi Eficienți în C++ cu , ,

Written by

admin

in

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:

  1. Citire/O scriere secvențială – nu încărca tot în memorie
  2. Un singur parcurs când e posibil (O(n))
  3. Vectori de frecvență pentru valori mici (0-100, 0-1000)
  4. Two pointers pentru probleme cu secvențe
  5. 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. 🚀

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts