/**
 * www.algorytm.org
 * Algorytm Holt'a - detekcja zakleszczenia
 * (c)2005 Tomasz Lubinski
 */

public class AlgorytmHolta {

	public static void main(String[] args) {
		int p,z,j,k,tmp,flaga;
		int E[][][] = new int[2][10][10];
		int A[][] = new int[10][10];
		int f[] = new int[10];
		int I[] = new int[10];
		int c[] = new int[11];
		
		System.out.println("Podaj liczbe procesow (max. 10)");
		p = Console.readInt("?");
		System.out.println("Podaj liczbe zasobow (max. 10)");
		z = Console.readInt("?");
//		pobranie danych
		for (k=0; k<p; k++)
			for (j=0; j<z; j++)
				{
				System.out.println("Podaj ile zasobu "+ (j+1) +" posiada proces "+ (k+1));
				A[k][j] = Console.readInt("?");
				}
		for (k=0; k<p; k++)
			for (j=0; j<z; j++)
				{
				System.out.println("Podaj ile zasobu "+ (j+1) +" moze jeszcze zazadac proces "+ (k+1));
				E[0][k][j] = Console.readInt("?");
				E[1][k][j]=k;
				}
		for (j=0; j<z; j++)
			{
			System.out.println("Podaj ile zasobu "+ (j+1) +" jest jeszcze wolne w systemie");
			f[j] = Console.readInt("?");
			}
//		algorytm Holt'a
//		posortowanie zadan procesow (bubble sort)
		for (j=0; j<z; j++)
			{
			flaga=1;
			while (flaga==1)
				{
				flaga=0;
				for (k=0; k<p-1; k++)
					if (E[0][k][j]>E[0][k+1][j])
						{
						flaga=1;
						tmp=E[0][k][j];
						E[0][k][j]=E[0][k+1][j];
						E[0][k+1][j]=tmp;
						tmp=E[1][k][j];
						E[1][k][j]=E[1][k+1][j];
						E[1][k+1][j]=tmp;
						}
				}
			}
		for (k=0; k<z; k++) I[k]=0;
		for (k=1; k<=p; k++) c[k]=z;
		c[0]=p;
//		wlasciwa częsc algorytmu
		do
		{
		flaga=0;
		for (j=0; j<z; j++)
			while ((I[j]<p)&&(E[0][I[j]][j]<=f[j]))
				{
				c[E[1][I[j]][j]+1]=c[E[1][I[j]][j]+1]-1;
				if (c[E[1][I[j]][j]+1]==0)
					{
					c[0]--;
					flaga=1;
					for (k=0; k<z; k++)
						f[k]=f[k]+A[E[1][I[j]][j]][k];
					}
				I[j]++;
				}
		}while ((flaga==1)&&(c[0]>0));
		if (flaga==1) 
			System.out.println("Nie ma zakleszczenia"); 
		else 
			System.out.println("Istnieje zakleszczenie");
		System.out.print("Zbior zadan zakleszczonych: {");
		for (k=1; k<=p; k++) if (c[k]!=0) System.out.print(" " + k);
		System.out.println(" }");

	}
}