INFOMAN брой 20

/* Input data is: N A B
 20 15 15


			       Кутии
			      -------

    В една редица  са наредени N кутии (1<=N<=20). Разполагаме с А броя
 червени топчета и  В  броя сини (0<=А<=15, 0<=B<=15). Червените, както
 и сините топчета, са неразличими помежду си. Топчетата  могат  да  се
 поставят в кутиите. Разрешено е в една кутия да се поставят по няколко
 топчета от  двата вида или само от единия вид. Възможно е някои  кутии
 да остават празни. Не  е задължително всичките топчета да се  поставят
 в кутиите. Съставете програма  която намира по колко  различни  начина
 може да се осъществи описаното поставяне нa топчетата в кутиите.

 РЕШЕНИЕ:

    Поставената задача изисква преброяването на някакви комбинаторни
 конфигурации което обикновено не може да бъде извършено с генерирането
 на всички възможности поради  времевото ограничение. Тогава можем  да
 дефинираме функция която ни дава броя  на различните поставяния  на  А
 червени топчета и B сини топчета в N кутии по гореописания начин:

		  A   B
      F(N,A,B) =  ä   ä  F(N-1,A-i,B-j)
		 i=0 j=0
      F(0,A,B) = 1

 Верността на функцията е очевидна. На всяка стъпка тя избира колко от
 червените топчета да постави в кутията N (i броя), и колко от сините
 топчета да постави в същата кутия (j броя). Броя на поставянията се
 получава като сума от различните поставяния на всяка стъпка. Разбира се
 рекурсивна функция изчисляваща функцията F би била прекалено бавна.
 Затова можем да използваме динамично оптимиране и да пазим в таблица
 стойността на функцията. Тази стойност запазваме веднага след като сме
 изчислили стойността на функцията при определени три параметъра. Когато
 повторно ни се наложи да изчисляваме функцията при тези три параметъра
 стойнотта можем да вземем от таблицата, защото тази стойност вече я имаме.
 Сложността на алгоритъма за изброяване е O(N*A*B),
 защото всяка стойност на функцията се изчислява само веднъж, а броя на
 различните параметри N, A и B, които можем да предадем на функцията е
 N*A*B. Самото изчисляване е реализирано с рекурсивна функция, но може
 да се направи и итеративно.
   Важно е да се забележи, че стандартния тип int, не може да "побере"
 отговора на задачата. Затова е нужно да си реализираме собствени функции
 за работа с дълги числа. Те разбира се е нужно да поддържат само
 най-простата операция - събиране. Реализацията и е по-стандартния начин
 за събиране на две числа, с пазене на пренос и намиране на текуща цифра
 на сбора. Възможността за предефиниране на оператори в С++, ни предоставя
 много удобен начин за реализиране на дългите числа, при коeто синтаксиса
 за работа с тях не се различава от синтаксиса за работа с обикновения тип
 int например.

Petko Minkov
*/
#include <fstream.h>
#include <string.h>

#define MAXD 25
#define MAXN 21
#define MAXAB 16
#define max(a, b) ((a) > (b) ? (a) : (b))

class large {
  public:
    int  dc; // брой на цифрите
    char d[MAXD]; // самите цифри

    large();
    large(int);
    large operator +(large);
    void writeln();
};

large::large()
{
   memset(d, 0, sizeof(d));
   dc = 0;
}

large::large(int val)
{
   memset(d, 0, sizeof(d));
   dc = 0;
   while(val)
   {
      d[++dc] = val % 10;
      val /= 10;
   }
}

large large::operator +(large b)
{
   int   i, carry, v;
   large res;

   carry = 0;
   for(i=1;i<=max(b.dc, dc);i++)
   {
      v = d[i] + b.d[i] + carry;
      res.d[++res.dc] = v % 10;
      carry = v / 10;
   }

   if(carry)
     res.d[++res.dc] = carry;

   return res;
}

void large::writeln()
{
   int i;

   for(i=dc;i>=1;i--)
     cout << int(d[i]);
   cout << endl;
}

/* program data */

int   n, a, b;
large t[MAXN][MAXAB][MAXAB];

void readdata()
{
   ifstream fin("boxes.cpp");
   fin.ignore(80, '\n');

   fin >> n >> a >> b;
   fin.close();
}

large calc(int n, int a, int b)
{
   int   i, j;
   large sum;

   if(n == 0)
     return 1;

   if(t[n][a][b].dc)
     return t[n][a][b];

   for(i=0;i<=a;i++)
     for(j=0;j<=b;j++)
       sum = sum + calc(n - 1, a - i, b - j);

   t[n][a][b] = sum;
   return sum;
}

void main()
{
   readdata();
   calc(n, a, b).writeln();
}