#include <stdio.h>
#include <stdlib.h>
/*
Za pomoca programowania dynamicznego zaimplementuj procedure optymalnego wydawania reszty.

Dostepne nominaly to: 1, 2, 5, 10, 20, 50, 100, 200, 500

Przykladowo dla kwoty r=1358, program powinien wypisac:

Optymalna ilosc monet wydanych dla kwoty 1358:
Nominal   1: 1 szt.
Nominal   2: 1 szt.
Nominal   5: 1 szt.
Nominal  10: 0 szt.
Nominal  20: 0 szt.
Nominal  50: 1 szt.
Nominal 100: 1 szt.
Nominal 200: 1 szt.
Nominal 500: 2 szt.


Dla kwoty r=167, program powinien wypisac:

Optymalna ilosc monet wydanych dla kwoty 167:
Nominal   1: 0 szt.
Nominal   2: 1 szt.
Nominal   5: 1 szt.
Nominal  10: 1 szt.
Nominal  20: 0 szt.
Nominal  50: 1 szt.
Nominal 100: 1 szt.
Nominal 200: 0 szt.
Nominal 500: 0 szt.

*/

// Funkcja wykonujaca wydawanie reszty za pomoca programowania dynamicznego
void wydawanieReszty(int* c, int n, int r)
{
    int i, j;

    // Alokuje pamiec na tablice o i s
    int* o = (int*)malloc(r * sizeof(int));
    int* s = (int*)malloc(r * sizeof(int));

    // Tablica k przechowuje ilosc uzytych monet
    int* k = (int*)malloc(n * sizeof(int));
    for (j = 0; j < n; ++j) {
        k[j] = 0; // Inicjalizuje zerami
    }
    // lub krocej za pomoca calloc
    // int* k = (int*)calloc(n, sizeof(int));

    // Obliczenia dla programowania dynamicznego
    for (j = 0; j < n; ++j) {
        for (i = 0; i < r; ++i) {
            if (j == 0) {
                o[i] = i + 1;
                s[i] = 0;
            } else if ((i + 1) == c[j]) {
                o[i] = 1;
                s[i] = j;
            } else if (((i + 1) > c[j]) && (o[i] > o[i - c[j]])) {
                o[i] = o[i - c[j]] + 1;
                s[i] = j;
            }
        }
    }

    printf("Optymalna ilosc monet wydanych dla kwoty %d:\n\n", r);

    // Oblicza ilosc uzytych monet
    while (r > 0) {
        k[s[r - 1]] += 1;
        r -= c[s[r - 1]];
    }

    // Wypisanie wyniku
    for (i = 0; i < n; ++i) {
        printf("Nominal% 4d: %d szt.\n", c[i], k[i]);
    }

    // Zwolnienie zaalokowanej pamieci
    free(o);
    free(s);
}

int main() {

    int a[] = {1, 2, 5, 10, 20, 50, 100, 200, 500}; //tablica nominalow
    int n = sizeof(a) / sizeof(a[0]);   //wielkosc tablicy a (sama tablice przekazujemy przez wskaznik)
    int r = 167; // rozpatrywana kwota

    wydawanieReszty(a, n, r);

    return 0;
}