Joãozinho não era um garoto comum. Enquanto seus amigos organizavam figurinhas por times, ele criava sistemas de senhas com uma lógica que só existia em sua cabeça. Para qualquer outra pessoa, sua lista de senhas parecia uma bagunça completa.
Seu irmão mais velho, Jhon, um mestre das travessuras, encontrou a lista e, ao lado, um bilhete: “Senha Chave de hoje: [um número]”. Jhon sorriu e teve uma ideia:
“A ordem do Joãozinho parece aleatória, mas sei que há um padrão escondido. Para criar a pegadinha perfeita, preciso primeiro decifrar a lógica dele e depois criar a minha própria bagunça sistemática!”
Naquela tarde, Jhon se preparou para executar seu plano. Ele usaria a ordem crescente como uma “chave-mestra” para decifrar a posição da senha do dia e, com isso, criar uma nova sequência ainda mais confusa a partir da lista original.
Seu objetivo é criar o algoritmo que Jhon usou para reorganizar as senhas de Joãozinho. O programa deve primeiro encontrar a “chave” da pegadinha (o índice da Senha Chave na lista ordenada) e depois aplicar a transformação na lista original.
A entrada é composta por duas linhas.
A
primeira linha contém N (o total de senhas) e
C (a Senha Chave).
A segunda linha
contém as N senhas na ordem original de Joãozinho.
A saída também terá duas linhas: o índice secreto e a nova
lista.
O algoritmo de busca do índice do elemento em uma lista tem que ser mais eficiente do que O(N)
Entrada
5 30
10 80 5 95 30
Saída
2
5 95 30 10 80
Entrada
7 42
99 10 4 8 42 15 23
Saída
5
15 23 99 10 4 8 42
Entrada
4 100
10 100 5 50
Saída
3
50 10 100 5