Tìm Hợp Âm

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Cho một dãy gồm $N$ nốt nhạc và một mẫu hợp âm gồm $C$ nốt. Một đoạn $C$ nốt liên tiếp trong dãy được gọi là khớp với mẫu hợp âm nếu sau khi sắp xếp cả hai, hiệu tương ứng giữa các nốt bằng nhau (tức là có thể chuyển vị và sắp xếp lại để trùng khớp).

Hãy tìm tất cả các vị trí bắt đầu của đoạn khớp trong dãy.

Dữ liệu vào

Dòng 1: Số nguyên $N$ — số nốt trong dãy
$N$ dòng tiếp theo: Mỗi dòng chứa một số nguyên — giá trị nốt nhạc (từ $1$ đến $88$ )
Dòng tiếp: Số nguyên $C$ — số nốt trong mẫu hợp âm
$C$ dòng tiếp theo: Mỗi dòng chứa một số nguyên — giá trị nốt trong mẫu

Dữ liệu ra

Dòng 1: Số lượng $K$ đoạn khớp tìm được
$K$ dòng tiếp theo: Các vị trí bắt đầu (đánh số từ $1$ ), theo thứ tự tăng dần

Ràng buộc

$1 \leq C \leq 10$
$1 \leq N \leq 20 000$
Giá trị mỗi nốt từ $1$ đến $88$

Ví dụ

Input	Output	Giải thích
6 1 8 5 7 9 10 3 4 6 7	2 2 4	Mẫu ${4, 6, 7}$ khớp với ${8, 5, 7}$ tại vị trí 2 (chuyển vị $+ 1$ ) và ${7, 9, 10}$ tại vị trí 4 (chuyển vị $+ 3$ )

Bình luận

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