Biến Đổi Cặp Số

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ con bò xếp thành hàng, con thứ $i$ thuộc giống $a_{i}$ . Bác sĩ thú y sẽ khám con bò ở vị trí $i$ chỉ khi nó thuộc giống $b_{i}$ .

FJ thực hiện đúng một thao tác: chọn hai số $l$ và $r$ ( $1 \leq l \leq r \leq N$ ) rồi đảo ngược thứ tự các con bò từ vị trí $l$ đến $r$ .

Với mỗi $c$ từ $0$ đến $N$ , hãy đếm có bao nhiêu thao tác $(l, r)$ phân biệt khiến đúng $c$ con bò được khám.

$N + 1$ dòng, dòng thứ $i$ chứa số thao tác cho kết quả đúng $i - 1$ con bò được khám.

Input	Output	Giải thích
3 1 3 2 3 2 1	3 3 0 0	Các thao tác $(1, 1)$ , $(2, 2)$ , $(3, 3)$ không thay đổi mảng, không con nào khớp $\Rightarrow$ 0 con được khám. Các thao tác $(1, 2)$ , $(2, 3)$ , $(1, 3)$ mỗi cái cho 1 con được khám.
3 1 2 3 1 2 3	0 3 0 3	Ban đầu 3 con đều khớp. Thao tác giữ nguyên $(1, 1)$ , $(2, 2)$ , $(3, 3)$ cho 3 con. Các thao tác đảo ngược cho 1 con.

Bình luận

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