27887번 - 가희와 코드

문제

가희의 오빠는 노래를 듣고 즉석에서 반주를 하는 능력이 있습니다. 이번에도 가희는 새로운 노래를 듣고 가희만의 방식으로 반주를 하려고 합니다. 문제에서 등장하는 음의 이름은 12개가 있습니다.

[표 1] 문제에 등장하는 12개의 음의 이름

음의 이름은 같지만, 높이가 다를 수 있습니다. 이는 {octave}로 결정됩니다.

음에 대한 정보는 아래 두 형식 중 하나로 주어집니다.

• {character}{octave}
  • {octave} 옥타브에 있는 음의 이름이 {character}인 음입니다.
• {character}{octave}{additional_character}
  • {octave}옥타브에 있는 음의 이름이 {character}{additional_character}인 음입니다.
  • {additional_character}는 # 또는 $ 중 하나입니다.

즉, 음에 대한 정보는 {octave} 와 음의 이름으로 이루어져 있습니다. 아래 [그림 1]은 피아노 건반을 나타내며, 오른쪽으로 갈수록 음높이가 높아집니다.

[그림 1] 0 옥타브에 있는 음들과 대응되는 피아노 건반

두 음이 인접한다면 아래 조건 중 하나를 만족합니다.

• 두 음이 같은 옥타브에 있는 경우
  • 음의 이름이 n1인 것의 순번 s1과 음의 이름이 n2인 것의 순번 s2의 차이가 1일 때, 두 음은 인접합니다.
  • 음의 이름이 n1인 것의 순번은 [표 1]에 있습니다.
• octave 옥타브이고 음의 이름이 B인 음과 ocvate+1 옥타브이고 음의 이름이 C인 두 음은 인접합니다.

예를 들어, 0 옥타브 C와 0 옥타브 C#은 1번 조건을, 0 옥타브 B와 1 옥타브 C는 2번 조건을 만족시킵니다. 따라서, 1 옥타브 C와 1 옥타브 C#, 0 옥타브 B와 1 옥타브 C는 인접합니다. 아래 [그림 2]에서 빨간 화살표는 인접한 두 음을 보여줍니다.

[그림 2] 인접한 두 음의 예시

인접한 두 음 사이의 거리는 반음입니다. 음 note1과 음 note2의 반음 거리가 n이라는 의미는 아래 둘 중 하나를 의미합니다.

• 음 note1보다 3개의 반음만큼 음높이가 높아진 음은 note2입니다.
• 음 note1보다 3개의 반음만큼 음높이가 낮아진 음은 note2입니다.

아래 [표 3]은 문제에 자주 등장하는 용어들을 나타낸 것입니다.

[표 2] 문제에 자주 나오는 용어들과 대응되는 반음 거리

[그림 3] 0 옥타브 도 C0로부터 단 3도 위, 장 3도 위에 있는 음

[그림 1]에서 각 화살표들은 반음 1개의 거리를 나타냅니다. 음 C0으로부터 단 3도 위에 있는 음은 D0#이고 음의 이름은 D#입니다. C0에서 출발하여 빨간색 화살표 따라 이동하면 도착하는 음이기 때문입니다. 음 C0으로부터 장 3도 위에 있는 음은 E0이고, 음의 이름은 E입니다. C0에서 출발하여, 빨간색 화살표와 보라색 화살표를 따라 이동하면 도착하는 음이기 때문입니다.

이제 코드에 대해 설명하겠습니다. 코드에서 근음(1음)이란 뿌리가 되는 음을 의미합니다. 그 위에 장 3도, 또 그 위에 단 3도를 쌓아 올려서 만든 코드를 Major 코드라고 합니다. 몇 개의 Major 코드의 예시가 [표 3]에 있습니다.

[표 3] Major 코드 예시

다음에 minor 코드를 알아보겠습니다. Major 코드에서 3음을 반음 내린 것을 minor 코드라고 합니다. 몇 가지 minor 코드의 예제가 [표 4]에 있습니다.

[표 4] minor 코드 예시

