I need to call my friends but the buttons of my cordless phone are not working properly. The only buttons I can press are [Up], [Down] and [Call]. [Up] and [Down] can be used to navigate in my recent calls and [Call] can be used to call the selected name. My phone has a list that holds
N recent calls, and I know that all the friends I need to call are in this list.
You'll receive a number
N and a list of names
Nis the number of recent calls my phone can remember;
Lhas the names in the order I need to call.
You must output the number of button presses I need to make in an optimal arrangement of the recent call list.
Calling Anna, Bob and then Anna again. With a recent calls list of size 5.
5 Anna Bob Anna
Possible optimal arrangement:
Anna, Foo, Bar, Foobar, Bob
5 # Key presses: [Call] Anna, [Up] + [Call] Bob, [Down] + [Call] Anna
More test cases:
Input: 5, Anna, Bob, Carl Output: 5 Input: 5, Anna, Bob, Carl, Anna Output: 8 Input: 5, A, B, C, D, E, A Output: 11 Input: 6, A, B, C, D, E, A Output: 12 Input: 4, A, B, C, B, A Output: 10
- Your cursor will always start in the first position of the list;
- You can take the input
Lfrom any source: keyboard, parameters, file, etc;
- The names in the list can be in any reasonable format such as: strings, integers, chars;
- When you reach the end of the recent calls list and presses [Down] again, your cursor wraps around. The same happens when you're at the begining of the recent calls list and presses [Up];
- When you call someone, that person's name will be moved to the first position of the recent calls list and the rest will be pushed down;
- When you call someone, your cursor will be moved to the first position;
- A friend name cannot appear more than once in the recent calls list;
- You can fill your recent calls list with dummy entries (see example);
- The number of friends to call will not be greater than