eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фрактал

Фрактал

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Есть квадрат размера 1×1 окрашенный либо в черный, либо в белый цвет. Горизонтальными и вертикальными линиями этот квадрат разбивается на N^2 одинаковых квадратов меньшего размера, каждый из которых окрашивается в черный или белый цвет, согласно некоторому заданному шаблону. Далее к каждому из полученных маленьких квадратов применяется такая же операция - снова происходит разбиение квадрата на еще более мелкие квадратики, каждый из которых окрашивается по шаблону, который определяется цветом разбиваемого квадрата. Черные квадраты перекрашиваются по одному шаблону, а белые - по другому. Операции разбиения квадратов и перекрашивания его составных частей выполняются K раз.

Напишите программу, которая найдет суммарную площадь чёрных квадратов.

Входные данные

В первой строке находится два целых числа: размер разбиения N и количество операций разбиения K (1N10, 0K10^9). Во второй строке задается цвет исходного квадрата: 0 обозначает черный цвет, 1 - белый. Следующий блок из N строк содержит по N чисел описывает шаблон для перекрашивания черных квадратов после разбиения. Аналогичным образом, следующий блок из N строк описывает шаблон, по которому перекрашиваются белые квадраты.

Выходные данные

В единственную строку выведите одно число - сумму площадей черных квадратов с точностью не менее 10^{-7}.

Примечание: В приведенном примере последовательность разбиений и перекрашиваний будет такой:

На получившемся рисунке черная часть состоит из 11 квадратиков c длиной стороны 0.25.

Пример

Входные данные #1
2 0
0
1 0
0 1
0 1
0 0
Выходные данные #1
1.00000000
Автор Лунев А.А.
Источник Донецкая областная олимпиада среди школьников 2011