Minor Setback

면접 대비

시간 제한3초메모리 제한1024 MB

요약

440 Hz 기준 반음 계열 주파수 N개가 주어진다. 표에 나열된 키 중 정확히 하나만 맞는 키를 찾아 없으면 판정을 출력하고 맞으면 각 음을 그 키가 쓰는 표기로 출력한다.

난이도: 보통10점 중 5점
유형: 구현, 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

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.

Table 1: Frequencies and corresponding pitch names of various notes.


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.

Table 2: A few musical keys and the pitches they use.


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.

예제2

예제 1

입력

7
783.9908720
783.9908720
587.3295358
587.3295358
659.2551138
659.2551138
587.3295358

예상 출력

cannot determine key

예제 2

입력

5
523.2511306
391.9954360
440.0
329.6275569
369.9944227

예상 출력

G major
C
G
A
E
F#