👤
a fost răspuns

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

Răspuns :

ENANDREI750238

► 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 [tex]\frac{b-a}{n}+1[/tex] 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.

Vă mulțumim că ați ales să vizitați site-ul nostru dedicat Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări sau aveți nevoie de asistență suplimentară, vă rugăm să ne contactați. Revenirea dumneavoastră ne va bucura, iar pentru acces rapid, nu uitați să ne salvați la favorite!


En Trainingsy: Alte intrebari