Question

Cerința
Se dau numerele naturale a, b, c și d cu proprietatea că a < b < c < d. Să se determine câte numere naturale divizibile cu 3 sunt în reuniunea de intervale [a,b] ∪ [c,d].

Date de intrare
Programul citește de la tastatură numerele naturale a, b, c, d.

Date de ieșire
Programul va afișa pe ecran numărul de numere naturale divizibile cu 3 din [a,b] ∪ [c,d].

Restricții și precizări
2 ≤ a < b < c < d ≤ 2.000.000.000

Answer 1

► SOLUTIE SIMPLA, INEFICIENTA, PENTRU INCEPATORI :

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a, b, c, d;

int contor = 0;

cin >> a >> b >> c >> d;

for (a; a <= b; a++)

 if (a % 3 == 0) ++contor;

for (c; c <= d; c++)

 if (c % 3 == 0) ++contor;

cout << contor;

}

► Explicatie

Aceasta solutie ia la rand numerele din cele doua intervale si verifica daca acestea sunt divizibile cu 3. Solutia nu e recomandata, avand o complexitate liniara.

Aceasta solutie e foarte usor de inteles, dar pe diferite site-uri de provocari competitive de programare (aka amaraciunea de pbinfo #3928) nu vei obtine punctaj foarte mare.

► SOLUTIE EFICIENTA (100p) :

#include <iostream>

using namespace std;

int main() {

int a, b, c, d;

int contor = 0;

cin >> a >> b >> c >> d;

//Aducem a si c la cele mai mici numere din interval divizibile cu 3

while (a % 3)++a;

while (c % 3)++c;

//Aducem b di d la cele mai mari numere din interval divizibile cu 3

while (b % 3)--b;

while (d % 3)--d;

//Determinam numarul de elemente divizibile cu 3 din cele doua intervale

int contor1 = (b - a) / 3 + 1;

int contor2 = (d - c) / 3 + 1;

int total = contor1 + contor2;

 //Afisam rezultatul

cout << total;

}

► Explicatie :

Folosim formula matematica : Daca a si b (a≤b) sunt doua numere divizibile cu n atunci in intervalul [a,b] exista $\frac{b-a}{n}+1$ numere divizibile cu n.

Din acest motiv va trebui sa aducem toate valorile la numere divizibile cu 3 din interval - pentru a si c gasim primele numere, iar pentru b si d gasim ultimele numere.

Aplicam formula si adunam numarul de valori gasite pentru fiecare interval.

Aceasta solutie are o complexitate constanta.