/**
 * www.algorytm.org
 * algorytm testowania czy podany ciąg 
 * stopni wierzcholków grafów jest graficzny
 * Tomasz Lubiński (c)2005
 */
public class Graficzny2 {

	private static int c[];

	//sortuje ciąg nierosnąco
	private static void sort(int c[], int n) {
		int j,k;
		int flag;
		
		flag=1;
		while (flag==1) {
			flag=0;
	        for (j=0; j<n-1; j++)
	        	if (c[j]<c[j+1]) {
	        		k=c[j];
	        		c[j]=c[j+1];
	        		c[j+1]=k;
	        		flag=1;
	        	}
		}
	}

	public static void main(String[] args) {

		int graficzny;
		int n,i,s;
		
		//pobierz dane
		System.out.println("Podaj liczbe wierzcholkow grafu");
		n = Console.readInt("?");
		c = new int[n];
		for (i=0; i<n; i++) {
			c[i] = Console.readInt("Podaj stopien wierzcholka " + (i+1));
        }
		
		//algorytm testowania czy podany ciąg stopni wierzcholkow jest graficzny
		graficzny=1;
		
		//sprawdz czy suma ciągu jest liczbą parzystą
		s=0;
		for (i=0; i<n; i++) 
			s+=c[i];
		if ((s%2)!=0) 
			graficzny=0;
		else 
			sort(c,n); //posortuj ciąg nierosnąco jeżeli suma jest liczbą parzystą
		while ((c[0]!=0) && (graficzny==1)) {
			s=0;
			for (i=1; i<n; i++)
				if (c[i]!=0) 
					s++;
			if (c[0]>s) 
				graficzny=0;
			else 
				for (i=1; i<=c[0]; i++) 
					c[i]--;
			c[0]=0;
			sort(c,n);
		}
		
		//podaj użytkownikowi wynik
		if (graficzny == 1) 
			System.out.println("Podany ciąg jest graficzny");
		else 
			System.out.println("Podany ciąg nie jest graficzny");
	}
}