#include <stdio.h>

#define MAXP 10//最大進(jìn)程數(shù)
#define MAXR 10//最大資源種類數(shù)

int NUMP,NUMR;//進(jìn)程數(shù)目和資源數(shù)目

void Safe(int * Available, int Max[MAXP][MAXR], int Alloc[MAXP][MAXR]);//安全算法
bool LE(int * a, int * b, int len);//判斷向量a小于等于向量b

int main()
{
	int	Max[MAXP][MAXR];//= {{3,2,2},{6,1,3},{3,1,4},{4,2,2}};//每一進(jìn)程需要每一資源最大數(shù)
	int Alloc[MAXP][MAXR];//= {{1,0,0},{6,1,2},{2,1,1},{0,0,2}};//每一進(jìn)程已經(jīng)得到每一資源數(shù)
	int Available[MAXR];//= {0,1,0};//系統(tǒng)中未分配給進(jìn)程的每種資源總量3
	int i, j;

	printf("input the amount of porcess and resource:\n");
	scanf("%d %d", &NUMP, &NUMR);

	printf("請輸入每一資源還可使用數(shù):\n");
	for(j = 0; j < NUMR; j++)//輸入每一資源還可使用數(shù)
		scanf("%d", &Available[j]);

	printf("請輸入進(jìn)程第一資源最大數(shù):\n");
	for(i = 0; i < NUMP; i++)//輸入進(jìn)程第一資源最大數(shù)
		for(j = 0; j < NUMR; j++)
			scanf("%d", &Max[i][j]);

	printf("請輸入進(jìn)程已擁有每一資源數(shù):\n");
	for(i = 0; i < NUMP; i++)//輸入進(jìn)程已擁有每一資源數(shù)
		for(j = 0; j < NUMR; j++)
			scanf("%d", &Alloc[i][j]);
		
	Safe(Available, Max, Alloc);

	return 0;
}

void Safe(int * Available, int Max[MAXP][MAXR], int Alloc[MAXP][MAXR])
{
	int CurrentAvail[MAXR];
	int Need[MAXR];
	int Process[MAXP], pointer = 0;//記錄進(jìn)程的完成順序
	bool Finish[MAXP];//記錄進(jìn)程i是否順利完成
	int i,j;

	for(i = 0; i < NUMR; i++)
		CurrentAvail[i] = Available[i];
	for(i = 0; i < NUMP; i++)
		Finish[i] = false;

	for(i = 0; i < NUMP; i++)
	{
		for(j = 0; j < NUMR; j++)//計(jì)算進(jìn)程i需要資源數(shù)
			Need[j] = Max[i][j] - Alloc[i][j];

		if( LE(Need, CurrentAvail, NUMR) && Finish[i] == false )
		{//可用資源可滿足進(jìn)程需要的資源
			for(j = 0 ; j < NUMR; j++)//完成進(jìn)程i后計(jì)算可用資源
				CurrentAvail[j] += Alloc[i][j];
			Finish[i] = true;
			Process[pointer] = i;
			pointer++;
			i = -1;
		}
	}

	for(i = 0; i < NUMP; i++)
		if( Finish[i] == false )
		{//進(jìn)程沒用全部完成,則不安全
			printf("unsafe\n");
			return ;
		}

	printf("safe: ");//進(jìn)程全部順利完成,安全
	for(i = 0; i < NUMP; i++)//輸出進(jìn)程完成順序
		printf("p%d ", Process[i]+1);
	printf("\n");
}

bool LE(int * a, int * b, int len)
{//判斷長度為len的向量a小于等于b
	for(int i = 0; i < len; i++)
		if(a[i] > b[i])
			return false;
	return true;
}