다음에 aug 코드를 알아보겠습니다. Major 코드에서의 5음을 반음 올린 것을 aug 코드라고 합니다. 몇 가지 aug 코드의 예제가 [표 5]에 있습니다.

[표 5] aug 코드 예시

다음에 dim 코드를 알아보겠습니다. Major 코드에서의 3음, 5음을 반음 내린 것을 dim 코드라고 합니다. 몇 가지 dim 코드의 예제가 [표 6]에 있습니다.

[표 6] dim 코드 예시

가희는 아래와 같은 알고리즘으로 반주를 하려고 합니다.

• 이전 p개의 마디에서 k번 이상 쓰였던 코드들은 제외합니다. 이 작업을 수행한 후 남은 코드의 개수가 r이라면
  • r이 0인 경우, 가장 오랫동안 사용하지 않은 코드를 선택합니다.
    • 그러한 코드가 여러 개 있다면, 아스키코드 사전 순으로 가장 앞에 있는 것을 선택합니다.
  • r이 0보다 큰 경우
    • 코드를 이루는 음의 이름이 m번째 마디에 총 몇 번 나왔는지를 계산합니다. 이 수치가 가장 높은 코드를 선택합니다.
    • 그러한 것이 여러 개인 경우, 아스키코드 사전 순으로 가장 앞선 코드를 선택합니다.

이 알고리즘에 따라, p와 k가 1이고 마디 수가 1인 음악에 대해 반주해 보겠습니다.

[표 7] 예제 1의 곡

먼저 첫 번째 마디에 F2, E2, D2, E2, F2, 순서대로 나옵니다. 즉, 음의 이름이 D(레)인 것이 1번, E(미)인 것이 2번, F(파)인 것이 2번 나옵니다. C Major 코드를 이루는 음의 이름이 1번째 마디에서 몇 번 나왔는지 세 보겠습니다.

[표 8] C, E, G가 1번째 마디에 나온 횟수

C Major를 이루는 음의 이름이 C, E, G인 것이 나온 횟수를 모두 합하면 2가 됩니다. 이런 식으로 모든 코드에 대해, 코드를 이루는 음의 이름이 1번째 마디에 총 몇 번 나왔는지 계산합니다. 그 결과는 [표 9]에 있습니다.

[표 9] 코드를 이루는 음의 이름이 1번째 마디에 나온 횟수

이 중, 아스키코드 사전 순으로 가장 앞선 것은 A#M이 됩니다.

이제 p가 2, k가 1이고 마디 수가 3인 음악에 대해 반주해 보겠습니다.

[표 10] 예제 2의 곡

먼저 첫 번째 마디에 F2, F3, F2, F3, F2, F3, F2, F3 순서대로 나옵니다. 즉 음의 이름이 F(파)인 것이 8번 나옵니다.

[표 11] 각 코드가 이루는 음의 이름이 1번째 마디에 나온 횟수

코드를 이루는 음의 이름이 총 몇 번 나왔는지 셉니다. 가장 많이 나온 코드는 8회였고, 이를 만족하는 코드는 총 12개입니다. r이 0보다 크므로, 12개의 코드 중 아스키코드 사전 순으로 가장 앞선 A#M을선택합니다.

2번째 마디를 반주해 보겠습니다. 두 번째 마디에는 F0, F1, F0, F1, F0, F1, F0, F1 순서대로 나옵니다. 1번째 마디와 같이 음의 이름이 F(파)인 것이 8번 나옵니다. 이전 2개의 마디에서 1번 이상 쓰인 A#M을 제외한 나머지 코드들에 대해, 각 코드가 이루는 음의 이름이 총 몇 번 나왔는지 셉니다.

[표 12] 각 코드가 이루는 음의 이름이 2번째 마디에 나온 횟수

코드를 이루는 음의 이름이 총 몇 번 나왔는지 셉니다. 가장 많이 나온 횟수는 8번이었고, 이를 만족하는 코드는 11개입니다. r이 0보다 크므로, 11개의 코드 중 아스키코드 사전 순으로 가장 앞선 A#m를 선택합니다.

