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 ```