oac

Algoritmul, pas cu pas

Cheia: broscuța cu intervalul $K$ cântă fix în secundele $K, 2K, 3K, \dots$ care nu depășesc $T$, adică de $\lfloor T / K \rfloor$ ori. Pentru că $T$ poate ajunge la $10^8$ și timpul e doar $0{,}1$ secunde, nu parcurgem secundele una câte una, ci folosim formule.

Cerința 1 — maximul individual. Răspunsul este $\max(\lfloor T/K_1 \rfloor, \lfloor T/K_2 \rfloor, \lfloor T/K_3 \rfloor)$.

Cerința 3 — numărul de duete.

1. Două broscuțe cu intervalele $K_i$, $K_j$ cântă simultan exact în multiplii lui $\text{cmmmc}(K_i, K_j)$, deci de $\lfloor T / \text{cmmmc}(K_i, K_j) \rfloor$ ori.
2. Adun aceste valori pentru cele $3$ perechi.
3. Momentele când cântă toate trei (multiplii lui $\text{cmmmc}(K_1, K_2, K_3)$) nu sunt duete, dar sunt numărate în fiecare dintre cele $3$ perechi. Le scad de $3$ ori.

$\text{duete} = \sum_{\text{perechi}} \left\lfloor \frac{T}{\text{cmmmc}(K_i, K_j)} \right\rfloor - 3 \left\lfloor \frac{T}{\text{cmmmc}(K_1, K_2, K_3)} \right\rfloor$

Cerința 2 — primul duet. Cel mai devreme duet al unei perechi e chiar $\text{cmmmc}(K_i, K_j)$ — dar numai dacă acolo nu cântă și a treia broscuță, adică dacă $\text{cmmmc}(K_i, K_j) < \text{cmmmc}(K_1, K_2, K_3)$. Răspunsul e cel mai mic astfel de cmmmc de pereche (care nu depășește $T$).

Toate cerințele se rezolvă în $O(\log K)$ (pentru cmmmc) — independent de $T$.

Soluția în C++

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

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

long long cmmdc(long long a, long long b) {
    while (b) { long long r = a % b; a = b; b = r; }
    return a;
}
long long cmmmc(long long a, long long b) {
    return a / cmmdc(a, b) * b; // împărțim întâi ca să nu depășim long long
}

int main() {
    int C;
    fin >> C;
    long long k1, k2, k3, T;
    fin >> k1 >> k2 >> k3 >> T;

    if (C == 1) {
        // multiplii fiecărui interval până la T
        fout << max({T / k1, T / k2, T / k3}) << "\n";
    } else {
        long long L12 = cmmmc(k1, k2);
        long long L13 = cmmmc(k1, k3);
        long long L23 = cmmmc(k2, k3);
        long long L123 = cmmmc(L12, k3); // toate trei deodată

        if (C == 3) {
            // perechi - de 3 ori momentele cu toate trei (nu sunt duete)
            long long duete = T / L12 + T / L13 + T / L23 - 3 * (T / L123);
            fout << duete << "\n";
        } else { // C == 2
            long long pairs[3] = {L12, L13, L23};
            long long best = -1;
            for (int i = 0; i < 3; i++) {
                // un duet apare la cmmmc-ul perechii doar dacă acolo NU cântă a treia
                if (pairs[i] < L123 && pairs[i] <= T) {
                    if (best == -1 || pairs[i] < best) best = pairs[i];
                }
            }
            fout << best << "\n";
        }
    }
    return 0;
}