Аппликатура :: Олимпиады :: Сайт Андрея Зайчикова

Сайт Андрея Зайчикова

Среда, 23 Июля 2003г.

.:Навигатор

.:Информация

Аппликатура

Одна из проблем при игре на фортепьяно -- выбор хорошей аппликатуры, то есть определение для каждого звука мелодии (клавиши инструмента) пальца руки, которым эту ноту лучше всего сыграть в данном месте мелодии.
Пронумеруем пальцы пианиста слева направо натуральными числами от 1 до P, клавиши инструмента также пронумеруем слева направо натуральными числами от 1 до K. Тогда запись звуков мелодии можно представить в виде последовательности N номеров клавиш, которые следует нажимать для ее исполнения, где N -- длина мелодии.
Пусть для каждой пары пальцев с номерами i и j заданы целые числа a_{ij} и b_{ij}, такие, что если палец i нажимает клавишу X, то следующей клавишей пальцем j может быть нажата лишь клавиша из диапазона [X+a_{ij}, X+b_{ij}]. Этот набор чисел a_{ij}, b_{ij}, 1<=i<=P, 1<=j<=P, зависит от особенностей пианиста и его исполнительской техники. Заметим, что не каждая мелодия может быть сыграна конкретным пианистом при указанных выше ограничениях.
Hазовем перекладыванием пальцев ситуацию, когда для двух последовательно исполняемых нот мелодии клавиша с большим номером нажимается пальцем с меньшим номером. Требуется написать программу, которая для заданной мелодии определяет аппликатуру с наименьшим количеством перекладываний пальцев.

Ввод:
В первой строке входного файла содержится число P -- количество пальцев у пианиста (1<=P<=20). Во второй строке записано число K -- количество клавиш у инструмента (1<=K<=10000). В третьей строке указаны целые числа a_{11} b_{11} a_{12} b_{12} ... a_{1P} b_{1P} a_{21} b_{21} a_{22} b_{22} ... a_{2P} b_{2P} ... a_{P1} b_{P1} a_{P2} b_{P2} ... a_{PP} b_{PP}, разделенные пробелами (-K <= a_{ij} <= b_{ij} <= K). В четвертой строке находится число N -- длина мелодии (1<=N<=1000). Пятая строка содержит N чисел X_1 X_2 X_3 ... X_N -- последовательность разделенных пробелами номеров клавиш для исполнения мелодии.

Вывод:
В первой строке выходного файла должно содержаться либо число L -- количество перекладываний пальцев в оптимальной аппликатуре, либо число -1 при невозможности сыграть мелодию. Вторая строка при наличии решения должна содержать N чисел Y_1 ... Y_N -- последовательность разделенных пробелами номеров пальцев при исполнении мелодии.

Пример:

3
10
0 0 -2 -2 -5 1 2 3 8 10 0 1 2 10 -2 -2 -1 -1
9
4 5 7 7 7 6 8 7 5

Результат:

3
2 3 1 1 3 3 1 3 2

.:Реклама

Об авторе | Юмор | Карта сайта | Поиск | Web мастеру