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

GENERAL - O general

A Segunda Guerra Mundial foi o confronto que causou mais vítimas na história da humanidade. Iniciando-se em 1939, ela opôs, de um lado, o Eixo, formado por Alemanha, Itália e Japão, e de outro os Aliados, que contavam, entre outros, com China, França, Inglaterra, Estados Unidos e Rússia. O Brasil se integrou aos Aliados em 1943, grupo esse que saiu vencedor em 1945.

Entre os principais nomes da guerra estavam Adolph Hitler, Benito Mussolini, Joseph Stalin e Winston Churchill. Porém, outras personalidades também tiveram seu destaque no período. Alguns desses passaram desconhecidos por várias décadas, mas documentos recentemente encontrados, mostraram que a atuação dessas pessoas tiveram um grande impacto no resultado final. Um desses ex-desconhecidos é o General da Gringolândia, Charles Eduard Blacksmith.

Charles era uma pessoa muito peculiar. Ele exigia que seus soldados sempre formassem uma fila, de tal maneira que pudesse vê-los todos ao mesmo tempo, para receber as ordens. Por ter uma estatura abaixo da média (usando um pouco de eufemismo), essa fila deveria estar em ordem crescente de altura dos soldados. Para evitar confusão, Little Charles, como era conhecido, sempre comandava seus soldados na hora deles se organizarem na fila. Porém, logo ele notou que para grandes batalhões essa era uma tarefa que dava muito trabalho. Para evitar a fadiga, ele, então, decidiu contratar terceiros para organizar a fila no seu lugar. Sua tarefa é, dada a fila inicial, com a altura de cada soldado, encontrar o menor número de trocas para organizá-la. Contudo, Charles impôs a seguinte condição: um soldado na posição i da fila só pode trocar de lugar com o soldado que está na posição i + k da fila. (um jeito bem peculiar, não?)

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância terá duas linhas. Na primeira haverá dois inteiros N e K que indicam o número de soldados e a distância entre dois soldados que podem trocar de posições, respectivamente. Na segunda haverão N inteiros separados por um espaço, com a altura de cada soldado, na ordem em que estão na fila inicialmente.

Restrições

1 <= N <= 100000
1 <= K <= N
1 <= ai <= 1000000 Altura do soldado i, onde i = 1, 2, . . . , N.

Saída

Para cada instância imprima um inteiro com o menor número de trocas necessárias para ordenar os soldados, ou impossivel caso não seja possível ordenar os soldados levando em conta a condição imposta por Little Charles.

Exemplo de entrada

3
4 2
3 4 1 2
4 1
4 3 2 1
4 2
7 3 6 5

Saída para o exemplo de entrada

2
6
impossivel

Adicionado por:Wanderley Guimarăes
Data:2009-08-31
Tempo limite:1.274s
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:Segunda Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2010-09-28 02:02:30 [UFS] Guilherme 3P
Problemas como esse dividiram o mundo entre trolls e ragers!

Last edit: 2010-09-28 03:09:20
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.