838A.md (1783B)
1 Source: https://codeforces.com/problemset/problem/838/A 2 3 A. Binary Blocks 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an image, that can be represented with a 2-d *n* by *m* grid of pixels. Each pixel of the image is either on or off, denoted by the characters "0" or "1", respectively. You would like to compress this image. You want to choose an integer *k* > 1 and split the image into *k* by *k* blocks. If *n* and *m* are not divisible by *k*, the image is padded with only zeros on the right and bottom so that they are divisible by *k*. Each pixel in each individual block must have the same value. The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle (after padding) in order for the image to be compressible for some *k*. More specifically, the steps are to first choose *k*, then the image is padded with zeros, then, we can toggle the pixels so it is compressible for this *k*. The image must be compressible in that state. 22 23 Input 24 25 The first line of input will contain two integers *n*, *m* (2 ≤ *n*, *m* ≤ 2 500), the dimensions of the image. 26 27 The next *n* lines of input will contain a binary string with exactly *m* characters, representing the image. 28 29 Output 30 31 Print a single integer, the minimum number of pixels needed to toggle to make the image compressible. 32 33 Example 34 35 Input 36 37 ``` 38 3 5 39 00100 40 10110 41 11001 42 ``` 43 44 Output 45 46 ``` 47 5 48 ``` 49 50 Note 51 52 We first choose *k* = 2. 53 54 The image is padded as follows: 55 56 ``` 57 001000 58 101100 59 110010 60 000000 61 ``` 62 63 We can toggle the image to look as follows: 64 65 ``` 66 001100 67 001100 68 000000 69 000000 70 ``` 71 72 We can see that this image is compressible for *k* = 2.