Find the keys P29346


Statement
 

pdf   zip

html

Rick Deckard falls asleep while Rachael plays the piano and lets down her hair.

Deckard: I dreamt music.

Rachael: I didn’t know if I could play. I remember lessons. I don’t know if it’s me or Tyrell’s niece.

Rachael softly plays thirteen notes on the piano: (2.8,0)

Deckard: You play beautifully.

Rachael: I remember well there are twelve different notes: C, C#, D, D#, E, F, F#, G, G#, A, A# and B; and then comes C again. However, if I play in the key of C, I can’t use the second, the fourth, the seventh, the ninth nor the eleventh notes, that is, C#, D#, F#, G# nor A#.



Rachael plays a scale of C: (1.8,0)




Rachael: However, if I play in the key of, say E, I can’t use the second, the fourth, the seventh, the ninth nor the eleventh notes either, but now starting from E, that is, F, G, A#, C nor D.



Rachael plays a scale of E: (2,0)




Deckard: If I play a tune, can you tell me the key it is in?

Rachael: Of course!




Deckard plays some notes: (2,0)





[r]

Rachael covers her face with her hand…

* * *

Despite Deckard’s clumsy attempts at musical art, can you write a program such that, given a sequence of notes, tells the possible keys the tune is written in?

Input

Input consists of several cases. Every case begins with a number n followed by n notes. Note names are uppercase letters from A to G, optionally suffixed by #. There are no E# nor B# notes.

Output

For every case, print a lexicographically sorted list of the possible keys the tune is written in. If a tune cannot belong to any key, print “None”.

Public test cases
  • Input

    7 C D E F G A B
    7 E F# G# A B C# D#
    9 C# B C# F# D C# D C# B
    5 C D E F# G#
    2 A# F
    

    Output

    C
    E
    A D
    None
    A# C# D# F F# G#
    
  • Information
    Author
    Èdgar Gonzàlez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Semifinal
    Date
    2008-06-28