“A key signature is not the same as a key; key signatures are merely notational devices. They are convenient principally for diatonic or tonal music. Some pieces that change key (modulate) insert a new key signature on the staff partway, while others use accidentals: natural signs to neutralize the key signature and other sharps or flats for the new key.” – Wikipedia You see, key signatures can be really confusing at times. For example, consider the follow score, whose key signature is “0 sharp/flat” (which usually indicates C major/A minor): (InASCIIformat: B#C#DE#F#G#AB) It’s more reasonable to rewrite the score in the key signature “5 sharp” (which usually indicates B major/g# minor): (InASCIIformat: BCDEFGAB) This is more “natural” because no accidentals (i.e. sharp/flat/natural sign) exist. Given a music piece with a key signature, your task is the find the best key signature that minimizes the number of accidentals. Under that condition, the number of sharps/flats in the key signature should be minimized. Note that you CANNOT change the staff position of any note. For example, you can’t change #G to bA even if this can save accidentals. To simplify this problem, we only consider sharp, flat and natural accidentals (no double accidentals or half-sharps etc), and all the notes are in the same octave. No notes will be tied to the same note across the barline. In your optimized score, no courtesy or cautionary accidental should be placed by a note whose pitch is, strictly speaking, already given by the key signature. However, in the original piece, such accidentals might exist to make people’s life easier, because even musicians may sometimes get confused when reading the score at speed. Important notes: • Don’t forget the effect of accidental last until the end of the measure. For example, the measure bA A A A contains only one accidental, but the last three notes are also affected, so all four notes are of the same pitch. • The effect of the accidental has to be understood in relation to the “natural” meaning of the note’s staff position, so in the key signature with 3 sharps, a bG note is actually TWO semitones lower than G (which is actually #G, thanks to the key signature).
2/3 Input The first line contains the number of test cases T (T ≤ 100). Each test case begins with the initial key signature formatted as “m#/b”, that means the key signature has m sharps/flats (0 ≤ m ≤ 7). If m = 0, then the #/b part is omitted. The next line contains the notes, separated by barlines ‘|’ and ending with a double barline ‘||’. Consecutive notes and barlines are separated by a single space. Each note is formatted as two characters, where the first is either empty or one of ‘#’(sharp), ‘b’(flat) or ‘n’(natural), the second character is one of C,D,E,F,G,A,B (upper-case). There will be at most 10 measures and 100 notes in each score. Output For each test case, print the minimum number of accidentals in the first line, and then the best key signatures having the least number of sharps/flats, in the same format as the input. Key signatures should be sorted lexicographically. Print a blank line after each test case. Appendix: Staff. In standard Western musical notation, the staff, or stave, is a set of five horizontal lines and four spaces that each represent a different musical pitch. You can see in the web page: http://en.wikipedia.org/wiki/Staff_%28music%29. Key signature. A key signature is a series of sharp or flat symbols placed on the staff, designating notes that are to be consistently played one semitone higher or lower than the equivalent natural notes unless otherwise altered with an accidental... See: http://en.wikipedia.org/wiki/Key_signature. Accidentals. An accidental is a note whose pitch (or pitch class) is not a mem- ber of a scale or mode indicated by the most recently applied key signature... In most cases, a sharp raises the pitch of a note one semitone while a flat lowers it a semitone. A natural is used to cancel the effect of a flat or sharp. This sys- tem of accidentals operates in conjunction with the key signature, whose effect contin- ues throughout an entire piece, unless can- celed by another key signature. An acci- dental can also be used to cancel or re- instate the flats or sharps of the key sig- nature...accidentals have been understood to continue for the remainder of the mea- sure in which they occur, so that a sub- sequent note on the same staff position is still affected by that accidental, unless marked as an accidental on its own... See: http://en.wikipedia.org/wiki/Accidental_%28music%29 Finally, looking that Circle of fifth if you’re not sure about some key signatures. Sample Input 4 0
3/3 C D E #F G | A B C || 1b F F bB B | B B #F F bD || 7# C D bE E F bG | G A bB || 0 #F #C bB bE || Sample Output Case 1: 0 1# Case 2: 1 4b Case 3: 3 5# Case 4: 2 2# 2b