eolymp
bolt
Try our new interface for solving problems
Məsələlər

Фрактал

Фрактал

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

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

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

Nümunə

Giriş verilənləri #1
2 0
0
1 0
0 1
0 1
0 0
Çıxış verilənləri #1
1.00000000
Müəllif Лунев А.А.
Mənbə Донецкая областная олимпиада среди школьников 2011