Improwizator [B]

Limit pamięci: 32 MB

Adaś od dziecka chciał grać jazz. Wyrósł już na Adama, a postępów wciąż nie widać. Postanowił więc wykorzystać doświadczenie zdobyte na studiach informatycznych i użyć komputera. Co więcej, zdaniem profesora Barwiejuka wymyślony przez Adama Algorytm Improwizatora nadaje się na doktorat! Jedynym problemem jest implementacja algorytmu, która przerasta naszego bohatera.

Istotą algorytmu jest wykorzystanie istniejących improwizacji do komponowania nowych. Każda improwizacja jest na jakiś temat, czyli pasuje do pewnego ciągu akordów. Algorytm Improwizatora dostosowuje improwizację pasującą do jednego ciągu akordów aby pasowała do innego ciągu akordów.

Do zrozumienia algorytmu potrzebne będzie nam kilka pojęć z teorii muzyki.

Po pierwsze, istnieje 12 różnych nut, których normalna kolejność jest następująca:

, , , , , , , , , , ,

Po następuje znowu (kolejność normalna jest "cykliczna"). Nuty, które oznaczamy krzyżykiem () możemy również oznaczyć bemolem () tak jak zostało to podane w nawiasach.

Po drugie, będziemy potrzebowali pojęcia pauzy do oznaczania przerw w improwizacjach. Pauzę będziemy oznaczać znakiem .

Po trzecie, istnieją także różne akordy. Każdy akord ma prymę, która jest dowolną nutą oraz tryb. Jest sześć trybów: , , , , oraz . Na podstawie prymy oraz trybu określamy nuty pasujące do danego akordu. W tym celu dla każdego trybu podajemy jego skalę, czyli zbiór przesunięć nut względem prymy w kolejności normalnej. Na przykład, jeśli prymą jest , a skala , to zbiorem pasujących dźwięków jest . Skale dla wszystkich trybów są następujące:

tryb	skala
	0, 2, 4, 7, 9, 11
	0, 2, 3, 5, 7, 9, 10
	0, 2, 3, 5, 6, 8, 9, 11
	0, 2, 4, 7, 9, 10
	0, 1, 3, 4, 6, 7, 9, 10
	0, 1, 3, 4, 6, 8, 10

Na przykład skalą dla akordu jest (akordy zapisujemy jako prymę i tryb pisane jednym ciągiem).

Improwizacja jest to skończony ciąg nut i/lub pauz.

Dla danej nuty , nuta najbliższa pasująca do akordu to pierwszy element ciągu , , , , , , który pasuje do . Napis oznacza następną po nutę w kolejności normalnej, a poprzednią względem nutę w kolejności normalnej.

Algorytm Improwizatora możemy zapisać w pseudo-kodzie:

Wejście algorytmu:   ciąg akordów P, improwizacja I,
                     długość ciągu akordów m, długość improwizacji n
Wynik algorytmu:     improwizacja J
Zmienne pomocnicze:  liczba całkowita i, liczba całkowita p

 1  J := ciąg długości n składający się z samych pauz
 2  p := 1
 3  for i := 1 to n do begin
 4      if I[i] <> pauza then begin
 5          J[i] := najbliższa I[i] nuta pasująca do P[p]
 6          if i mod 4 = 0 then begin
 7              p := p + 1
 8              if p > m then p := 1
 9          end
10      end
11  end

Zadanie

Należy zaimplementować Algorytm Improwizatora. Twój program powinien:

• wczytać ze standardowego wejścia ciąg akordów oraz improwizację,
• znaleźć - zgodnie z Algorytmem Improwizatora - improwizację pasującą do podanych akordów,
• zapisać wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się liczba , . W drugim wierszu znajduje się wejściowy ciąg akordów, zapisany jako akordów, pooddzielanych pojedynczymi odstępami. W trzecim wierszu znajduje się liczba , . W czwartym wierszu znajduje się nut i/lub pauz, pooddzielanych pojedynczymi odstępami. Nuty te stanowią wejściową improwizację.

Wyjście

Wyjście powinno składać się z jednego wiersza, zawierającego nut i/lub pauz, stanowiących wynikową improwizację, pooddzielanych pojedynczymi odstępami.

Uwaga. Wypisując nutę posiadającą dwa oznaczenia należy użyć oznaczenia zgodnego z akordem P[p] w linii 5 pseudokodu algorytmu: jeśli pryma akordu ma bemol, to należy użyć oznaczenia z bemolem. W przeciwnym przypadku należy użyć oznaczenia z krzyżykiem.

Przykład

2
Gb7 Bb7
12
C C# D D# E F _ F# G _ G# A

Db Db Eb Eb F F _ G Ab _ Ab Bb

Autor zadania: Bolek Szewczyk.