codeforces-scrape

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

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.