Trò chơi 2048

Điểm: 2,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Bạn có một multiset $s$ gồm $n$ số nguyên, trong đó mỗi phần tử là một lũy thừa của $2$ .

Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy ý (kể cả không lần nào): chọn hai phần tử bằng nhau trong $s$ , xóa cả hai khỏi $s$ và thêm vào $s$ một phần tử mới có giá trị bằng tổng của chúng.

Ví dụ, nếu $s = {1, 2, 1, 1, 4, 2, 2}$ và bạn chọn hai số $2$ và $2$ , thì $s$ trở thành ${1, 1, 1, 4, 4, 2}$ .

Bạn thắng nếu trong $s$ xuất hiện số $2048$ . Hãy xác định xem bạn có thể thắng được hay không.

Có $q$ truy vấn độc lập, mỗi truy vấn cho một multiset $s$ .

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $q$ — số truy vấn.
Với mỗi truy vấn:
- Dòng thứ nhất chứa một số nguyên $n$ — số phần tử của multiset.
- Dòng thứ hai chứa $n$ số nguyên $s_{1}, s_{2}, \dots, s_{n}$ — các phần tử của multiset. Đảm bảo mỗi $s_{i}$ là một lũy thừa của $2$ .

Dữ liệu ra

Với mỗi truy vấn, in ra YES nếu có thể thu được số $2048$ , ngược lại in ra NO. Phân biệt hoa-thường không quan trọng.

Ràng buộc

$1 \leq q \leq 100$
$1 \leq n \leq 100$
$1 \leq s_{i} \leq 2^{29}$
Mỗi $s_{i}$ là một lũy thừa của $2$ .

Ví dụ

Input	Output	Giải thích
6 4 1024 512 64 512 1 2048 3 64 512 2 2 4096 4 7 2048 2 2048 2048 2048 2048 2048 2 2048 4096	YES YES NO NO YES YES	Truy vấn 1: gộp 512+512=1024, rồi 1024+1024=2048. Truy vấn 2: đã có sẵn 2048. Truy vấn 3: tổng các phần tử nhỏ hơn 2048 chỉ là 578, không đủ. Truy vấn 4: 4096 không thể tách thành 2048, và 4 thì quá nhỏ. Truy vấn 5: đã có sẵn 2048. Truy vấn 6: đã có sẵn 2048.
1 3 1024 1024 1	YES	Gộp 1024 + 1024 = 2048.

Bình luận

Không có bình luận tại thời điểm này.