Problem D
Minor Setback
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.
Some Music Theory
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.
Your Task
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}$ |
Input
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}$.
Output
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# |
