Link către problema multiple -> link

Înainte de a citi ghidul de rezolvare, încearcă propria ta soluție!

Pentru această problemă există două abordări eficiente și simple care aduc de la sine 100 de puncte, o variantă lungă si una scurtă. Varianta lungă este, în general, cea care îți vine cel mai repede în mine. Varianta scurtă se rezumă la folosirea unei formule de calcul. Cu greu ați putea avea probleme legate de timp sau memorie la această problemă.

Să începem prin a descrie varianta brută, care ia pas cu pas problema. Se va construi o structură repetitivă în cadrul căreia se vor citi din fișier perechile de numere precizate în problemă.

Imediat după citire, se va verifica dacă variabila k este mai mare sau nu decât variabila n.

• Dacă este mai mare, atunci nu mai este nevoie de niciun algoritm de căutare a numărului strict mai mare decât n și divizibil cu k, ci doar îl vom afișa pe k.
• În caz contrar, algoritmul de căutare va avea loc, iar primul lucru pe care îl vom face va fi să mărim cu 1 variabila n, deoarece este precizat în enunț că numărul dorit trebuie să fie strict mai mare decât n. După aceea, folosindu-ne de o structură repetitivă, vom mări n cu o unitate de fiecare dată când vedem că n nu este divizibil cu k.

Când n devine divizibil cu k, structura repetitivă se va opri, iar noi vom fi siguri că acela este numărul de care avem nevoie.

Soluția lungă în C++:

#include <fstream>;

using namespace std;

ifstream f("multiple.in");
ofstream g("multiple.out");

int main()
{
    int t, n, k;
    f >> t; //citim numarul de perechi de numere

    while(t != 0) //cat timp acest numar este diferit de 0
    {
        f >> n >> k; //citim perechile de numere
        if(n < k) //daca al doilea numar este mai mare decat primul, nu mai are rost sa ne complicam cautandu-l
            g << k;
        else
            {
                //de aici incepem cautarea celui mai mic numar strict mai mare decat n si divizibil cu k
                n++;
                while(n % k != 0) //cat timp numarul nu este divizibil cu k, vom mari numarul cu 1
                    n++;
                g << n; //cand structura repetitiva while se sfarseste, stim sigur ca n este numarul dorit
            }
        if(t != 1) //aceasta structura are loc doar ca dupa ultimul rand sa nu mai fie adaugat un spatiu in plus, deoarece este trecut ca raspuns gresit, indiferent daca algoritmul este corect sau nu
            g << '\n';
        t--;
    }
    return 0;
}

Varianta scurtă și elegantă ține de o formulă simplă și interesantă. Să o deducem logic, printr-un exemplu: n= 393 și k= 300. Se vede clar că cel mai mic număr, strict mai mare decât 393 și divizibil cu 300 este 600. Cum ajungem la el? Ei bine, știm că 600=300*2, deci în cadrul formulei va trebui să apară o sumă care va da acest număr, folosindu-se de k. Avem, deci, un punct de pornire al formulei: k+k; Dar, bineînțeles, nu e suficient; avem nevoie în alte cazuri de mai multe apariții ale lui k. Să ne punem întrebarea: Unde mai găsim multipli de k? Simplu, în n. Observăm că 393=300+93, adică, generalizat, n=m*k+r, unde m arată de câte ori apare k în n, iar r este n%k; Astfel, de la k+k, putem avansa la k+n, care este echivalent cu k+m*k+r, adică numărul de care avem nevoie ( k*(m+1) ) și n%k. Pentru a scăpa de surplus, vom scădea din formulă n%k, fomula finală devenind k+n-n%k;

Soluția scurtă în C++:

#include <fstream>;

using namespace std;

ifstream f("multiple.in");
ofstream g("multiple.out");

int main()
{
    int t, n, k;
    f >> t; //citim numarul de perechi de numere

    while(t != 0) //cat timp acest numar este diferit de 0
    {
        f >> n >> k;
        g << k + n - (n % k); //formula descrisa inainte
        if(t != 1)
            g << '\n';
    }
    return 0;
}

Dacă te simți înflăcărat și dornic de a fi mai bun la programare după această problemă, îți propun următoarele exerciții, asemănătoare cu problema noastră:

1. În loc să citiți din fișier t perechi de numere, citiți t triplete de numere. Al treilea număr va reprezenta a treia condiție pe care numărul cerut va trebui să o satisfacă, și anume: Dacă al treilea număr este 1, atunci numărul cerut va trebui să fie par, iar dacă este 2, impar.
2. La fel, se citesc t triplete de numere, doar că primele două, n și k, vor reprezenta un interval închis, unde n<k, iar al treilea, d să zicem, va prelua rolul de condiție. Noua cerință este să se determine toate numerele divizibile cu d din intervalul închis n,k.
3. Se citesc t cvadruplete de numere, n,k,d,r. Se îmbină cele două enunțuri anterioare (intervalul închis n, k; d preia rolul de condiție; apare numărul r care va fi 1 sau 2, așa cum este precizat în cadrul primei cerințe), iar cerința finală este să se creeze și apoi să se afișeze un vector cu elementele sortate crescător pentru fiecare întrebare, care va cuprinde toate numerele din intervalul n,k care sunt divizibile cu d și care, depinzând de r, sunt pare sau impare.