codeforces-scrape

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

371A.md (2196B)


      1 Source: https://codeforces.com/problemset/problem/371/A
      2 
      3 A. K-Periodic Array
      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 This task will exclusively concentrate only on the arrays where all elements equal 1 and/or 2.
     22 
     23 Array *a* is *k*-period if its length is divisible by *k* and there is such array *b* of length *k*, that *a* is represented by array *b* written exactly ![](https://espresso.codeforces.com/e8f8616e518b67af73332593c4c73ae9f207dc04.png) times consecutively. In other words, array *a* is *k*-periodic, if it has period of length *k*.
     24 
     25 For example, any array is *n*-periodic, where *n* is the array length. Array [2, 1, 2, 1, 2, 1] is at the same time 2-periodic and 6-periodic and array [1, 2, 1, 1, 2, 1, 1, 2, 1] is at the same time 3-periodic and 9-periodic.
     26 
     27 For the given array *a*, consisting only of numbers one and two, find the minimum number of elements to change to make the array *k*-periodic. If the array already is *k*-periodic, then the required value equals 0.
     28 
     29 Input
     30 
     31 The first line of the input contains a pair of integers *n*, *k* (1 ≤ *k* ≤ *n* ≤ 100), where *n* is the length of the array and the value *n* is divisible by *k*. The second line contains the sequence of elements of the given array *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 2), *a**i* is the *i*-th element of the array.
     32 
     33 Output
     34 
     35 Print the minimum number of array elements we need to change to make the array *k*-periodic. If the array already is *k*-periodic, then print 0.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 6 2  
     43 2 1 2 2 2 1
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 1
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 8 4  
     56 1 1 2 1 1 1 2 1
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 0
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 9 3  
     69 2 1 1 1 2 1 1 1 2
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 3
     76 ```
     77 
     78 Note
     79 
     80 In the first sample it is enough to change the fourth element from 2 to 1, then the array changes to [2, 1, 2, 1, 2, 1].
     81 
     82 In the second sample, the given array already is 4-periodic.
     83 
     84 In the third sample it is enough to replace each occurrence of number two by number one. In this case the array will look as [1, 1, 1, 1, 1, 1, 1, 1, 1] — this array is simultaneously 1-, 3- and 9-periodic.