Problem Name: 2 AD-HOC - beecrowd | 1127

Problem Link:

Musical Plagiarism


Maratona de Programação da SBC Brazil

Timelimit: 1

The musical notes are the basic units of Western music. Each note is associated with a frequency. Two notes for which the fundamental frequencies have a ratio of power of 2 (one is half of the other, one is double of the other, etc..) are perceived as very similar. Therefore, any notes with that kind of relationship are given the same name, as described below.

There are twelve basic notes in a sequence of increasing frequency, each note separated from the previous note by the same distance in the musical scale (this distance is called a semitone). Seven of these twelve notes are represented by letters of the alphabet (A, B, C, D, E, F and G). The table below shows the distance, in semitones, between the notes.

Notice that there are five notes that are not represented by letters of the alphabet: the notes between A and B, between C and D, between D and E, betwen F and G and between G and A.

Notes can be modified by two accidentals, called sharp and flat, represented respectively by the symbols `#' and `b'. A sharp raises the note a semitone, a flat lowers the note a semitone. A note with an accidental is denoted by the name of the note followed by the accidental symbol. Notice that with this scheme we can represent all twelve notes.

The figure below illustrates the name of the notes in accordance with the scheme described above, in a fragment of a piano keyboard.

A melody can be represented by a sequence of notes. For example,

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

is a well known melody. Note however that as the distances between the semitones are always equal, the same melody can be written starting with another note (we say that the melody is in another key):

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

Your neighbor is a famous composer who suspects someone has plagiarized one of her songs. She asked your help to write a program that, given the sequence of notes of the melody in her song, and the sequence of notes of a suspicious snippet of melody, determines if the suspicious snippet occurs, in some key, in her song.




The input consists of several test cases. The first line of a test case contains two integers M and T (1 ≤ M ≤ 100000, 1 ≤ T ≤ 10000, TM ), indicating the number of notes in the song suspected of having been plagiarized and in the suspect snippet. Each of the next two lines contains M and T notes, respectively, indicating the notes of the song and of the suspect snippet.

Notes in each line are separated by one space; each note is one among `A', `B', `C', `D', `E', `F' or `G', possibly followed by an accidental sign: `#' for sharp or `b' for flat.

The last test case is followed by a line containing only two zeros separated by a blank space.




For each test case your program must print a single line containing one character, `S' in case the song has been plagiarized by the text, or `N' in case the song has not been plagiarized by the text.




Input Sample Output Sample

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



Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;
typedef pair < string,string> ss;
map m1;
vector < ss > v;
vector<ss > v2;

int main ()
	string nota;
	string plagio;
	string aux;
	stringstream buf;
	int flag;
	int n;
	int t;
	int lb;
	int ub;
	m1["C#"] = ss("C#", "Db");
	m1["D#"] = ss("D#", "Eb");
	m1["F#"] = ss("F#", "Gb");
	m1["G#"] = ss("G#", "Ab");
	m1["A#"] = ss("A#", "Bb");
	m1["Db"] = ss("C#", "Db");
	m1["Eb"] = ss("D#", "Eb");
	m1["Gb"] = ss("F#", "Gb");
	m1["Ab"] = ss("G#", "Ab");
	m1["Bb"] = ss("A#", "Bb");
	m1["D"] = ss ("D", "D");
	m1["B#"] = ss("C", "B#");
	m1["E"] = ss("E", "Fb");
	m1["E#"] = ss("E#", "F");
	m1["B"] = ss("B", "Cb");
	m1["C"] = ss("C", "B#");
	m1["Fb"] = ss("E", "Fb");
	m1["F"] = ss("E#", "F");
	m1["Cb"] = ss("B", "Cb");
	m1["A"] = ss("A", "A");
	m1["G"] = ss("G", "G");
		cin >> n >> t;
		if (!n && !t) return 0;
		getline(cin, nota);
		buf << nota;
		while(buf >> aux)
		getline(cin, plagio);
		buf << plagio;
		while(buf >> aux)
		flag = 0;
		for (int i = 0, k = 0 ; i  <  t && k < n;)
			ub = k;
			flag = 0;
			while(v[k].first == v2[i].first || v[k].second == v2[i].second)
				if (i >= t)
					flag = 1;	
				if (k >= n)
					flag = 1;	
			if (flag) break;
			k = ub + 1;
			i = 0;
		if (flag) cout << "S\n";
		else cout << "N\n";
Copy The Code & Try With Live Editor


#1125 Beecrowd Online Judge Solution 1090 Formula 1 Solution in C, C++, Java, Js and Python
#1129 Beecrowd Online Judge Solution 1129 Optical Reader Solution in C, C++, Java, Js and Python