Muszę zadzwonić do znajomych, ale przyciski mojego telefonu bezprzewodowego nie działają poprawnie. Jedynymi przyciskami, które mogę nacisnąć, są [W górę], [W dół] i [Zadzwoń]. Przyciski [W górę] i [W dół] mogą być używane do nawigacji w moich ostatnich połączeniach, a [Połączenie] może być używany do wybierania wybranej nazwy. Mój telefon ma listę Nostatnich połączeń i wiem, że wszyscy przyjaciele, do których muszę zadzwonić, są na tej liście.

Zadanie:

Otrzymasz numer Ni listę nazwisk L:

• N to liczba ostatnich połączeń, które mój telefon może zapamiętać;
• L ma nazwy w kolejności, w której muszę zadzwonić.

Musisz podać liczbę naciśnięć przycisków, które muszę wykonać w optymalny sposób na liście ostatnich połączeń.

Przykład:

-> Wejście:

Dzwonię do Anny, Boba, a potem znów do Anny. Z listą ostatnich połączeń o rozmiarze 5.

5
Anna
Bob
Anna

-> Wyjście:

Możliwe optymalne ustawienie: Anna, Foo, Bar, Foobar, Bob

5    # Key presses: [Call] Anna, [Up] + [Call] Bob, [Down] + [Call] Anna

Więcej przypadków testowych:

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

Zasady:

• Kursor zawsze zaczyna się od pierwszej pozycji listy;
• Możesz pobrać dane wejściowe Ni Lz dowolnego źródła: klawiatury, parametrów, pliku itp .;
• Nazwy na liście mogą mieć dowolny rozsądny format, taki jak: ciągi, liczby całkowite, znaki;
• Po osiągnięciu końca listy ostatnich połączeń i ponownym naciśnięciu przycisku [W dół] kursor się zawija. To samo dzieje się, gdy jesteś na początku listy ostatnich połączeń i naciskasz [W górę];
• Kiedy zadzwonisz do kogoś, nazwisko tej osoby zostanie przeniesione na pierwszą pozycję listy ostatnich połączeń, a reszta zostanie przesunięta w dół;
• Kiedy do kogoś zadzwonisz, kursor zostanie przesunięty na pierwszą pozycję;
• Imię znajomego nie może pojawić się więcej niż raz na liście ostatnich połączeń;
• Możesz wypełnić listę ostatnich połączeń fałszywymi wpisami (patrz przykład);
• Liczba znajomych, do których można zadzwonić, nie będzie większa niż N.

Ruby , 97 95 94 bajtów

->n,a{r=a.size;1.upto(r-1){|i|r+=[p=a[(a[0,i].rindex(a[i])||i-2)+1...i].uniq.size,n-p].min};r}

Wypróbuj online!

W optymalnym układzie pierwsze imię zajmie jedno naciśnięcie ( Call). Nazwy, które nie zostały jeszcze wywołane, wymagają dwóch naciśnięć ( Up Call) i nazw, które mają różne liczby, w zależności od tego, ile innych niepowtarzalnych nazw zostało wywołanych od tego czasu i czy umieszcza je bliżej górnej lub dolnej części listy.

Myślę, że jest to strategia podobna lub identyczna do strategii WaffleCohn.

Python 3 , 195 185 164 bajtów

-4 bajty dzięki @notjagan
-27 bajtów dzięki @FelipeNardiBatista

lambda n,l:min(g([*x],l,n)for x in permutations(range(n)))
def g(x,l,n,r=0):
 for p in l:a=x.index(p);x=[x.pop(a)]+x;r-=~min(a,n-a)
 return r
from itertools import*

Wypróbuj online!

L jest traktowany jako lista liczb całkowitych z [0, N)

JavaScript (SpiderMonkey) , 213 143 bajtów

(N,L)=>L.reduce((t,v,i)=>{x=0,a=[v]
for(j=i;j-->=0&!~a.indexOf(L[j]);x++)a+=L[j]+","
return i?t+((x=L.indexOf(v)-i?x:1)<N-x?x:N-x):t},L.length)

Wypróbuj online!

Generuje optymalne ustawienie podanych nazw, a następnie zlicza liczbę naciśnięć klawiszy.

Pominięto generację i właśnie policzyłem, ile naciśnięć klawiszy zabrałoby każdą nazwę w optymalnym układzie