Задача A. Миша и негатив ≡

Условие

Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив бинарного черно-белого изображения.

Бинарное черно-белое изображение — это прямоугольник, состоящий из пикселей, каждый из которых может быть либо черным, либо белым. Негатив такого изображения получается путем замены каждого черного пикселя на белый, а каждого белого пикселя — на черный.

Миша, как начинающий программист, написал свою программу с ошибкой, поэтому в результате ее исполнения мог получаться некорректный негатив. Для того чтобы оценить уровень несоответствия получаемого негатива исходному изображению, Миша начал тестировать свою программу.

В качестве входных данных он использовал исходные изображения. Сформированные программой негативы он начал тщательно анализировать, каждый раз определяя число пикселей негатива, которые получены с ошибкой.

Требуется написать программу, которая в качестве входных данных использует исходное бинарное черно-белое изображение и полученный Мишиной программой негатив, и на основе этого определяет количество пикселей, в которых допущена ошибка.

Формат входного файла

Первая строка входного файла содержит целые числа n и m — высоту и ширину исходного изображения (в пикселях).

Последующие n строк содержат описание исходного изображения. Каждая строка состоит из m символов B и W. Символ B соответствует черному пикселю, а символ W — белому.

Далее следует пустая строка, а после нее — описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.

Формат выходного файла

В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.

Ограничения

1 ≤ n, m ≤ 100

Примеры тестов

3 4
WBBW
BBBB
WBBW

BWWW
WWWB
BWWB

2

2 2
BW
BB

WW
BW

2

Задача B. Треугольник Максима ≡

Условие

С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент — треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.

У Максима есть профессиональный музыкальный тюнер, с помощью которого можно проигрывать ноту с заданной частотой. Максим действует следующим образом: он включает на тюнере ноты с разными частотами и для каждой ноты на слух определяет, ближе или дальше она к издаваемому треугольником звуку, чем предыдущая нота. Поскольку слух у Максима абсолютный, он определяет это всегда абсолютно верно.

Вам Максим показал запись, в которой приведена последовательность частот, выставляемых им на тюнере, и про каждую ноту, начиная со второй, записано — ближе или дальше она к звуку треугольника, чем предыдущая нота. Заранее известно, что частота звучания треугольника Максима составляет не менее 30 герц и не более 4000 герц.

Требуется написать программу, которая определяет, в каком интервале может находиться частота звучания треугольника.

Система оценивания

Решения, правильно работающие только для целых чисел f_i, имеющих одинаковую четность, будут оцениваться из 40 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n — количество нот, которые воспроизводил Максим с помощью тюнера. Последующие n строк содержат записи Максима, причем каждая строка содержит две компоненты: вещественное число f_i — частоту, выставленную на тюнере, в герцах, и слово closer или слово further для каждой частоты, кроме первой.

Слово closer означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |f_i − f_треуг.| < |f_i − 1 − f_треуг.|.

Слово further означает, что частота данной ноты дальше, чем предыдущая.

Если оказалось, что очередная нота так же близка к звуку треугольника, как и предыдущая нота, то Максим мог записать любое из двух указанных выше слов.

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

Формат выходного файла

В выходной файл необходимо вывести через пробел два вещественных числа с точностью не менее 10^− 8 — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом.

Ограничения

2 ≤ n ≤ 1000, 30 ≤ f_i ≤ 4000

Примеры тестов

3
440
220 closer
300 further

30.0 260.0

4
554
880 further
440 closer
622 closer
	

531.0 660.0

Задача C. Производство деталей ≡

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

Формат входного файла

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂… p_n, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

Формат выходного файла

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Ограничения

1 ≤ n ≤ 100000, 1 ≤ p_i ≤ 10⁹

Сумма всех чисел k_i не превосходит 200000.

Примеры тестов

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

4
2 3 4 5
2 3 2
1 3
0
2 1 3

9 3
3 2 1

Задача D. Новое слово в рекламе ≡

Условие

В наши дни предоставление поверхностей заборов и стен промышленных зданий рекламодателям — уже не оригинальный способ получить дополнительный заработок, а нечто само собой разумеющееся.

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером 1 × 1 × L, на одной из сторон которого есть место для рекламы — пространство размера 1 × L, в которое можно вписать ровно L букв латинского алфавита.

К сожалению, иногда сделки у компании срывались, и заранее подготовленные блоки с рекламой отправлялись на склад. Со временем там скопилось приличное количество блоков различных типов (блоки разных типов отличаются друг от друга только надписью), поэтому было решено использовать их вторично.

Была предложена следующая идея: если поставить несколько блоков друг на друга и закрасить ненужные буквы, то, читая сверху вниз и слева направо, можно будет прочитать какой-нибудь другой текст, как показано на рисунке.

Таким образом, можно получить рекламную надпись для нового клиента. При этом из эстетических соображений при прочтении конечной надписи разрывы в виде закрашенных букв недопустимы.

После того, как некоторое число K блоков, каждый из которых имеет длину L, поставили друг на друга, получилась прямоугольная таблица размером K × L, в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображенном на рисунке, в результате этого процесса получилась бы строка TOEIIZENITKN.

Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока TOEIIZENITKN.

Требуется написать программу, которая будет определять, какое минимальное количество блоков надо использовать, чтобы получить рекламную надпись, необходимую заказчику. При этом можно считать, что на складе блоков каждого типа неограниченно много.

Система оценивания

Решения, правильно работающие только для N ≤ 5, будут оцениваться из 50 баллов.

Формат входного файла

Первая строка входного файла входного файла содержит два натуральных числа N и L — число различных типов блоков на складе и длина каждого блока соответственно. Последующие N строк содержат по одной записи длиной L, состоящей из строчных латинских букв — надписи на блоках соответствующего типа. Надписи на блоках разных типов не совпадают.

Последняя строка входного файла содержит новую рекламную надпись s — строку, состоящую только из строчных латинских букв. Можно считать, что на складе находится неограниченное число блоков каждого типа.

Формат выходного файла

В первой строке выходного файла необходимо вывести натуральное число K — минимальное количество блоков, которое нужно использовать для составления новой рекламы. Следующая строка должна содержать K чисел — номера типов блоков, которые нужно для этого использовать, перечисляя их сверху вниз. Типы блоков нумеруются с единицы в порядке их задания во входном файле.

Если ответов несколько, выведите любой из них. Если решения не существует, выведите в выходной файл число  − 1.

Ограничения

1 ≤ N, L ≤ 100, 1 ≤ |s| ≤ 200

Примеры тестов

3 4
tiet
oink
ezin
zenit

3
1 2 3

2 11
sillysample
happysample
sam

1
2

2 3
baa
aab
bb

2
2 2

2 3
aaa
bbb
cc

-1