INFOMAN брой 20

/* Input is: N M; l1..ln; L1..Lm
  5 2
  4
  10
  2
  5
  3
  11
  13
				   КОРАБИ
				  --------

   Военното разузнаване на една държава съобщило, че всичките N (N < 100)
 бойни кораби на съседна вражеска държава са се събрали и са се
 разположили там в M пристанища (1 < M < 10), номерирани с числата от
 1 до М, като във всяко пристанище има поне един кораб. На разузнаването са
 известни дължините l1, l2, ... , ln на корабите - различни цели положителни
 числа в интервала от 1 до 100, но би му се искало да знае и в кое пристанище,
 кои кораби са разположени. За съжаление разузнавателната подводница, която
 е правила наблюдението може да съобщи само сумите от дължините на корабите
 L1, L2, ... Lm във всяка едно от пристанищата.
   Да се  намери поне едно възможно разпределение на корабите по пристанища.
 Като резултат програмата трябва да представя намерените редици от кораби,
 изведвайки броя на корабите в определена редица, след коет извежда и
 дължините на корабите в тази редица.

 РЕШЕНИЕ:

   Задачата наподобява задачата за раницата, но не може да бъде решена
 с динамично оптимиране с използването на достатъчно малко памет, поради
 това, че раниците (в случая пристанища) са прекалено много.

   Как тогава можем да я решим? Очевидно ще се прилага някакъв алгоритъм
 с пълно изчерпване и генериране на всички възможности. При намиране на
 едно решение програмата прекратява изпълнението си (което не бива да ни
 успокоява, защото даже и едно решение може да се намери достатъчно бавно).
 При изпълнението на алгоритъма с пълно изчерпване запълваме последователно
 пристанищата едно по едно с кораби. На всяка стъпка определяме кои кораб
 да сложим в пристанището което текущо запълваме. Естествено не можем да
 слагаме кораб които вече сме използвали (именно за това си пазим в един
 масив used, дали даден кораб е използван). Освен това не можем да слагаме
 кораб с които ще надишим капацитета на пристанището. Започваме да запълваме
 следващо пристанище когато текущото е запълнено точно до краен капацитет.
 Много важно при подобни алгоритми е да не повтаряме в гененрирането дадена
 конфигурация. Тъй като реда по-които запълваме пристанищата няма значение
 то ги запълваме от 1-то към М-тото. Освен това реда на корабите в дадено
 пристанище няма значение, затова избираме корабите в едно пристанище да
 се вкарват така, че един кораб не може в пристанището да е преди друг,
 ако във входната последователност е след него.
   Съществено е да се забележи, че бързодействието на програмата зависи от
 конкретния вход (не само от големината на N и M). Например вход съставен
 от произволни числа бива решен мигновено. Но внимателно подбрани входни
 данни могат да забавят значително програмата. Затова идеята е да проверим
 колкото се може повече пермутации на входните данни с надеждата, че някоя
 от тях ще бъде решена достатъчно бързо.
   Конкретно, за всяка последователност която решаваме, пускаме рекурсия
 по например 0.1 секунди. Важно е да се проверят и сортираните в нарастващ
 и намаляващ ред входни последователности. След проверяването на оригиналната
 входна последователност и двата вида сортирани последователности генерираме
 произволни пермутации докато задачата бъде решена.

Petko Minkov
*/
#include <fstream.h>
#include <time.h>
#include <stdlib.h>
#include <process.h>

#define MAXN 100
#define MAXM 10

int blen[MAXN], plen[MAXN];
int n, m, runs;
int used[MAXN];
int pristan[MAXN];

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

   fin >> n >> m;
   for(i=1;i<=n;i++)
     fin >> blen[i];

   for(i=1;i<=m;i++)
     fin >> plen[i];

   fin.close();
}

void writesol()
{
   int i, j, count;

   for(i=1;i<=m;i++)
   {
      count = 0;
      for(j=1;j<=n;j++)
	if(pristan[j] == i)
	  count++;

      cout << count << endl;
      for(j=1;j<=n;j++)
	if(pristan[j] == i)
	  cout << blen[j] << " ";
      cout << endl;
   }

   exit(0); // halt
}

void order(int npos, int mpos, int curlen)
{
   int i;

   /* Проверява дали времето не е надхвърлило разрешеното
      за текущия опит за подреждане */
   if(clock() / CLK_TCK > runs * 0.1)
     return;

   if(mpos == m + 1)
     writesol();

   for(i=npos;i<=n;i++)
     if(!used[i] && curlen + blen[i] <= plen[mpos])
     {
	used[i] = 1;
	pristan[i] = mpos;
	/* дали да почваме да запълваме следващото пристанище? */
	if(curlen + blen[i] == plen[mpos])
	  order(1, mpos + 1, 0);
	else
	  order(npos + 1, mpos, curlen + blen[i]);
	used[i] = 0;
     }
}

void swap(int &a, int &b)
{
   int tmp = a; a = b; b = tmp;
}

void sort_ascending()
{
   int tmp, i, j;

   for(i=1;i<=n;i++)
     for(j=i+1;j<=n;j++)
       if(blen[i] > blen[j])
	 swap(blen[i], blen[j]);
}

void sort_descending()
{
   int tmp, i, j;

   for(i=1;i<=n;i++)
     for(j=i+1;j<=n;j++)
       if(blen[i] < blen[j])
	 swap(blen[i], blen[j]);
}

void randperm()
{
   int i;

   for(i=1;i<=n;i++)
     swap(blen[i], blen[random(n)+1]);
}

void solve()
{
   // process original sequence
   runs++;
   order(1, 1, 0);

   // process sorted sequences
   sort_ascending();
   runs++;
   order(1, 1, 0);

   sort_descending();
   runs++;
   order(1, 1, 0);

   // generate random permutations
   while(1)
   {
      randperm();
      runs++;
      order(1, 1, 0);
   }
}

void main()
{
   readdata();
   randomize();
   solve();
}