Minor Setback

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

요약

튜닝된 주파수 N개가 주어질 때 모든 음이 맞는 장조 또는 단조를 하나만 찾아 각 음의 이름을 출력합니다.

난이도: 보통10점 중 4점
유형: 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

음의 높이는 로그 눈금의 주파수로 나타낸다. 주파수 $440\ \textrm{Hz}$ 가 음이름 $\textrm{A}$ 에 해당한다. 어떤 음의 주파수에 $\sqrt[12]{2}$ 를 곱하면 반음 높은 음이 된다. 표 1은 서양 음악에서 쓰는 음과 그 주파수를 보여준다.

표 1: 여러 음의 주파수와 음이름.

주파수(Hz)	음이름	주파수(Hz)	음이름
$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}$

어떤 음의 주파수를 2배 하면 같은 음이 한 옥타브 높아진다. $440$ Hz와 $880$ Hz가 모두 $\textrm{A}$ 에 해당하는 이유다. 이 규칙은 일반화된다. $554.37\ \textrm{Hz}$ 에 2의 거듭제곱을 곱하면 또 다른 $\textrm{C}^{\sharp }$ 가 된다. 표에서 보듯 한 음에 이름이 둘 이상 붙는 경우도 있다.

노래 한 곡은 주파수의 수열로 나타낸다. 장조나 단조 같은 조에 속한 노래는 보통 가능한 음 중 일부만 쓴다. 이 노래가 표 2의 일반적인 조 중 하나에 속한다고 가정하라. 먼저 노래의 조를 찾고, 그다음 노래를 음이름의 수열로 바꿔라.

표 2: 몇 가지 조와 사용하는 음.

조 이름	사용하는 음	조 이름	사용하는 음
$\textrm{G}$ major	$\textrm{G}$ , $\textrm{A}$ , $\textrm{B}$ , $\textrm{C}$ , $\textrm{D}$ , $\textrm{E}$ , $\textrm{F}^{\sharp }$	$\textrm{F}^{\sharp }$ minor	$\textrm{F}^{\sharp }$ , $\textrm{G}^{\sharp }$ , $\textrm{A}$ , $\textrm{B}$ , $\textrm{C}^{\sharp }$ , $\textrm{D}$ , $\textrm{E}$
$\textrm{C}$ major	$\textrm{C}$ , $\textrm{D}$ , $\textrm{E}$ , $\textrm{F}$ , $\textrm{G}$ , $\textrm{A}$ , $\textrm{B}$	$\textrm{G}$ minor	$\textrm{G}$ , $\textrm{A}$ , $\textrm{B}^{\flat }$ , $\textrm{C}$ , $\textrm{D}$ , $\textrm{E}^{\flat }$ , $\textrm{F}$
$\textrm{E}^{\flat }$ major	$\textrm{E}^{\flat }$ , $\textrm{F}$ , $\textrm{G}$ , $\textrm{A}^{\flat }$ , $\textrm{B}^{\flat }$ , $\textrm{C}$ , $\textrm{D}$

입력

첫 줄에 노래의 주파수 개수를 나타내는 정수 $1 \leq N \leq 100\, 000$ 이 주어진다. 다음 $N$ 개 줄에는 음 하나의 주파수를 나타내는 실수 $20 \le f \le 4\, 000$ 이 한 줄에 하나씩 주어진다. 소수점 아래는 최대 8자리다. 악기는 정확하게 조율되어 있었다고 가정해도 된다. 따라서 각 주파수는 어떤 정수 $a$ 에 대해 $440\cdot 2^{a/12}$ 에 절댓값 오차 $10^{-4}$ 이하로 가까운 값이다.

출력

첫 줄에 노래가 연주된 조의 이름을 출력한다. G major, F# minor처럼 쓴다. 음이름의 형식은 아래와 같다. 노래가 표 2의 어떤 조에도 맞지 않거나 맞는 조가 둘 이상이면 cannot determine key를 출력한다.

조를 정하지 못하면 다른 내용은 출력하지 않는다. 그렇지 않으면 입력 순서대로 음이름을 한 줄에 하나씩 $N$ 줄 출력한다. 음이름은 A부터 G 중 한 글자이고, 필요하면 두 번째 글자로 #(샤프) 또는 b(플랫)를 붙인다. 음 하나가 여러 이름을 가질 수 있어도, 각 조의 표에 적힌 이름만 쓴다. 예를 들어 $\textrm{F}^{\sharp }$ 단조에서는 Db 대신 C#을 출력한다.

예제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#