Problem 3: Moo Sick [Rob Seay]
Каждый знает, что коровы любят слушать музыку. Великий композитор Мууцарт однажды открыл, некоторые последовательности нот действуют на коров угнетающе. Поэтому их нужно избегать во всех композициях для коров.
Фермер Джон, не знакомый с этим фактом, решил проигрывать свою любимую песню через громкоговорители в амбаре. Ваша задача – определить все угнетающие последовательности нот в его песне, чтобы оценить, насколько она вредна для коров.
Песня, которую озвучивает ФД, представляет собой последовательность из N нот, каждая в диапазоне от 1 до 88. Угнетающая последовательность состоит из С (1<=C<=10) различных нот, также целых чисел от 1 до 88. Однако, если ноты транспонированы (увеличены или уменьшены на одну и ту же величину), или переупорядочены, то эта последовательность нот все равно остается угнетающей. Например, если «4 6 7» - угнетающая последовательность нот, то последовательности «3 5 6» (транспонирована на -1), «6 8 9» (транспонирована на +2), «6 4 7» (переупорядочена), «5 3 6» (транспонирована и переупорядочена) , также являются угнетающими.
Таким образом, угнетающей последовательностью нот являются C подряд идущих нот, удовлетворяющих вышеописанному критерию. Поэтому она однозначно определяется своим стартовым положением в песне. Определите стартовое положение всех угнетающих последовательностей.
PROBLEM NAME: moosick
Формат входных данных
* Строка 1: Одно целое число: N.
* Строки 2..1+N: N нот в песне ФД, по одной ноте на строке.
* Строка 2+N: Одно целое число: C.
* Строки 3+N..2+N+C: C нот определяющих угнетающую последовательность. Все транспозиции и переупорядочивания также угнетающие последовательности.
Формат выходных данных
* Строка 1: Количество, K, угнетающих последовательностей, которые есть в песне ФД. Заметим, что различные экземпляры угнетающих последовтельностей могут перекрываться друг с другом.
* Строки 2..1+K: Каждая строка указывает начальную позицию угнетающей последовательности (1 – первая нота в песне ФД, N - последняя). Эти начальные позиции должны указываться в порядке возрастания.
Примечание
Две угнетающих последовательности встретились в песне ФД и они перекрываются в одной ноте. Первая – 8,5,7 (транспонирована на 1 и переупорядочена), начинается с позиции 2, а вторая 7,9,10 (транспонирована на 3) , начинается с позиции 4.