Phần tử quan trọng

Điểm: 800

Thời gian: 1.5s

PyPy3 3.0s

Python 3.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Cho một dãy số nguyên $a$ gồm $n$ phần tử và một số nguyên dương $k$ . Một phần tử $a_i$ được gọi là quan trọng khi và chỉ khi tồn tại một tập các phần tử của dãy $a$ (giá trị có thể trùng nhau nhưng vị trí bắt buộc phải khác nhau) có chứa phần tử $a_i$ sao cho tổng các giá trị trong tập này lớn hơn hoặc bằng $k$ , nhưng khi bỏ đi số $a_i$ thì tổng các số lại nhỏ hơn $k$ . Hãy xác định xem mỗi phần tử trong dãy $a$ có quan trọng hay không.

Input, Output và Subtasks:

Input:

Dòng đầu tiên chứa hai số nguyên dương.
Dòng tiếp theo chức $n$ số nguyên dương của dãy $a$ .

Output:

In ra một dãy nhị phân độ dài $n$ , bit thứ $i$ là $0$ nếu phần tử thứ $i$ không quan trọng và ngược lại.

Subtasks:

$n,k\leq 5.10^4,a_i\leq 10^9$ với mọi testcase.

Sample:

Input:

4 10 
4 1 6 2

Output:

Notes:

Tồn tại tập { $4,6$ } có tổng lớn hơn hoặc bằng $10$ , nhưng khi bỏ một trong hai phần tử đó đi thì tổng sẽ nhỏ hơn $10$ , vậy phần tử thứ $1$ và $3$ là quan trọng.
Với các phần tử $1$ và $2$ , để có được một tập có tổng lớn hơn hoặc bằng $10$ , tập đó phải có cả phần tử $4$ và $6$ , nên khi bỏ đi phần tử thứ $1$ hoặc $2$ thì tổng vẫn lớn hơn hoặc bằng $10$ . Vậy phần tử thứ $2$ và $4$ là không quan trọng.

Bình luận

Không có bình luận nào.