#!/usr/bin/python3 # Řešení úlohy 32-3-2 napsal Martin „Medvěd“ Mareš L.P. 2020 def counting_sort(degrees): """Setřídí posloupnost stupňů, vrací novou posloupnost a indexy prvních výskytů.""" n = len(degrees) counters = [0] * n for d in degrees: counters[d] += 1 degrees = [] first_occ = [None] * n for d in range(n): first_occ[d] = len(degrees) degrees += [d] * counters[d] return degrees, first_occ def graph_exists(degrees): """Zjistí, zda existuje graf se zadanými stupni vrcholů.""" # Triviální kontrola for d in degrees: if d < 0 or d >= len(degrees): return False # Setřídíme stupně degrees, first_occ = counting_sort(degrees) # Opakovaně používáme větu o skóre while len(degrees) > 0: # Momentálně nejvyšší stupeň označíme k k = degrees.pop() if k < 0 or k > len(degrees): return False # Abychom si nepřepisovali seznam first_occ pod rukama, uložíme # si všechny začátky úseků a first_occ aktualizujeme dodatečně. starts = [] # Předchozích k stupňů snížíme o 1 j = len(degrees) while k > 0: # degrees[i:j] bude souvislý úsek délky l obsahující stupeň delta delta = degrees[j-1] i = first_occ[delta] starts.append(i) l = j - i if k >= l: # Snižujeme všechny stupně v úseku for p in range(i, j): degrees[p] -= 1 k -= l else: # Chceme snížit jen některé, tak si vybereme prvních k for p in range(i, i+k): degrees[p] -= 1 starts.append(i+k) # Pozor, vznikl nový úsek k = 0 # Jdeme na další úsek j = i # Aktualizace first_occ pro všechny úseky for i in starts: if i == 0 or degrees[i] != degrees[i-1]: first_occ[degrees[i]] = i return True degrees = list(map(int, input().split())) print(graph_exists(degrees))