## DMOPC '18 Contest 1 P6 - Sorting

View as PDF

Points: 20 (partial)
Time limit: 1.8s
Java 4.5s
Python 4.5s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Harold has been misbehaving and now his teacher has given him detention! The teacher has written numbers in their binary representation on the chalkboard. These binary numbers are all written with exactly bits (leading zeroes are allowed) and are written in a list. The teacher tells Harold,

You can leave once the -bit binary numbers are sorted from least to greatest.

Harold, being mischievous, decides that as long as there are -bit binary numbers in sorted order, then he is done, even if they are not the original numbers. He will change some of the characters so that the resulting numbers are sorted. He can only change 0s to 1s and 1s to 0s. He is not allowed to add more characters or delete existing characters.

Harold is also lazy, so he wants to change as few characters as possible. Help him find the least number of changes he needs.

#### Input Specification

The first line contains two space-separated integers, and .
Lines each contain a single string of exactly characters, either 0 or 1. The string on line represents the number in the list.

#### Output Specification

Output a single integer, the minimum number of changes required to sort the list.

#### Sample Input 1

4 3
111
110
000
100

#### Sample Output 1

3

#### Explanation for Sample 1

Harold can change the first character of the first number, the second character of the second number, and the first character of the third number to get the sorted list.

011
100
100
100

#### Sample Input 2

10 5
10010
11101
01011
01000
11100
00110
00110
10001
01101
01000

#### Sample Output 2

10