Những người hâm mộ trà sữa
Đề bài
Mô tả
Hạnh là một tín đồ của trà sữa, thức uống thơm ngon nổi tiếng ở các nước châu Á! Vì vậy, tất cả học sinh của thầy cũng rất thích loại đồ uống này.
Một ngày nọ, thầy Hạnh tổ chức một bữa tiệc trà sữa và mời tất cả học sinh. Có học sinh tham dự. Ban đầu, thầy yêu cầu các em đứng thành một hàng và đánh số từ đến từ trái sang phải.
Mỗi học sinh có đúng một thương hiệu trà sữa yêu thích, tức là quán trà sữa em thích nhất. Sau đó thầy Hạnh đến chỗ một số học sinh và hỏi cùng một câu: "Trong phòng này có bao nhiêu học sinh (tính cả em) có cùng thương hiệu yêu thích với em?". Thầy chỉ hỏi một số em, không hỏi tất cả. Mọi học sinh được hỏi đều trả lời đúng.
Sau khi hỏi và nhận câu trả lời, thầy Hạnh tự hỏi: liệu có thể suy ra câu trả lời của tất cả các học sinh không được hỏi hay không? Thầy biết chắc một điều về học sinh của mình: các học sinh có cùng thương hiệu yêu thích luôn đứng cạnh nhau. Nói cách khác, nếu học sinh thứ và học sinh thứ thích cùng một thương hiệu thì mọi học sinh thứ với cũng thích thương hiệu đó.
Hãy giúp thầy Hạnh trả lời câu hỏi này.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên () là số học sinh tham dự bữa tiệc.
Dòng thứ hai chứa số nguyên () là thông tin về các học sinh. Nếu thì học sinh thứ không được hỏi, ngược lại là câu trả lời của em.
Dữ liệu đảm bảo nhất quán, tức là tồn tại ít nhất một tình huống mà mọi câu trả lời của học sinh đều đúng.
Dữ liệu ra
In ra YES nếu thầy Hạnh có thể suy ra câu trả lời của tất cả học sinh một cách chính xác và duy nhất, ngược lại in ra NO.
Ràng buộc
- .
- .
- Dữ liệu nhất quán.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 3 0 0 0 4 0 0 |
YES | Học sinh thứ nhất nói có học sinh cùng thương hiệu với mình, đó phải là học sinh , , (vì những người cùng thương hiệu đứng cạnh nhau). Do đó học sinh cùng thương hiệu với học sinh thứ năm phải là học sinh đến . Dãy câu trả lời duy nhất có thể (nếu hỏi tất cả) là . |
| 4 1 0 0 1 |
NO | Học sinh thứ hai chắc chắn không cùng thương hiệu với học sinh thứ nhất, học sinh thứ ba không cùng thương hiệu với học sinh cuối. Nhưng không biết học sinh thứ hai và thứ ba có cùng thương hiệu hay không, nên có hai dãy câu trả lời: và . |
Bình luận