Editorial for Pha chế

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Gọi $liters_i$ ~liters_i~ là số lít nước hiện có trong lọ thứ $i$ ~i~. Ban đầu, $liters_i=1$ ~liters_i=1~ với mọi $1 \le i \le N$ ~1 \le i \le N~.

Gọi $red_i$ ~red_i~ là khả năng có phần nước màu đỏ của lọ thứ $i$ ~i~ ( $red_i=True$ ~red_i=True~ nếu lọ thứ $i$ ~i~ có phần nước màu đỏ và ngược lại). Ban đầu, $red_1=True$ ~red_1=True~ và $red_i=False$ ~red_i=False~ với mọi $2 \le i \le N$ ~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$ ~liters_i~ và $red_i$ ~red_i~ như sau:

$liters_x=liters_x-1$ ~liters_x=liters_x-1~, $liters_y=liters_y+1$ ~liters_y=liters_y+1~
Nếu $red_x=True$ ~red_x=True~ (lọ thứ $x$ ~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$ ~red_y=True~
Nếu $liters_x=0$ ~liters_x=0~ (lọ thứ $x$ ~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$ ~red_x=False~

Kết quả của bài toán là số chỉ số $i$ ~i~ thỏa mãn $red_i=True$ ~red_i=True~.

Độ phức tạp: $O(N+M)$ ~O(N+M)~

Editorial for Pha chế

Comments