Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PLAGIO - Plágio musical

As notas musicais são unidades básicas da música ocidental tradicional. Cada nota está associada a uma frequência. Duas notas musicais cujas frequêcias fundamentais tenham uma relação de potência de 2 (uma metade da outra, uma duas vezes a outra, etc.) são percebidas como muito similar. Por isso, todas as notas com esse tipo de relação recebem o mesmo nome, como descrito a seguir.

Há doze notas básicas, em uma sequência crescente de frequências, cada nota separada da anterior por uma mesma distância na escala musical (essa distância é chamada de meio-tom). Sete dessas doze notas são representadas por letras do alfabeto (A, B, C, D, E, F e G). A tabela abaixo mostra a distância, em meio-tons, entre essas notas.

Notas A-B B-C C-D D-E E-F F-G G-A
Número de meios-tons 2 1 2 2 1 2 2

Note que há cinco notas que não são representadas pelas letras do alfabeto: as que estão entre A e B, entre C e D, entre D e E, entre F e G e entre G e A.

As notas podem ser modificadas por duas alterações cromáticas: sustenido e bemol, representadas respectivamente pelos símbolos ‘#’ e ‘b’. Sustenido altera a nota em meio tom para cima, e bemol altera a nota em meio tom para baixo. Uma nota com alteração cromática é denotada pelo nome da nota seguida pelo símbolo da alteração. Note que com esse esquema conseguimos representar todas as doze notas.

A figura abaixo ilustra o nome das notas, segundo o esquema descrito acima, em um trecho de teclado de piano.

 

 

Uma melodia pode ser representada por uma sequência de notas musicais. Por exemplo,

A   A   D   C#   C#   D   E   E   E   F#   A   D   G#   A

é uma melodia muito conhecida. Note no entanto que, como as distâncias entre os meios-tons são sempre iguais, a mesma melodia pode ser escrita iniciando em outra nota (dizemos que a melodia está em outro tom):

B   B   E   D#   D#   E   Gb   Gb   Gb   G#   B   E   A#   B

Sua vizinha é uma famosa compositora que suspeita que tenham plagiado uma de suas músicas. Ela pediu a sua ajuda para escrever um programa que, dada a sequência de notas da melodia de sua música, e a sequência de notas de um trecho de melodia suspeito, verifique se o trecho supeito ocorre, em algum tom, na música dada.

Entrada

A entrada é composta por vários casos de teste. A primeira linha de um caso de teste contém dois inteiros M e T (1 ≤ M ≤ 100000, 1 ≤ T ≤ 10000, TM ), indicando respectivamente o número de notas da música e do trecho suspeito de ter sido plagiado. As duas linhas seguintes contém M e T notas, respectivamente, indicando as notas da música e do trecho suspeito.

As notas em cada linha são separadas por espaço; cada nota é uma dentre ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’ ou ‘G’, possivelmente seguida de um modificador: ‘#’ para um sustenido ou ‘b’ para um bemol.

O último caso de teste é seguido por uma linha que conté m apenas dois números zero separados por um espaço em branco.

Saída

Para cada caso de teste, imprima uma única linha contendo um caractere: ‘S’ caso o trecho realmente tenha sido plagiado pela música ou ‘N’ caso contrário.

Exemplo

Entrada:
16 4
D G A B C D G G G C D E F# G C C
G G C D
12 2
C C# D D# E F F# G G# A A# B
C D
12 2
C Db D Eb E F Gb G Ab A Bb B
C D
4 3
C E G Bb
D F# A
0 0

Saída:
S
N
N
S


Adicionado por:Wanderley Guimarăes
Data:2011-02-12
Tempo limite:1.134s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2010

hide comments
2014-10-05 02:19:44 Wensttay
Fiz essa merda em JAVA em PYTHON e ambos dăo tempo limite T_T


Last edit: 2014-10-07 21:11:00
2012-10-03 18:01:14 Cristhian Bonilha
A entrada faz todo sentido Thiago, visto que săo 16 notas da melodia original e 4 notas da melodia a ser comparada.
2012-04-06 13:18:37 Thiago Otero de Sousa
Essa primeira entrada ficou sem sentido.
2011-12-18 14:44:08 Fernando Fonseca [ITA]
Năo, nenhuma das sequęncias do problema é considerada circular.
2011-07-09 20:25:11 Nilson Felipe [UFV]
A sequęncia é circular?
2011-05-13 13:41:59 Rodrigo Félix [UEPG]
A última entrada é plagio pois C E G um tom acima é D F# A
2011-02-16 12:09:39 Luckas
Como a ultima entrada da com resposta SIM?
Onde de C E G Bb tem D F# A ? A resposta esta errada entao?
2011-02-15 20:59:37 Rômulo
Se năo disser de qual oitava é a nota, o problema sempre permite um NĂO como resposta !
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.