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!
