Alto Singing

Sheet music, public domain
Anton is a famous choir singer in the Kongliga Teknologkören, the KTH choir. After years of careful political maneuvering, he managed to become the chairman of the choir. As such he has absolute power of what the choir does – including what pieces to rehearse.

Anton has chosen a particular song he likes very much that he wants the choir to sing. There is only a slight problem – the song is not at all suited for his particular vocal range. Anton has the alto vocal range, and wants to make sure that the most important part of the piece is perfect for his voice.

The piece is currently written down using the $12$ standard tones, in ascending order C, C#, D, D#, E, F, F#, G, G#, A, A#, B, each followed by an integer denoting the octave the tone appears in. The lowest octave is $1$. Immediately after the B tone of octave $i$, the C tone of octave $i + 1$ follows.

Now, Anton wants to transpose the piece so that all tones in the part are within his vocal range, which is given by the lowest and highest tone he can sing. Transposing means that all tones are shifted either up or down by some fixed number of tones. For example, C#4 (C# in the fourth octave) transposed $5$ tones down would be G#3. Furthermore, Anton is not very good at reading sheet music. Among all valid transpositions, he is only interested in the ones that minimize the number of tones with accidentals (that is, those with a # sign)1.

Given the piece and Anton’s vocal range, can you determine how many such transpositions there are?


The first line of input contains the number of tones $n$ ($1 \le n \le 1000$) in the piece. Then follows a line containing two tones, the lowest and the highest tone that Anton can sing (in that order).

The third and final line contains the tones that Anton’s piece consists of. The same tone may appear multiple times in the piece. It is guaranteed that Anton can sing at least one transposition of the piece.

Each tone is written as one of the $12$ tones C, C#, D, D#, E, F, F#, G, G#, A, A#, B followed immediately by its octave without any space in between. Only octaves between $1$ and $10^9$ are used2.


Output a single line with two integers – the minimum number of accidentals (notes with #) among all transpositions, and the number of transpositions that keeps the piece in Anton’s vocal range and has the minimum number of accidentals. If the piece is already in Anton’s vocal range, the transposition of $0$ tones should be counted as well (if that minimizes accidentals).

Sample Input 1 Sample Output 1
F3 F5
C4 C4 G4 G4 A4 A4 G4 F4 F4 E4 E4 D4 D4 C4
0 3
Sample Input 2 Sample Output 2
C#1 A#1
0 5
Sample Input 3 Sample Output 3
F3 F5
F3 F#3 F5
1 1


  1. For those of you who know music, Anton finds writing down a key for the piece other than C major even more confusing, since he must then remember what tones should be raised or lowered throughout the piece.
  2. Possibly only after centuries of vocal exercises.
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 3.9medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in