Preciso ligar para meus amigos, mas os botões do meu telefone sem fio não estão funcionando corretamente. Os únicos botões que posso pressionar são [Up], [Down] e [Call]. [Para cima] e [Para baixo] podem ser usados ​​para navegar nas minhas chamadas recentes e [Ligar] para o nome selecionado. Meu telefone possui uma lista que mantém Nligações recentes e sei que todos os amigos para os quais preciso ligar estão nessa lista.

Tarefa:

Você receberá um número Ne uma lista de nomes L:

• N é o número de chamadas recentes que meu telefone pode lembrar;
• L tem os nomes na ordem em que preciso ligar.

Você deve imprimir o número de pressionamentos de botão que preciso fazer em um arranjo ideal da lista de chamadas recente.

Exemplo:

-> Entrada:

Chamando Anna, Bob e depois Anna novamente. Com uma lista de chamadas recentes do tamanho 5.

5
Anna
Bob
Anna

-> Saída:

Possível arranjo ideal: Anna, Foo, Bar, Foobar, Bob

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

Mais casos de teste:

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

Regras:

• Seu cursor sempre inicia na primeira posição da lista;
• Você pode pegar a entrada Ne Lde qualquer fonte: teclado, parâmetros, arquivo, etc;
• Os nomes na lista podem estar em qualquer formato razoável, como: seqüências de caracteres, números inteiros, caracteres;
• Quando você chega ao final da lista de chamadas recentes e pressiona [Baixo] novamente, seu cursor gira em torno. O mesmo acontece quando você está no início da lista de chamadas recentes e pressiona [Para cima];
• Quando você liga para alguém, o nome dessa pessoa é movido para a primeira posição da lista de chamadas recentes e o restante é pressionado;
• Quando você liga para alguém, seu cursor é movido para a primeira posição;
• O nome de um amigo não pode aparecer mais de uma vez na lista de chamadas recentes;
• Você pode preencher sua lista de chamadas recentes com entradas falsas (veja o exemplo);
• O número de amigos para quem ligar não será maior que N.

Ruby , 97 95 94 bytes

->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}

Experimente online!

Em uma organização ideal, o primeiro nome será pressionado ( Call). Os nomes que ainda não foram chamados levam duas vezes ( Up Call) e os nomes que recebem números variados, dependendo de quantos outros nomes exclusivos foram chamados desde então e se isso os coloca mais perto do topo ou da parte inferior da lista.

Eu acho que essa é uma estratégia semelhante ou idêntica à da WaffleCohn.

Python 3 , 195 185 164 bytes

-4 bytes graças a @notjagan
-27 bytes graças a @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*

Experimente online!

L é tomado como uma lista de números inteiros de [0, N)

JavaScript (SpiderMonkey) , 213 143 bytes

(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)

Experimente online!

Gera uma organização ideal dos nomes dados e conta o número de pressionamentos de tecla.

Ignorou a geração e contou quantas teclas pressionaria cada nome na organização ideal