Alberta Collegiate Programming Contest 2017


2017-10-14 18:00 UTC

Alberta Collegiate Programming Contest 2017


2017-10-14 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -958 days 11:21:29

Time elapsed


Time remaining


Problem G
Musical Scales

The following are musical notes in “increasing order”:

A, A#, B, C, C#, D, D#, E, F, F#, G, G#

The difference between consecutive notes is a semitone, and the sequence wraps around so the note that is one semitone above G# is A. The difference between a tone is the same as two semitones. So the note that is one tone above B is C#. The note that is one tone above G is A.

We do not worry about flats such as Cb nor do we worry about adding a # sign to B and E in this problem (they are aliases for notes that are already listed).

A major scale is defined by a note (such as A or C#) and all other notes following that one in an arithmetic progression:

tone, tone, semitone, tone, tone, tone, semitone

The starting note appears in the name of the scale.

For example, the scale A#-major consists of the following notes:

A#, C, D, D#, F, G, A, A#

(by convention, the first note is repeated at the end of the sequence)

Finally, in this problem a song is just a sequence of notes. Your job is to identify all major scales such that the song uses only notes in that scale.


The first line of input is an integer $1\leq n \leq 100$ denoting the number of notes played in a song. The second line consists of a sequence of notes, separated by spaces.


Output consists of a single line that lists all scales the song may be played in. Consecutive scales should be separated by a single space and the scales must appear in lexicographic order. If the song may not fit in any one of these scales, simply output a line containing the text none.

Sample Input 1 Sample Output 1
C D F D C D F F F C 
A# C D# F
Sample Input 2 Sample Output 2
A B A F# G# C