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

ACOES2MG - Investindo no mercado de ações 2

José investe no mercado de ações com uma estratégia de investimento um tanto quanto complexa.

Considere que José possui duas sequências de inteiros P = (P1, P2, ..., PA) e R = (R1, R2, ..., RB), tal que P é uma sequência de inteiros que representa os preços das últimas A negociações de uma determinada ação e R é uma sequência de inteiros distintos utilizada como referência para decidir se José deve ou não investir nas ações em questão.

A partir da sequência P, José gera uma nova sequência M = (M1, M2, ..., MA) , em que Mi é igual à mediana dos valores da subsequência P(1:i) = (P1, P2, ..., Pi), para todo i = 1, 2, ..., A. A mediana da subsequência P(1:i) é definida como o k-ésimo valor da subsequência P(1:i) ordenada em ordem crescente, em que k = ⌈i/2⌉. Por exemplo, se temos a sequência de preços P = (5, 3, 2, 1, 4, 2), então:

  • M1 = mediana de P(1:1) = mediana de (5) = primeiro valor de (5) = 5
  • M2 = mediana de P(1:2) = mediana de (5, 3) = primeiro valor de (3, 5) = 3
  • M3 = mediana de P(1:3) = mediana de (5, 3, 2) = segundo valor de (2, 3, 5) = 3
  • M4 = mediana de P(1:4) = mediana de (5, 3, 2, 1) = segundo valor de (1, 2, 3, 5) = 2
  • M5 = mediana de P(1:5) = mediana de (5, 3, 2, 1, 4) = terceiro valor de (1, 2, 3, 4, 5) = 3
  • M6 = mediana de P(1:6) = mediana de (5, 3, 2, 1, 4, 2) = terceiro valor de (1, 2, 2, 3, 4, 5) = 2

Assim, se P = (5, 3, 2, 1, 4, 2), temos que M = (5, 3, 3, 2, 3, 2).

Após determinar a sequência M, José a compara com a sequência de referência R, formada por inteiros distintos e obtida através de informações privilegiadas, que representa a sequência ótima de valores para as medianas dos preços das últimas negociações de uma determinada ação. Assim, se as sequências M e R forem iguais, José pode investir tranquilamente tendo a certeza de que consiguirá obter o maior lucro possível em seu investimento.

Como é muito difícil que as sequências M e R sejam iguais, José considera suficiente que elas sejam ao menos bastante similares para que ele invista nas ações. Assim, para determinar o quanto a sequência M se assemelha da sequência R, José deve calcular a maior subsequência comum de M e R.

Uma subsequência X' de uma sequência de inteiros X é obtida a partir da remoção de zero ou mais inteiros de X, com os elementos de X' aparecendo na mesma ordem em que aparecem em X. Por exemplo, se X = (2, 4, 1, 1, 2, 3), então X' = (2, 1, 1, 3) é uma subsequência de X, enquanto X' = (1, 4) e X' = (2, 1, 5) não são subsequências de X. Assim, as subsequências comuns das duas sequências (5, 3, 3, 2, 4) e (4, 5, 3, 4) são (), (3), (4), (5), (5, 3), (5, 4) e (5, 3, 4), sendo a última a maior delas, com tamanho 3.

José está com dificuldades para determinar se deve ou não investir nas ações e precisa da sua ajuda. Para tanto, dadas as sequências P e R, você deve calcular o tamanho da maior subsequência comum de M e R, em que M é a sequência de medianas calculada da maneira descrita anteriormente.

Entrada

Há vários casos de teste.

Cada caso de teste é descrito em duas linhas. A primeira linha inicia com um inteiro A (1 ≤ A ≤ 100.000) que representa o tamanho da sequência P, seguido de A inteiros que representam a sequência P. A segunda linha inicia com um inteiro B (1 ≤ B ≤ 100.000) que representa o tamanho da sequência R, seguido de B inteiros distintos que representam a sequência R. Todos os inteiros das sequências P e R são maiores ou iguais a 0 e menores ou iguais a 1.000.000.000.

A entrada termina com A=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma única linha contendo um único inteiro, o tamanho da maior subsequência comum de M e R.

Exemplos

Entrada:
6 5 3 2 1 4 2
5 5 1 2 7 3
4 1 2 3 4
7 7 6 5 4 3 2 1
3 1 1 1
5 2 4 3 5 6
0

Saída:
3
1
0

Adicionado por:Wanderley Guimarăes
Data:2012-06-21
Tempo limite:2.207s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2012

hide comments
2014-12-29 20:40:13 Junior Andrade [UNIFEI]
-> Para achar todas as medianas em nlogn use duas estruturas de dados que consigam manter os números ordenados. Uma dessas estruturas contem a metade com [0...teto(i/2)] e o outra parte [teto(i/2)+1....n] ( em que n é o tamanho atual da soma dos tamanhos dessas estruturas ).
-> Tente pensar em uma maneira de reduzir a parte de achar a maior subsequęncia de dois vetores em um outro tipo de problema, como uma LIS.


Last edit: 2014-12-29 20:41:34
2014-03-14 03:38:32 Luciano Ribeiro
Alguma dica?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.