ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1974. Similar Tunes

Time limit: 1.0 second
Memory limit: 64 MB
‘The boss gave me a disk with soundtracks of all six episodes of the Star Wars. We must make sure that the tune we want to use in our game isn’t similar to any of the tunes on the disk. He says that even though we’ve written the tune ourselves, copyright holders may file a lawsuit against us if they find a slightest similarity between our tune and any of their tunes. Then we’ll have to pay multimillion fines.’
‘But it can take us many hours to listen to all the tunes from the disk, and it can be difficult to find similar tunes by listening. We need to automate the process.’
‘I think we can write a program for comparing the tunes and then listen to the tunes from the disk for which the computed similarity to our tune is high enough. The comparison algorithm can be the following. If we neglect pauses and the lengths of sounds, we can write each tune as a string of sounds. For strings s and t of equal length, let’s call the number of positions i in which s[i] = t[i] the intersection size I(s, t) of these strings. The absolute similarity of strings s and t will be the maximum of I(u, v) for all u and v, where u is a substring of s and v is a substring of t and the lengths of u and v are the same. For example, the absolute similarity of the strings “AAAAA” and “ABABA” is three, and the absolute similarity of the strings “BABAB” and “ABABA” is four. The relative similarity between our tune and a tune from the disk is the ratio of their absolute similarity to the length of the tune from the disk. This value will be computed by our program.’


The first line describes the tune used in the game. The description of the tune starts with the length n of the tune, which is followed by the description of n sounds. The second line contains the number m of tunes on the Star Wars soundtrack disk (1 ≤ m ≤ 100). Each of the following m lines describes these tunes in the same format as the tune from the game is described. All tunes have lengths from 1 to 1000.
The description of sound is a string “dN”, “dN+”, or “dN-”, where d is a number of octave, N is a note letter name (an uppercase English letter), “+” and “-” are symbols of raising and lowering a note by a half tone. There are eight octaves numbered from 1 to 8. Each octave consists of 12 sounds: C, C+, D, D+, E, F, F+, G, G+, A, A+, B (sounds follow in this order in the octave). Some of these sounds have alternative notation. In the following pairs both notations denote the same sound of this octave: (C+, D-), (D+, E-), (E, F-), (F, E+), (F+, G-), (G+, A-), and (A+, B-). Also a notation B+ denotes a sound C of the next octave, and a notation C- denotes a sound B of the previous octave. There are no sounds 1C- and 8B+.


Output m lines, each containing one number. The numbers are the relative similarities between the tune from the game and the tunes from the disk. The answer must have absolute or relative error not exceeding 10−6.


4 5C+ 5D 5C 5G
2 5D- 5D
2 5D 4B+
4 5D 5C+ 5D 5F-
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013