Intermediário Informática - Semana 25

0 Flares Facebook 0 0 Flares ×

André e os Mentos

André é um maratonista do CIn-UFPE. Todo sábado, durante os treinos, ele come de tudo: salgadinho, refrigerante, biscoito, água e mentos. Principalmente mentos. Mas o problema, porém, é que toda vez que André vai tirar alguns mentos do tubo, ele tem que parar de codar por alguns instantes, o que atrapalha sua concentração.

O mentos vem em um tubo com duas pontas. Cada vez que André quer chupar alguns, ele escolhe um certo sabor, e olha pra cada ponta do mentos. Em cada uma, se houver um mentos do sabor escolhido, ele pega. Se não houver nenhum daquele sabor nas pontas, ele não pega nenhum, e só parou de codar à toa. Para diminuir a perda de tempo durante o contest, André decidiu minimizar suas paradas para pegar mentos. Ele fez um corte fino ao longo do tubo, para poder ver com antecedência quais sabores tem dentro dele. Mas ele não vai pegar do meio, e fez isso apenas para poder decidir melhor quais sabores irá escolher tirar das pontas em cada uma de suas paradas.

Agora, André precisa calcular o número mínimo de vezes que ele deve parar para pegar seus mentos, seguindo o método descrito, até eles acabarem. Ele calcularia isso facilmente usando Transformada de Fourier, mas ele está ocupado codando uma questão. Por isso cabe a você, um companheiro de time dele, fazer isso para ajudá-lo.

Entrada

A primeira linha contém um inteiro T (1 ≤ T ≤ 200), o número de casos de teste. Cada caso de teste começa com uma linha com um inteiro N, o número de mentos do tubo (1 ≤ N ≤ 1000). Na linha seguinte, há N inteiros, o i-ésimo deles é o número do sabor do i-ésimo mentos no tubo. Cada um desses números está entre 1 e 10⁹.

Saída

Para cada caso imprima uma linha contendo "Caso #X: Y", onde X é o número do caso atual, iniciando em 1, e Yé a quantidade mínima de vezes que André precisa parar para pegar mentos.

Exemplo de Entrada Exemplo de Saída
3
5
1 3 1 3 2
5
1 2 3 2 1
7
1 1 2 3 3 4 2
Caso #1: 4
Caso #2: 3
Caso #3: 5

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: