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