Tuesday, October 19, 2010

ACM - UVA 674 - coin change

Problem : 674 - coin change
Solution : C++
Hints: http://www.algorithmist.com/index.php/UVa_674
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <math.h>
using namespace std;

int oszto[] = {1,5,10,25,50};
int tabla[5][7500], i, j, k;

int  ermevaltas(int n)
{
    for(i = 0; i < n + 1; i++)
        tabla[0][i] = 1;
    for(i = 0; i < 5; i++)
        tabla[1][i] = tabla[2][i] = tabla[3][i] = tabla[4][i] = 1;

    for(i = 1; i < 5; i++)
    {
        for(j = 5; j < n + 1; j++)
        {
            for(k = 0; k <= i; k++)
            {
                if(j >= oszto[k])
                {
                    tabla[i][j] += tabla[k][j - oszto[k]];
                }
            }
        }
    }
}
 

 int main()
{
    ermevaltas(7489);
    while(scanf("%d",&j) == 1)"%
    {
        printf(d\n",tabla[4][j]);
    }
    return 0;
}
 

No comments:

Post a Comment