Digital TV
Time limit1sMemory limit128 MB
Compute the minimum button presses to move KBS1 to position 1 and KBS2 to position 2 in a channel list using arrow move and swap operations.
- Level
Medium5 of 10
- Topics
- Greedy, Simulation, Array
- Solved
- No attempts yet
Problem
Sang-geun just bought a new digital receiver and wants to make KBS1 the first channel and KBS2 the second channel in his list of available channels. Every channel has a distinct name, and the list always contains both KBS1 and KBS2.
To the left of the list there is an arrow that points at the currently selected channel. Initially the arrow points at the topmost channel. The following four buttons rearrange the list.
- Move the arrow down by one (from channel to ).
- Move the arrow up by one (from channel to ).
- Move the currently selected channel down by one (swap channels and ; the arrow then points at ).
- Move the currently selected channel up by one (swap channels and ; the arrow then points at ).
A button that would move the arrow outside the list is ignored.
You only need to make KBS1 the first channel and KBS2 the second channel; the order of the remaining channels does not matter. Write a program that finds the minimum number of button presses required to achieve this.
Input
The first line contains the number of channels (). Each of the next lines contains one channel name, given in the current list order. Each channel name is at most characters long and consists only of uppercase letters and digits. The input never has KBS1 already in the first position and KBS2 already in the second position at the same time.
Output
Print, on a single line, the minimum number of button presses needed to make KBS1 the first channel and KBS2 the second channel.