Minor Setback

Photo by
Xato

You are developing a smartphone app that converts audio recorded from an instrument into sheet music. You already have the code to record the audio and convert it into sequence of frequency values. What is left is to translate those frequencies into pitch names more easily recognizable to musicians.

Musical pitches are described by frequencies using a logarithmic scale. The frequency $440\ \textrm{Hz}$ corresponds to the pitch named $\textrm{A}$. Multiplying a pitch’s frequency by $\sqrt [12]{2}$ produces the next higher pitch. Table 1 lists pitches used in Western music and their frequencies.

frequency (Hz) |
pitch name |
frequency (Hz) |
pitch name |

$440$ |
$\textrm{A}$ |
$440 \cdot 2^{6/12} \approx 622.25$ |
$\textrm{D}^{\sharp }$, $\textrm{E}^{\flat }$ |

$440 \cdot 2^{1/12} \approx 466.16$ |
$\textrm{A}^{\sharp }$, $\textrm{B}^{\flat }$ |
$440 \cdot 2^{7/12} \approx 659.26$ |
$\textrm{E}$ |

$440 \cdot 2^{2/12} \approx 493.88$ |
$\textrm{B}$ |
$440 \cdot 2^{8/12} \approx 698.46$ |
$\textrm{F}$ |

$440 \cdot 2^{3/12} \approx 523.25$ |
$\textrm{C}$ |
$440 \cdot 2^{9/12} \approx 739.99$ |
$\textrm{F}^{\sharp }$, $\textrm{G}^{\flat }$ |

$440 \cdot 2^{4/12} \approx 554.37$ |
$\textrm{C}^{\sharp }$, $\textrm{D}^{\flat }$ |
$440 \cdot 2^{10/12} \approx 783.99$ |
$\textrm{G}$ |

$440 \cdot 2^{5/12} \approx 587.33$ |
$\textrm{D}$ |
$440 \cdot 2^{11/12} \approx 830.61$ |
$\textrm{G}^{\sharp }$, $\textrm{A}^{\flat }$ |

$880$ |
$\textrm{A}$ |

Doubling any pitch’s frequency yields the same pitch, but one octave higher (note that both $440$ and $880\ \textrm{Hz}$ correspond to pitch $\textrm{A}$). This rule generalizes: multiplying $554.37\ \textrm{Hz}$ by a power of two yields another $\textrm{C}^{\sharp }$. Some pitches have multiple names, as shown in the table.

You have a song, represented as a sequence of frequencies.
Songs in a *musical key* typically contain only a subset
of the possible pitches. Assume that the given song is in one
of the common keys listed in Table 2. First, determine
what key the song is in. Then, translate the song into a
sequence of pitch names.

key name |
allowed pitches |
key name |
allowed pitches |

$\textrm{G}$ major |
$\textrm{G}$, $\textrm{A}$, $\textrm{B}$, $\textrm{C}$, $\textrm{D}$, $\textrm{E}$, and $\textrm{F}^{\sharp }$ |
$\textrm{F}^{\sharp }$ minor |
$\textrm{F}^{\sharp }$, $\textrm{G}^{\sharp }$, $\textrm{A}$, $\textrm{B}$, $\textrm{C}^{\sharp }$, $\textrm{D}$, and $\textrm{E}$ |

$\textrm{C}$ major |
$\textrm{C}$, $\textrm{D}$, $\textrm{E}$, $\textrm{F}$, $\textrm{G}$, $\textrm{A}$, and $\textrm{B}$ |
$\textrm{G}$ minor |
$\textrm{G}$, $\textrm{A}$, $\textrm{B}^{\flat }$, $\textrm{C}$, $\textrm{D}$, $\textrm{E}^{\flat }$, and $\textrm{F}$ |

$\textrm{E}^{\flat }$ major |
$\textrm{E}^{\flat }$, $\textrm{F}$, $\textrm{G}$, $\textrm{A}^{\flat }$, $\textrm{B}^{\flat }$, $\textrm{C}$, and $\textrm{D}$ |

The first line of input contains a single integer $1 \leq N \leq 100\, 000$, the number of frequencies in the song. The next $N$ lines each contain a real number $20 \le f \le 4\, 000$, representing one pitch frequency, with at most $8$ digits after the decimal point. You may assume that the song was played using an instrument that is in tune, so that each frequency represents a valid pitch: each frequency approximates $440\cdot 2^{a/12}$ for some integer $a$ with absolute error at most $10^{-4}$.

On the first line, output the name of the key that the song
was played in: `G major`, `F# minor`, etc. See below for instructions for
how to format pitch names. If the song does not fit any of the
keys in Table 2, or if multiple possible keys could fit the
song, print `cannot determine key`.

If the key could not be determined, print no further output.
Otherwise, print $N$
lines, each containing one pitch name (in the order of the
input sequence). Each pitch name should be a letter `A` through `G` followed
optionally by a second character, either `#` or `b`, indicating a
sharp or flat. Note that although pitches can have multiple
names, only one of these names is listed in the allowed-pitches
table for any given key, and this is the name you should use.
For example, print `C#`, and not
`Db`, when writing pitches for the key
$\textrm{F}^{\sharp }$
minor.

Sample Input 1 | Sample Output 1 |
---|---|

7 783.9908720 783.9908720 587.3295358 587.3295358 659.2551138 659.2551138 587.3295358 |
cannot determine key |

Sample Input 2 | Sample Output 2 |
---|---|

5 523.2511306 391.9954360 440.0 329.6275569 369.9944227 |
G major C G A E F# |