Sliding wardrobe#7886
Vasya recently purchased a new sliding wardrobe with exactly identical sections and doors, arranged in rows. Each door is the size of a section, meaning one door covers exactly one section. This peculiar setup led Vasya to wonder: "How many moves are required to ensure all filled sections are covered, while the others remain open?" In a single move, Vasya can slide any door left or right by section, provided the adjacent position in that row is unoccupied. A section is considered covered if at least one door is over it, and open otherwise.
Develop a program that, given the initial placement of the doors and the status of each section (filled or not), calculates the minimum number of moves Vasya needs to make all filled sections covered and the others open.
The first line of the input contains a single natural number (P \leq 3) – the number of input data sets. Each data set consists of four lines. The first line contains numbers and (1 \leq N \leq 200,\ 0 \leq M \leq 2N) – the number of sections and the number of doors, respectively. The next two lines each contain numbers, indicating the presence of a door at each position ( – no, – yes). The last line for the given set contains numbers, each indicating whether the corresponding section is filled ( – no, – yes).
Output numbers – the minimum number of moves Vasya needs for each set of input data. If achieving the desired arrangement is impossible for a particular set, output for that set.
Beispiel 1
Additional conditions for the tests are as follows:
of tests: N \leq 5
of tests: there are no doors in the second row
of tests: N \leq 50, with at most two doors in the second row
of tests: N \leq 50