3번째 마디를 반주해 보겠습니다. 세 번째 마디에는 F2, F2, F3, F2, F3, F2, F3, F2 순서대로 나옵니다. 1, 2번째 마디와 같이 음의 이름이 F(파)인 것만 8번 나옵니다. 이전 2개의 마디에서 1번 이상 쓰인 A#M, A#m을 제외한 나머지 코드들에 대해, 각 코드가 이루는 음의 이름이 총 몇 번 나왔는지 셉니다.

[표 13] 각 코드 이루는 음의 이름이 3번째 마디에 나온 횟수

가장 많이 나온 횟수는 8번이었고, 이를 만족하는 코드는 10개입니다. r이 0보다 크므로, 10개의 코드 중 아스키코드 사전 순으로 가장 앞선 Aaug를 선택합니다.

입력

첫 줄에 마디 수 m과 문제에서 설명한 p, k가 공백으로 구분되어 주어집니다.

다음 m개의 줄에 마디에 나오는 음의 정보들이 주어집니다. 이때 음은 아래와 같은 형식으로 주어집니다.

{character}{octave}{addtional_character}

• {character}
  • A, B, C, D, E, F, G 중 하나로 주어집니다. 한국식 음의 이름은 각각 라, 시, 도, 레, 미, 파, 솔을 의미합니다.
• {octave}
  • -2보다 크거나 같고 7보다 작거나 같은 수로 주어집니다.
• {addtional_character} (optional)
  • {character}{octave}보다 반음 높은 경우 #으로, 반음 낮은 경우 $으로 주어집니다.
  • 이때, 해당 음에서만 반음이 높아지거나 낮아지는 효력이 발생합니다.

예를 들어 한 마디에 0 옥타브 레, -1 옥타브 시, 0 옥타브 레#, 0 옥타브 레♭이 있다고 했을 때, 아래와 같이 입력이 주어집니다.

D0B-1D0#D0$

또한 한 마디에 0 옥타브 레#, 0 옥타브 레, 0 옥타브 레#, 0 옥타브 레#이 있다고 했을 때, 아래와 같이 입력이 주어집니다.

D0#D0D0#D0#

단, 아래의 입력은 주어지지 않습니다.

[표 14] 주어지지 않는 입력

출력

m개의 줄에 답을 출력해 주세요. 이때

{character}{additional_character}{type}

형식으로 출력해 주세요.

• {character}
  • A, B, C, D, E, F, G 중 하나입니다. 한국식 음의 이름은 각각 라, 시, 도, 레, 미, 파, 솔을 의미합니다.
• {addtional_character} (optional)
  • 근음이 {character}보다 반음 위에 있는 경우 #으로 출력합니다.
    • 단 {character}가 B이거나 E인 경우 뒤에 #을 붙이지 않습니다.
  • #을 붙인 경우, 해당 음에서만 반음이 높아지는 효력이 발생합니다.
• {type}
  • 문제에 제시된 M, m, aug, dim중 하나입니다.

예를 들어, D#M의 경우, E$M으로도 표시될 수 있습니다. 이는 같은 옥타브에 있는 음의 이름이 D#인 것과, E$인 것이 같은 음(딴이름 한소리)이기 때문입니다. 이로 인해 발생하는 혼동을 방지하기 위해 출력 형식 제한이 있다는 것을 유의해 주세요.

제한

• 1 ≤ m ≤ 5×104
• 1 ≤ p ≤ m
• 1 ≤ k ≤ p
• 주어지는 음의 총개수는 50만을 넘어가지 않습니다.
• 각각의 마디에는 최소 하나 이상의 음이 있습니다.
• 조표에 아무것도 붙지 않았다고 가정합니다.
• 문제에 나오지 않는 요소들 (ex. 제자리표, 겹올림, 겹내림, 붙임줄, 이음줄)은 모두 무시합니다.

힌트

오빠. 숨어서 듣지 말고 대놓고 듣자.