Walk Only the Lightbulb Path
InterviewTime limit1sMemory limit512 MB
Arrange N binary strings in some order so the concatenation has the fewest adjacent 01 or 10 transitions, and print that minimum count; N is at most 10.
- Level
Medium6 of 10
- Topics
- Greedy, Sorting, Brute force, Implementation
- Solved
- No attempts yet
Problem
The Sunlin students admire ✨pop star super social butterfly Teacher Yewon✨. Not being able to see their teacher during vacation is unbearable! So on the day of the vacation ceremony, the students prepared an enormous event called 💡Walk Only the Lightbulb Path💡.
💡💡💡💡👨🏫💡💡💡💡
Unknown to anyone, Sunlin's science lab actually holds N bundles of lightbulbs, each with its bulbs strung in a line. The students decided to join these bundles into one long lightbulb path. But some bundles contained bulbs that would not light up, and once the bulbs were joined in a line, lit and unlit bulbs alternated, so the path was not pretty.
So the students want to arrange the bundles to make the lightbulb path as pretty as possible. A lightbulb path is prettiest when the number of times the bulb state changes is smallest. Writing a lit bulb as 1 and an unlit bulb as 0, this means 01 or 10 must appear as few times as possible along the path.
For example, suppose the bundles (1011) and (1000) are to be joined. Then joining them in the order (10111000) is prettier than joining them in the order (10001011). The first changes the bulb state 3 times, and the second changes it 4 times.
Suddenly Sehan says he will write code to compute this.
Let us decorate the lightbulb path prettily together with Sehan!
Input
The first line gives the number of lightbulb bundles N. (1 ≤ N ≤ 10)
From the second line, N lines follow, each giving a string that represents the state of one lightbulb bundle. The string consists only of 0 and 1, where 0 means an unlit bulb and 1 means a lit bulb.
The string has length between 1 and 100.
Output
Print the number of times the bulb state changes when the bundles are arranged in the prettiest way.