Read the editorial only when you are stuck, and do not copy code from it. Please respect the problem author and the editorialist: submitting an official solution before solving the problem yourself is a bannable offence.
Gọi ~liters_i~ là số lít nước hiện có trong lọ thứ ~i~. Ban đầu, ~liters_i=1~ với mọi ~1 \le i \le N~.
Gọi ~red_i~ là khả năng có phần nước màu đỏ của lọ thứ ~i~ (~red_i=True~ nếu lọ thứ ~i~ có phần nước màu đỏ và ngược lại). Ban đầu, ~red_1=True~ và ~red_i=False~ với mọi ~2 \le i \le N~.
Với mỗi thao tác, ta tiến hành cập nhật các giá trị ~liters_i~ và ~red_i~ như sau:
~liters_x=liters_x-1~, ~liters_y=liters_y+1~
Nếu ~red_x=True~ (lọ thứ ~x~ trước khi thực hiện thao tác đã có một phần nước màu đỏ) thì ta cập nhật ~red_y=True~
Nếu ~liters_x=0~ (lọ thứ ~x~ sau thao tác này không còn lượng nước nào) thì ta cập nhật ~red_x=False~
Kết quả của bài toán là số chỉ số ~i~ thỏa mãn ~red_i=True~.
Độ phức tạp: ~O(N+M)~
Comments
You need to sign in to write comments, reply and vote.
,
(lọ thứ
trước khi thực hiện thao tác đã có một phần nước màu đỏ) thì ta cập nhật
(lọ thứ
Comments