Question

一道ACM题目，看不懂

1026 Major ScalesTimeLimit : 1 Second Memorylimit : 32 Megabyte

Totalsubmit : 37 Accepted : 20

In music, the range of audible frequencies is divided into octaves, where each octave spans frequencies within factor of 2 of one another. For example, the note called middle C corresponds to an audio frequency of 263 Hz. The octave below middle C spans the frequency range from 131.5 Hz to 263 Hz while the octave above middle C spans the range from 263 Hz to 526 Hz.

An octave contains 13 chromatic notes whose frequencies differ by a common ratio. The separation between two adjacent chromatic notes is called a half-step or semi-tone. Note that there are 12 semi-tones in an octave and therefore the frequency ratio represented by a semi-tone is 1.0593 (since 1.0593^12 = 2). A tone is two semi-tones.
While it might be convenient to use frequencies to describe musical notes, historical tradition demands that we name the notes of the chromatic scale, in order: C, C#, D, D#, E, F, F#, G, G#, A, A#, B, C, and so on, repeating the same names for each new octave.

Western music rarely uses all the notes in the chromatic scale. Instead, 8 of the 13 chromatic notes are commonly used a composition. The most common such set of 8 notes is the major scale. The 8 notes of a major scale, in order, are separated by: tone, tone, semi-tone, tone, tone, tone, semi-tone. A major scale can begin with any of the chromatic notes; this note defines the key of the scale. Coincidentally, in the key of C, the major scale consists of the notes: C, D, E, F, G, A, B, C. On the other hand, in the key of F, the major scale is: F, G, A, A#, C, D, E, F.

There are other scales, notably the minor scale, and music composed in a particular scale sometimes uses notes that are not within the scale, caled accidentals. We shall concern ourselves only with music composed in a major scale with no accidentals.

Your job is to read a sequence of notes and to identify all the keys that the music might have been composed in. Your program need not have any musical ear: report a particular key if and only if all the notes come from the major scale in that key.

Input

Input contains several test cases. Each test case consists of a single line of input, containing a sequence of chromatic notes separated by white space. No input line exceeds 1000 characters. The last line of input contains the word "END".

Output

For each test case, output a line giving the possible keys, in the order given above.

Sample Input

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

Sample Output

C

C F
C C# D# F G G# A#
题目大概看懂了，不过它问的是什么还不清楚。
而且为什么输入有四个，输出却只有三个。
能解释一下吗？

Answer 1

这道题目和乐理有关系. 题目大意是输入一串或多串半音符序列(每串用一行表示, 每个半音符间用空格隔开), 然后程序要判断每串音符可能采用了哪些调号, 再输出(每个调号间用空格隔开).

首先理解:

1) 半音符序列为: C C# D D# E F F# G G# A A# B C ....(每两个代号之间相差半音)
2) 大调音阶(major scale)的定义: 可以任何一个半音符开始(此半音符即称为此串音符的调号)的由8个半音符组成的任意排序的序列, 但这8个半音符是根据"全音-全音-半音-全音-全音-全音-半音"这个规律来挑选的. 即第一个半音符与第二个半音符之间相差全音(即两个半音), 第二音与第三音间也是相差全音, 第三音与第四音间相差半音, 如此类推......

所以, 程序应该先根据以上先定义出所有可能的大调音阶(major scale), 如:

C大调(the major scale in the key of C)由以下8个半音符组成:
C D E F G A B C
C#大调: C# D# F F# G# A# C C#
D大调: D E F# G A B C# D
......

题目所举例子的解释:
第一行: C C D F E G A A F G B, 去除重复的半音符后剩下C D E F G A B, 然后程序与所有的大调比较, 发现能全部包括这7个半音符的调号只有C, 所以输出"C"
第二行: A B C D E F G C#, 程序与所有的大调比较, 发现没有一个调号的大调能全部包括这8个半音符, 所以输出为空
第三行: C C D F E G A A F G, 去除重复的半音符后剩下C D E F G A, 然后程序与所有的大调比较, 发现能全部包括这6个半音符的调号有C和F, 所以输出"C F"
第四行: C C C C C, 去除重复的半音符后剩下C, 然后程序与所有的大调比较, 发现能包括这一个半音符的调号有C,C#,D#,F,G,G#,A#这7种, 所以输出"C C# D# F G G# A#"