Đồng xu

Điểm: 1500

Thời gian: 1.0s

PyPy3 2.0s

Python 2.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 số nguyên dương $n$ và $k$ số nguyên dương $a_1,a_2,\dots,a_k ≤ 2n$ . Người ta bày sẵn $2n$ đồng xu trên bàn sao cho có đúng $n$ đồng xu ngửa và $n$ đồng xu sấp. Với mỗi thao tác, bạn có thể chọn một số bất kỳ trong tập $a$ , giả sử số bạn chọn là $t$ . Bạn sẽ lấy các đồng xu liên tiếp (có thể không lấy đồng xu nào) có cùng trạng thái (cùng sấp hoặc cùng ngửa), sau đó chuyển chúng ra đầu dãy. Ví dụ:
Với trạng thái các đồng xu được đặt như sau: AABBBBAA (ký hiệu A là mặt ngửa và B là mặt sấp) và $t = 4$ , ta có thể thu được các trạng thái sau:

BBBAABAA (chuyển các đồng xu $3, 4, 5$ lên đầu).
BBBBAAAA (chuyển các đồng xu $3, 4, 5, 6$ lên đầu).
...

Hỏi rằng với dãy $a$ đã cho, tồn tại hay không một cách sắp xếp các đồng xu sao cho không thể có trường hợp $n$ đồng xu đầu tiên có cùng một trạng thái sau một số hữu hạn các thao tác?

Input, Output và Subtasks:

Input:

Dòng đầu tiên gồm hai số nguyên dương $n$ và $k$ .
Dòng tiếp theo gồm các số nguyên dương miêu tả dãy $a$ .

Output:

In ra YES nếu tồn tại một cách sắp xếp các đồng xu sao cho không thể khiến $n$ đồng xu đầu tiên có cùng một trạng thái sau một số hữu hạn các thao tác, và NO trong trường hợp ngược lại.

Subtasks:

$n,a_i,k\leq 2.10^6; k,a_i\leq 2n$

Sample:

Input:

4 4
1 2 3 4

Output:

NO

Sample 2:

Input:

4 2
1 2

Output:

YES

Notes:

Tồn tại cách sắp xếp ABABABAB.

Bình luận

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