Problema algocoin — OJI 2026, Clasa VIII, rezolvare explicată

Algoritmul, pas cu pas

Calculul monedelor. Sortez punctajele crescător. moneda[0] = punctaj[0]; pentru $i \ge 1$ : dacă punctaj[i] == punctaj[i-1] atunci moneda[i] = moneda[i-1], altfel moneda[i] = punctaj[i] * (i+1). (Monedele cresc, deci sunt deja sortate.)

Cerința 2 — perechi divizibile cu $K$ .

Grupez monedele după restul modulo $K$ : cnt[r].
O pereche are suma divizibilă cu $K$ dacă resturile se completează: $r$ cu $(K-r) \bmod K$ .
Adun cnt[r] * cnt[K-r] pentru $r < K-r$ , plus $\binom{cnt[0]}{2}$ și, dacă $K$ e par, $\binom{cnt[K/2]}{2}$ .

Cerința 3 — cel mai mare prag $X$ .

Pentru un $X$ fix, numărul maxim de perechi disjuncte cu suma $> X$ se obține cu doi pointeri pe monedele sortate: dacă moneda[l] + moneda[r] > X, formez pereche și avansez ambii; altfel moneda[l] e prea mică pentru oricine (chiar și cu cel mai mare partener), deci o elimin.
Acest număr scade când $X$ crește, deci caut binar cel mai mare $X = K \cdot t$ pentru care numărul de perechi e cel puțin $P$ .

Complexitate: $O(N \log N)$ (sortare) + $O(N \log(\text{sumă}))$ pentru căutarea binară a cerinței 3.

Soluția în C++

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("algocoin.in");
ofstream fout("algocoin.out");

int main() {
    int C;
    long long N, K, P;
    fin >> C >> N >> K >> P;
    vector<long long> punctaj(N);
    for (auto &x : punctaj) fin >> x;
    sort(punctaj.begin(), punctaj.end());

    vector<long long> moneda(N);
    moneda[0] = punctaj[0];
    for (int i = 1; i < N; i++) {
        if (punctaj[i] == punctaj[i - 1]) moneda[i] = moneda[i - 1];
        else moneda[i] = punctaj[i] * (long long)(i + 1); // rang i+1
    }

    if (C == 1) {
        for (int i = 0; i < N; i++) {
            fout << moneda[i];
            fout << (i + 1 < N ? ' ' : '\n');
        }
    } else if (C == 2) {
        vector<long long> cnt(K, 0);
        for (int i = 0; i < N; i++) cnt[moneda[i] % K]++;
        long long pairs = 0;
        for (long long r = 0; r <= K / 2; r++) {
            long long comp = (K - r) % K;
            if (r == comp) pairs += cnt[r] * (cnt[r] - 1) / 2; // r și r
            else if (r < comp) pairs += cnt[r] * cnt[comp];
        }
        fout << pairs << "\n";
    } else { // C == 3
        sort(moneda.begin(), moneda.end()); // deja crescătoare, dar siguri
        auto maxPerechi = [&](long long X) -> long long {
            int i = 0, j = (int)N - 1;
            long long c = 0;
            while (i < j) {
                if (moneda[i] + moneda[j] > X) { c++; i++; j--; }
                else i++; // cel mai mic nu poate forma nicio pereche validă
            }
            return c;
        };
        long long lo = 0, hi = (moneda[N - 1] + moneda[N - 2]) / K + 1, best = 0;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            if (maxPerechi(mid * K) >= P) { best = mid * K; lo = mid + 1; }
            else hi = mid - 1;
        }
        fout << best << "\n";
    }
    return 0;
}

Greșeli frecvente

Folosești int pentru monede — moneda poate fi $10^6 \cdot 2 \cdot 10^5 = 2 \cdot 10^{11}$ , deci long long obligatoriu, altfel overflow.
Numeri dublu la cerința 2 — pentru restul $0$ și pentru $K/2$ (când $K$ e par) perechile sunt în interiorul aceleiași grupe: folosește $\binom{cnt}{2}$ , nu $cnt \cdot cnt$ .
Încerci toți multiplii lui $X$ pe rând la cerința 3 — cu valori până la $\sim 4 \cdot 10^{11}$ ar fi prea mulți; folosește monotonia (perechi scad când $X$ crește) și caută binar.

