Bedao Regular Contest 02 - LEAVES

View as PDF

Submit solution


Points: 0.15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Dưới mái trường, hình ảnh cây bàng, cây phượng đã quá quen thuộc với nhiều thế hệ học sinh, nhưng đối với học sinh chuyên Tin như iostream1308 thì quen thuộc nhất vẫn là cây nhị phân. Tuy rằng iostream1308 không thích thú mấy với việc đếm lá cây bàng, cây phượng nhưng lại rất thích đếm lá cây của cây nhị phân, nhận thấy khả năng trời phú này, thầy giáo đã giao cho iostream một bài tập như sau:

Cho biết số lượng lá và độ cao của các lá trong một cây (coi độ cao của node gốc là ~0~). Hãy xác định ít nhất ~1~ cách tạo nên cây nhị phân đầy đủ. Biết rằng cây nhị phân đầy đủ là cây trong đó mỗi node (không phải node lá) đều có hai node con.

input:

  • Dòng đầu tiên chứa số nguyên ~Q~ ~(1 \leq Q \leq 10)~ là số lượng truy vấn.
  • ~Q~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~ là số lượng lá của cây và ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(1 \leq a_i \leq 10^5)~ là độ cao của ~n~ lá.

output:

  • Ứng với mỗi truy vấn in ra kết quả của truy vấn đó trên một dòng. Nếu có thể tạo được cây nhị phân đầy đủ thì in ra ~YES~, ngược lại in ra ~NO~.

Sample Input:

3
4 2 2 2 2
3 1 2 2
2 1 2

Sample Output

YES
YES
NO

Subtask:

  • ~20\%~ số test có ~1 \leq n \leq 4~.
  • ~80\%~ số test còn lại không có điền kiện gì thêm.

Note

Ở test ví dụ thứ nhất ta được ~2~ cây sau đây:

hình 1

hình 2

Ta thấy rằng ở ~2~ cây này có tồn tại ít nhất ~1~ cây nhị phân đầy đủ nên đáp án là ~YES~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.