trang chủ / đề bài / icpc22_mb_k

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ó n 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ừ 1 đến 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ứ i và học sinh thứ j thích cùng một thương hiệu thì mọi học sinh thứ k với i≤k≤j 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 n (1≤n≤100) là số học sinh tham dự bữa tiệc.

Dòng thứ hai chứa n số nguyên a1,a2,…,an (0≤ai≤n) là thông tin về các học sinh. Nếu ai=0 thì học sinh thứ i không được hỏi, ngược lại ai 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

  • 1≤n≤100.
  • 0≤ai≤n.
  • 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ó 3 học sinh cùng thương hiệu với mình, đó phải là học sinh 1, 2, 3 (vì những người cùng thương hiệu đứng cạnh nhau). Do đó 4 học sinh cùng thương hiệu với học sinh thứ năm phải là học sinh 4 đến 7. Dãy câu trả lời duy nhất có thể (nếu hỏi tất cả) là 3,3,3,4,4,4,4.
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: 1,1,1,1 và 1,2,2,1.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0