Question

Va rog un program de 100pcte pe pbinfo(#1925), imi trebuie la suplimentar xd.

Cerința
Se dau două numere naturale S şi K. Să se afle cel mai mic număr natural A care are suma cifrelor egală cu S, precum şi restul împărţirii lui A la K.

Date de intrare
Fișierul de intrare numar9.in conține pe prima linie numerele naturale S şi K.

Date de ieșire
Fișierul de ieșire numar9.out va conține pe prima linie numărul A, iar pe a doua linie restul împărţirii lui A la K.

Restricții și precizări
1 ≤ S ≤ 20.000.000
1 ≤ K ≤ 1.000.000
Pentru prima cerinţă se acordă 60p, iar pentru a doua 40p
Pentru a primi punctajul pentru a doua cerinţă, în fişierul numar9.out trebuie să afişaţi două numere

Exemplu
numar9.in

25 13
numar9.out

799
6
Explicație
Cel mai mic număr natural care are suma cifrelor egală cu 25 este 799. Restul împărţirii lui 799 la 13 este 6.

Answer 1

Of, informatica asta.
Anyway, o sa iti dau si solutia oficiala si solutia facuta de mine, dupa ce explic putin, cum pot eu.
Ca sa obtinem cel mai mic numar trebuie sa tinem cont de doua lucruri: numarul de cifre si prima cifra a numarului. Ca numarul de cifre sa fie cat mai mic, trebuie ca numarul nostru sa contina cat de multe cifre de 9 posibil (adica numarul maxim de cifre de noua ce adunate nu depasesc suma data). Observam ca acest numar e chiar partea intreaga a s/9 (in exemplu 25/9=2). Iar, ca sa punem in aplicare a doua conditie necesara, punem s%9 prima cifra numarului (in cazul asta, 7).
Pretty cool, right? Doar ca S poate fi maxim 20.000.000. 20.000.000/9=2.222.222, ceea ce inseamna ca pentru S 20.000.000 numarul afisat va avea mai mult de doua milioane de cifre. Scary. Nu poti stoca asa un numar nici in long long unsigned.
Asa ca, eu am pus cifrele numarului intr-un vector. Initial, in fiecare element al vectorului aveam cate o cifra, dar asa algoritmul depasea limita de timp. Asa ca, am pus, cand aveam posibilitatea, grupe de cate 6 cifre de n intr-un element de vector. Numar format, totul ok, restul se calculeaza cu ceva chestie explicata la indicatii pe care n-o sa mai ma chinui  sa o explic (atasez screenshot though)

Solutia mea
#include <iostream>#include <fstream>using namespace std;long long unsigned s,x,r,con;long long nrnoua,nrnouamic;ifstream fin ("numar9.in");ofstream fout ("numar9.out");int unsigned k,i,v[2200001];int main(){    fin>>s>>k;
    r=s%9;    nrnoua=s/9;    nrnouamic=nrnoua/6;    for (i=1;i<=nrnouamic;i++)        v[i]=999999;    for (i=nrnouamic+1;i<=nrnouamic+nrnoua%6;i++)    {        v[i]=9;    }    if (r!=0&&s!=0)        v[0]=r;    x=0;    if (v[0]!=0)        for (i=0;i<=nrnouamic+nrnoua%6;i++)        {            fout<<v[i];            if (v[i]<10)                x=(x*10+v[i])%k;            else                {                    while (v[i]!=0)                    {                        x=(x*10+v[i]%10)%k;                        v[i]=v[i]/10;                    }                }        }    else        for (i=1;i<=nrnouamic+nrnoua%6;i++)        {            fout<<v[i];            if (v[i]<10)                x=(x*10+v[i])%k;            else                {                    while (v[i]!=0)                    {                        x=(x*10+v[i]%10)%k;                        v[i]=v[i]/10;                    }                }        }
        fout<<' '<<x;
//cout<<con*6+nrnouamic%6;    return 0;}
Solutia oficiala
01.#include <fstream>02.#define a 99999999903. 04.using namespace std;05.ifstream f("numar9.in");06.ofstream g("numar9.out");07. 08.long long s , k , i , r , c , x , m , n ;09. 10.int main()11.{12.f >> s >> k ;13.r = s % 9 ;14.c = s / 9 ;15.m = c / 9 ;16.n = c % 9 ;17.if ( r != 0 ) g << r ;18.x = r % k ;19.for ( i = 1 ; i <= n ; i++ )20.{21.g << 9 ;22.x = ( x * 10 + 9 ) % k ;23.}24.for ( i = 1 ; i <= m ; i++ )25.{26.g << a ;27.x = ( x * 1000000000 + a ) % k ;28.}29.g << "\n" ;30.g << x ;31. 32.return 0;33.}

happy coding!