QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#21240. 牛が嫌う音楽

Statistics

牛はあらゆる音楽が好きです。正確にはほぼ全てです。偉大な牛の作曲家 Wolfgang Amadeus Moozart は、ある和音で牛がひどく気分を悪くすることを発見しました。「反芻七の和音」と呼ばれ、牛の楽曲では通常避けられます。

Farmer John は牛の音楽史の細部を知らず、牛舎のスピーカーで好きな曲を流します。牛がどれほど気分を悪くするか推定するため、全ての反芻七の和音を見つけてください。

曲は $N$ 音、$1 \le N \le 20,000$ で、各音は $1..88$ の整数です。和音は相異なる $C$ 音、$1 \le C \le 10$ で指定され、音も $1..88$ の整数です。全音を同じ量だけ上下する移調や並べ替えでも同じ種類の和音です!$4,6,7$ が該当するなら、$3,5,6$($-1$ 移調)、$6,8,9$($+2$ 移調)、$6,4,7$(並べ替え)、$5,3,6$(両方)も該当します。

条件を満たす連続 $C$ 音が反芻七の和音です。開始位置で一意に決まります。全ての開始位置の添字を求めてください。

入力

  • $1$ 行目:整数 $N$。

  • $2..1+N$ 行目:曲の $N$ 音を一行に一つ。

  • $2+N$ 行目:整数 $C$。

  • $3+N..2+N+C$ 行目:和音の例の $C$ 音。全ての移調および/または並べ替えも該当します。

出力

  • $1$ 行目:和音の出現数 $K$。出現は互いに重なっても構いません。

  • $2..1+K$ 行目:各行に開始添字($1$ は最初の音、$N$ は最後の音)。昇順で出力します。

入出力例

入力 1

6
1
8
5
7
9
10
3
4
6
7

出力 1

2
2
4

注記

曲は $1,8,5,7,9,10$ で、和音は $4,6,7$ の移調や並べ替えです。

二つの和音があり、一音重なります。最初は添字 $2$ の $8,5,7$($+1$ 移調と並べ替え)、次は添字 $4$ の $7,9,10$($+3$ 移調)です。

問題作成者:Rob Seay

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.