Cho một dãy số bậc. Dùng định lý Erdős–Gallai để kiểm tra xem dãy đó có thể là dãy bậc của một đồ thị đơn vô hướng hay không: tổng bậc chẵn VÀ với mọi k, sum_{i=1..k} d_i ≤ k(k-1) + sum_{i=k+1..n} min(d_i, k) (sau khi sắp giảm dần).
Dòng 1: n. Dòng 2: n số bậc.
1 ≤ n ≤ 1000, 0 ≤ d_i < n.
YES nếu dãy đồ thị hóa được, ngược lại NO.
Ví dụ:
Đầu vào:
4
3 3 3 3
Đầu ra:
YES
Giải thích:
Đang tải editor...