3b_money

#include <iostream>
using namespace std;
//#include <stdio.h>

#define MAX_ADDS 100000

/* Сума, която ще разбиваме */
//const unsigned n = 25;
/* Брой различни стойности на монетите */
const unsigned gN = 7;
/* Стойности на монетите */
const unsigned given[] = { 200, 100, 50, 20, 10, 5, 2 };

unsigned mp[MAX_ADDS], count=0, n;
/*
void print(unsigned lenght)
{ unsigned i;
  for (i = 1; i < lenght; i++) printf("%u + ", mp[i]);
  printf("%d\n", mp[lenght]);
}
*/
void devNum(unsigned n, unsigned pos)
{ unsigned k, p;
  for (p = gN; p > 0; p--) {
    k = given[p - 1];
    if (n > k) {
      mp[pos] = k;
      if (mp[pos] <= mp[pos - 1]) devNum(n - k, pos + 1);
    }
    else if (n == k) {
      mp[pos] = k;
      if (mp[pos] <= mp[pos - 1]) count++;// print(pos);
    }
  }
}

int main(void) {

    while( cin >> n ){
        mp[0] = n + 1;
        devNum(n, 1);
        cout << count << " ";
        count = 0;
    }

  return 0;
}
/*
Задача 3b. [1.3.4, стр. 87, devnum3.c]
Да се намерят всички разбивания на дадена сума в лева на банкноти (200, 100, 50, 20, 10, 5, 2 лева).

Вход:
Задава се редица цели положителни числа (< 10000 лева) - дадените суми.

Изход:
За всеки елемент на редицата се извежда число - броят на всички възможни разбивания.

Пример:
25 11 10

Решение на примера:
7 1 3

Обосновка: 20+5, 10+10+5, 10+5+5+5, 5+5+5+5+5, 10+5+2+2+2+2+2, 5+5+5+2+2+2+2+2, 5+2+2+2+2+2+2+2+2+2+2
*/