codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

36B.md (1944B)


      1 Source: https://codeforces.com/problemset/problem/36/B
      2 
      3 B. Fractal
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 64 megabytes
     12 
     13 input
     14 
     15 input.txt
     16 
     17 output
     18 
     19 output.txt
     20 
     21 Ever since Kalevitch, a famous Berland abstractionist, heard of fractals, he made them the main topic of his canvases. Every morning the artist takes a piece of graph paper and starts with making a model of his future canvas. He takes a square as big as *n* × *n* squares and paints some of them black. Then he takes a clean square piece of paper and paints the fractal using the following algorithm:
     22 
     23 Step 1. The paper is divided into *n*2 identical squares and some of them are painted black according to the model.
     24 
     25 Step 2. Every square that remains white is divided into *n*2 smaller squares and some of them are painted black according to the model.
     26 
     27 Every following step repeats step 2.
     28 
     29  ![](https://espresso.codeforces.com/f55fec8483a8140526ea740b876c0ef5ee004e60.gif) 
     30 
     31 Unfortunately, this tiresome work demands too much time from the painting genius. Kalevitch has been dreaming of making the process automatic to move to making 3D or even 4D fractals.
     32 
     33 Input
     34 
     35 The first line contains integers *n* and *k* (2 ≤ *n* ≤ 3, 1 ≤ *k* ≤ 5), where *k* is the amount of steps of the algorithm. Each of the following *n* lines contains *n* symbols that determine the model. Symbol «.» stands for a white square, whereas «*» stands for a black one. It is guaranteed that the model has at least one white square.
     36 
     37 Output
     38 
     39 Output a matrix *n**k* × *n**k* which is what a picture should look like after *k* steps of the algorithm.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 2 3  
     47 .*  
     48 ..
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 .*******  
     55 ..******  
     56 .*.*****  
     57 ....****  
     58 .***.***  
     59 ..**..**  
     60 .*.*.*.*  
     61 ........
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 3 2  
     68 .*.  
     69 ***  
     70 .*.
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 .*.***.*.  
     77 *********  
     78 .*.***.*.  
     79 *********  
     80 *********  
     81 *********  
     82 .*.***.*.  
     83 *********  
     84 .*.***.*.
     85 ```