[PBINFO] Problema #1004

[~Wolf~]

Link site: pbinfo (<b>You have to register to ba able to see this link</b>)
Link problema: eureni (<b>You have to register to ba able to see this link</b>)
-draguta problema, am mers pe ideea urmatoare: luam un vector unde stocam acei "eureni", primul fiind obligatoriu 1, iar celalti sunt puteri ale lui "e".
-nr de bancnote reprezinta catul impartirii lui S la un element al vectorului.Pentru a gasi bancnote a carei aparitii este macar 1, impunem conditia ca daca catul este 0 sa nu luam in considerare elementul respectiv al vectorului.
De exemplu pt e=5, vom avea in vector 1 5 25 125 625, cu S=107.Nu ne intereseaza 125, fiindca niciodata nu vom avea acel tip de bancnota(107/125=0, fals in conditia pe care am impus-o, trecem la 25 care corespunde).

#include <fstream>
using namespace std;

ifstream fin("eureni.in");
ofstream fout("eureni.out");

void Citire(unsigned int& S, unsigned int& n, unsigned int& e)
{
fin >> S >> n >> e;
}

void Greedy(unsigned int S, unsigned int n, unsigned int e)
{
unsigned int v[11], nrBancnote=0;
v[1] = 1;
for (unsigned int i = 2; i <= n + 1; i++)
{
v[i] = v[i - 1] * e;
}
for (int i = n + 1; i > -1; i--)
{
unsigned int catul;
catul = S / v[i];
if (catul)
{
fout << v[i] << ' ' << catul << endl;
nrBancnote += catul;

S = S - (catul * v[i]);
}
}
fout << nrBancnote;
}

int main()
{
unsigned int S, n, e;
Citire(S, n, e);
Greedy(S, n, e);
return 0;
}