codeforces-scrape

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

426B.md (1814B)


      1 Source: https://codeforces.com/problemset/problem/426/B
      2 
      3 B. Sereja and Mirroring
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Let's assume that we are given a matrix *b* of size *x* × *y*, let's determine the operation of mirroring matrix *b*. The mirroring of matrix *b* is a 2*x* × *y* matrix *c* which has the following properties:
     22 
     23 * the upper half of matrix *c* (rows with numbers from 1 to *x*) exactly matches *b*;
     24 * the lower half of matrix *c* (rows with numbers from *x* + 1 to 2*x*) is symmetric to the upper one; the symmetry line is the line that separates two halves (the line that goes in the middle, between rows *x* and *x* + 1).
     25 
     26 Sereja has an *n* × *m* matrix *a*. He wants to find such matrix *b*, that it can be transformed into matrix *a*, if we'll perform on it several (possibly zero) mirrorings. What minimum number of rows can such matrix contain?
     27 
     28 Input
     29 
     30 The first line contains two integers, *n* and *m* (1 ≤ *n*, *m* ≤ 100). Each of the next *n* lines contains *m* integers — the elements of matrix *a*. The *i*-th line contains integers *a**i*1, *a**i*2, ..., *a**im* (0 ≤ *a**ij* ≤ 1) — the *i*-th row of the matrix *a*.
     31 
     32 Output
     33 
     34 In the single line, print the answer to the problem — the minimum number of rows of matrix *b*.
     35 
     36 Examples
     37 
     38 Input
     39 
     40 ```
     41 4 3  
     42 0 0 1  
     43 1 1 0  
     44 1 1 0  
     45 0 0 1
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 2
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 3 3  
     58 0 0 0  
     59 0 0 0  
     60 0 0 0
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 3
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 8 1  
     73 0  
     74 1  
     75 1  
     76 0  
     77 0  
     78 1  
     79 1  
     80 0
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 2
     87 ```
     88 
     89 Note
     90 
     91 In the first test sample the answer is a 2 × 3 matrix *b*:
     92 
     93 ```
     94 001  
     95 110
     96 ```
     97 
     98 If we perform a mirroring operation with this matrix, we get the matrix *a* that is given in the input:
     99 
    100 ```
    101 001  
    102 110  
    103 110  
    104 001
    105 ```