Algoritmul, pas cu pas

Calculul monedelor. Sortez punctajele crescător. moneda[0] = punctaj[0]; pentru

i \ge 1

: dacă punctaj[i] == punctaj[i-1] atunci moneda[i] = moneda[i-1], altfel moneda[i] = punctaj[i] * (i+1). (Monedele cresc, deci sunt deja sortate.)

Cerința 2 — perechi divizibile cu $K$ .

Grupez monedele după restul modulo

K

: cnt[r].

O pereche are suma divizibilă cu

K

dacă resturile se completează:

r

(K-r) \bmod K

Adun cnt[r] * cnt[K-r] pentru

r < K-r

, plus

\binom{cnt[0]}{2}

și, dacă

K

e par,

\binom{cnt[K/2]}{2}

Cerința 3 — cel mai mare prag $X$ .

Pentru un

X

fix, numărul maxim de perechi disjuncte cu suma

> X

se obține cu doi pointeri pe monedele sortate: dacă moneda[l] + moneda[r] > X, formez pereche și avansez ambii; altfel moneda[l] e prea mică pentru oricine (chiar și cu cel mai mare partener), deci o elimin.

Acest număr scade când

X

crește, deci caut binar cel mai mare

X = K \cdot t

pentru care numărul de perechi e cel puțin

P

Complexitate:

O(N \log N)

(sortare) +

O(N \log(\text{sumă}))

pentru căutarea binară a cerinței 3.

Soluția în C++

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("algocoin.in");
ofstream fout("algocoin.out");

int main() {
    int C;
    long long N, K, P;
    fin >> C >> N >> K >> P;
    vector<long long> punctaj(N);
    for (auto &x : punctaj) fin >> x;
    sort(punctaj.begin(), punctaj.end());

    vector<long long> moneda(N);
    moneda[0] = punctaj[0];
    for (int i = 1; i < N; i++) {
        if (punctaj[i] == punctaj[i - 1]) moneda[i] = moneda[i - 1];
        else moneda[i] = punctaj[i] * (long long)(i + 1); // rang i+1
    }

    if (C == 1) {
        for (int i = 0; i < N; i++) {
            fout << moneda[i];
            fout << (i + 1 < N ? ' ' : '\n');
        }
    } else if (C == 2) {
        vector<long long> cnt(K, 0);
        for (int i = 0; i < N; i++) cnt[moneda[i] % K]++;
        long long pairs = 0;
        for (long long r = 0; r <= K / 2; r++) {
            long long comp = (K - r) % K;
            if (r == comp) pairs += cnt[r] * (cnt[r] - 1) / 2; // r și r
            else if (r < comp) pairs += cnt[r] * cnt[comp];
        }
        fout << pairs << "\n";
    } else { // C == 3
        sort(moneda.begin(), moneda.end()); // deja crescătoare, dar siguri
        auto maxPerechi = [&](long long X) -> long long {
            int i = 0, j = (int)N - 1;
            long long c = 0;
            while (i < j) {
                if (moneda[i] + moneda[j] > X) { c++; i++; j--; }
                else i++; // cel mai mic nu poate forma nicio pereche validă
            }
            return c;
        };
        long long lo = 0, hi = (moneda[N - 1] + moneda[N - 2]) / K + 1, best = 0;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            if (maxPerechi(mid * K) >= P) { best = mid * K; lo = mid + 1; }
            else hi = mid - 1;
        }
        fout << best << "\n";
    }
    return 0;
}

Greșeli frecvente

Folosești int pentru monede — moneda poate fi $10^6 \cdot 2 \cdot 10^5 = 2 \cdot 10^{11}$ , deci long long obligatoriu, altfel overflow.
Numeri dublu la cerința 2 — pentru restul $0$ și pentru $K/2$ (când $K$ e par) perechile sunt în interiorul aceleiași grupe: folosește $\binom{cnt}{2}$ , nu $cnt \cdot cnt$ .
Încerci toți multiplii lui $X$ pe rând la cerința 3 — cu valori până la $\sim 4 \cdot 10^{11}$ ar fi prea mulți; folosește monotonia (perechi scad când $X$ crește) și caută binar.

algocoin

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

algocoin

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++