Irinei îi plac numerele naturale. Ea știe că orice număr natural cu cifre nenule se poate reprezenta ca un șir de cifre din mulțimea A={1, 2,..., 9}. Irina își alege o cifră k şi îşi propune să afle câte numere naturale au suma cifrelor egală cu un număr dat S și în același timp se reprezintă folosind doar cifre din mulţimea {1, 2,..., k}.
Cerința
Dându-se S şi k, se cere să se determine ultima cifră a numărului de numere naturale care se reprezintă doar cu cifre din mulțimea {1,...,k} și au suma cifrelor egală cu S.
Date de intrare
Fișierul de intrare numere4.in conține pe prima linie numerele naturale T şi k, separate printr-un spaţiu, unde T reprezintă numărul de teste, iar k are semnificaţia din enunţ.
Pe linia a doua se găsesc T numere naturale, separate prin câte un spaţiu. Al i-lea număr de pe linia a doua reprezintă suma S corespunzătoare celui de-al i-lea test.
Date de ieșire
Fișierul de ieșire numere4.out va conține pe prima linie, separate prin câte un spaţiu, T cifre calculate conform cerinţelor, în ordinea dată de fişierul de intrare.
Restricții și precizări
1 ≤ T ≤ 102 ≤ k ≤ 51 ≤ S ≤ 230
Exemplu
numere4.in
2 3 3 5
numere4.out
4 3
Explicație
Cu cifrele {1,2,3} şi suma cifrelor egală cu 3 putem scrie numerele 111, 12, 21, 3 deci 4 numere. Ultima cifră lui 4 este 4.
Cu cifrele {1,2,3} şi suma cifrelor egală cu 5 putem scrie numerele 11111, 1112, 1121, 1211, 2111, 122, 212, 221, 113, 131, 311, 23, 32 deci 13 numere. Ultima cifră lui 13 este 3.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Numere4:
#include<stdio.h>
int t,s,k,nr,j,i,l,per1,per2,p,z,it;
int d[100009];
int x[100009];
int main()
{
freopen("numere4.in","rt",stdin);
freopen("numere4.out","wt",stdout);
scanf("%d %d",&t,&k);
p=1;
for (i=1;i<k;i++)p=p*10;
for (it=1;it<=t;it++)
{
scanf("%d",&s);
for (i=0;i<p*10;i++)
d[i]=-1;
x[0]=1;
nr=1;
for (i=1;i<k;i++)
{
x[i]=0;
for (l=1;l<=k;l++)
{
if (i-l>=0)
x[i]=(x[i]+x[i-l])%10;
}
nr=nr*10+x[i];
d[nr]=i;
}
for (i=k;i<=s; i++)
{
x[i]=0;
for (l=1;l<=k;l++)
{
if (i-l>=0)
x[i]=(x[i]+x[i-l])%10;
}
nr=nr%p;
nr=nr*10+x[i];
if (d[nr]!=-1 && nr>0) {
per1=d[nr]; per2=i;break;
}
else d[nr]=i;
}
if (i>s)z=x[s];
else z=x[s%(per2-per1)];
printf("%d ",z);
}
fclose(stdout);
fclose(stdin);
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #701 Numere4
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #701 Numere4 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!