QOJ.ac

QOJ

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

#21240. Música que adoece

Statistics

As vacas adoram toda a música, quase toda: o grande compositor bovino Wolfgang Amadeus Moozart descobriu um acorde que as deixa doentes. Por isso o acorde de sétima ruminante costuma ser evitado nas suas composições.

Farmer John não conhece os pormenores da história musical bovina e toca a música favorita nos altifalantes do estábulo. Identifique todos esses acordes para estimar quanto as vacas adoecerão.

A música tem $N$ notas, $1 \le N \le 20,000$, inteiras em $1..88$. O acorde tem $C$ notas distintas, $1 \le C \le 10$, também em $1..88$. Transpor (aumentar ou diminuir todas pela mesma quantidade) ou reordenar mantém o acorde. Se $4,6,7$ serve, servem $3,5,6$ (transposição $-1$), $6,8,9$ ($+2$), $6,4,7$ (reordenação), $5,3,6$ (ambas).

O acorde é uma sequência de $C$ notas consecutivas que cumpre os critérios, determinada pelo início. Encontre todos os índices iniciais.

Entrada

  • Linha $1$: inteiro $N$.

  • Linhas $2..1+N$: as $N$ notas, uma por linha.

  • Linha $2+N$: inteiro $C$.

  • Linhas $3+N..2+N+C$: as $C$ notas de um acorde de exemplo. Toda transposição e/ou reordenação também serve.

Saída

  • Linha $1$: número $K$ de acordes presentes. Ocorrências podem sobrepor-se.

  • Linhas $2..1+K$: um índice inicial por linha ($1$ é a primeira nota, $N$ a última), em ordem crescente.

Exemplos

Entrada 1

6
1
8
5
7
9
10
3
4
6
7

Saída 1

2
2
4

Nota

A música é $1,8,5,7,9,10$. O acorde é uma transposição ou reordenação de $4,6,7$.

Há dois acordes, sobrepostos numa nota: $8,5,7$ (transposto $+1$ e reordenado) começa em $2$; $7,9,10$ (transposto $+3$) começa em $4$.

Autor do problema: 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.