Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WCW - Elementar, meu caro Watson!

Watson, Crick e Wilkins receberam em 1962 o prêmio Nobel de Medicina especialmente pelo seu trabalho que resultou na descoberta da estrutura das moléculas do DNA e na sua importância na transmissão de informações entre as gerações de seres vivos. Watson e Crick publicaram na revista "Nature" em 1953 o artigo em que mostravam que a molécula de DNA apresentava uma estrutura de dupla hélice. O artigo assume enorme importância nos dias de hoje, especialmente depois dos vários avanços na área.

Muitas pesquisas têm sido feitas na área de Bioinformática ligadas à descoberta da seqüência de bases que compõem as moléculas de DNA dos vários seres vivos. Em especial, a estrutura destas moléculas tem sido usada para compor teorias de como os seres vivos evoluíram e quais têm ancestrais comuns. Acredita-se que os seres vivos presentes hoje no planeta podem descender de ancestrais comuns, sendo que as modificações nos seus respectivos DNAs são devidas a fenômenos de mutação ocorridos durante a evolução. Muitos biólogos acreditam no princípio da parcimônia, que diz que o número destas mutações deve ser o mínimo possível, uma vez que a Natureza busca, de certa forma, o caminho "mais barato" para a modificação desejada.

Sua tarefa neste problema é auxiliar os pesquisadores na tarefa de determinar se duas seqüências de DNA podem ter um ancestral comum. Considere dadas duas seqüências (podemos imaginar como seqüências de números inteiros). O seu objetivo é determinar o menor número de trocas de elementos de uma das seqüências (os elementos não precisam estar em posições adjacentes na seqüência) que leva uma das seqüências na outra. Observe que podemos considerar uma das seqüências fixa (por exemplo, em ordem crescente), dessa forma buscamos o número mínimo de tais trocas que ordena a seqüência dada.

Entrada

A primeira linha da entrada possui um inteiro T que indica o número de instâncias. A primeira linha de cada instância possui um inteiro N (1 ≤ N ≤ 10000) indicando o número de inteiros na seqüência. A segunda linha contém uma permutação dos inteiros 1, 2, .., N separados por espaço.

Saída

Para cada instância imprima uma linha contendo o número mínimo de tais trocas que ordena a seqüência dada.

Exemplo de entrada
2
5
2 3 4 5 1
5
2 1 4 5 3

Exemplo de saída
4
3


Adicionado por:Wanderley Guimarăes
Data:2008-10-01
Tempo limite:0.242s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2016-05-07 15:02:48
É só não querer complicar as coisas.
2015-10-07 06:10:52 Leandro Tk
Pode ser interessante usar merge sort, e contar o número de swaps.
2015-09-11 05:46:21
É um absurdo como o java é custoso no Spoj. Praticamente desistindo dele ( claro que não ). Estou usando o melhor algoritmo ( Cormen ), e ainda assim dá "limite excedido" . Infelizmente terei que apelar para o C. =(

2013-10-28 02:58:28 Chinês da Cadeira
Pq vcs naum vao trabalhar ao inves de ficar na frente do pc? Cambada de vagabundos
2013-10-22 15:16:28 Adriano CPTM [USJT]
O inteiro "T" é infinito?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.