#include <stdio.h>
#include <stdlib.h>

/* gw[16] -> Wert der einzelnen Geldstuecke in Pfennig (a[15] kein Geldstueck!) */
/* vari[16]-> Anzahl der einzelnen Geldstuecke  */
unsigned long int gw[16]={ 1,2,5,10,50,100,200,500,1000,2000,5000,
				10000,20000,50000,100000,0};			
unsigned long int vari[16];

unsigned long int mwechsel(int Preis) /* Funktion gib Anzahl der Moeglichkeiten */
				/* des Wechselns fuer Preis in Pfennig zurueck! */
{
    unsigned long int r1;
    unsigned long int TOldp=0; /* Wert den alle Geldstuecke haben ohne */
    			       /* Einpfennigstueck */
    unsigned long int TPreis=0;/* TOldp + Einpfennigstuecke */

    long int count=0;	       /* Zaehler zaehlt gefundene Moeglichkeiten */
    for(r1=0;r1<16;r1++)       /* Wir starten bei 0 Geldstuecken */
     vari[r1]=0;
    vari[0]++;		       /* Unser erster Versuch ist 1 Pfennig */
    while(vari[15]==0)         /* Wenn das imaginaere Geldstueck an der Reihe  */
    {			       /* ist (!=0) koennen wir aufhoeren */
      
      TPreis=TOldp+vari[0];    /* TPreis aus TOldp+Einpfennigstuecke bilden */
      if(TPreis<Preis)	       /* Wenn TPreis kleiner als Preis */
      {			       /* dann koennen wir den fehlenden betrag immer */
	vari[0]+=Preis-TPreis; /* durch n*Einpfennigstuecken ersetzen! */
	count++;	       /* ->count erhoehen(eine weitere Loesung gefunden) */
        vari[0]++;	       /* +Dafuer sorgen das TPreis groesser ist als Preis */
        TPreis=Preis+1;
      }
      if(TPreis==Preis)	       /* Wenn TPreis = Preis dann haben wir eine */
      {			       /* loesung gefunden.(count++ und dafuer sorgen das */
	vari[0]++;	       /* TPreis um eins hoeher als Preis ist.) */
	count++;	       
	TPreis++;
      }
      if(TPreis>Preis)         /* Wenn TPreis groesser als Preis dann machen wir */
      {			       /* Folgendes 1. suchen das niedrigste Geldstueck */
	for(r1=0;r1<15;r1++)   /* 	      dessen Anzahl nicht null ist */
	{		       /*           2. Setzen diese Anzahl auf null 	 */
	  if(vari[r1]!=0)      /*              und ziehen den Betrag*Anzahl */
	  {		       /*              dieses Geldstueckes von TOldp ab. */
	    if(r1!=0)          /*              wenn dieses Geldstueck nicht */
	       TOldp-=gw[r1]*vari[r1];/*       ein Einpfennigstueck ist. */
	    
	    vari[r1]=0;
	    vari[r1+1]++;      /*           3. nun erhoehen wir das naechst-  */
	    TOldp+=gw[r1+1];   /*              hoehere Geldstueck um eins */
	    break;             /*              und addieren den neuen Betrag  */
	    		       /*              auf TOldp und weiter mit der  */
	    		       /*              while-schleife! */
	  }
	}
      }

    }
    
    
    return count;		/*  Anzahl der gefunden Moeglichkeiten rueckgeben */
}				

int main (int argc, char *argv[])
{
  /* Hauptprogramm um eine Eingabem"oglichkeit des zu wechselnden
     Betrages erweitert. Christian Borgelt, 14.12.1997 */

  int amount;

  if (argc != 2) {
    printf("usage: %s amount\n", argv[0]); return 0; }
  amount = atoi(argv[1]);
  if (amount <= 0) {
    printf("%s: amount must be > 0\n", argv[0]); return -1; }

  printf("Ergebnis: %ld \n", mwechsel(amount));
  return 0;
}