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
Added by: | Wanderley Guimarăes |
Date: | 2012-06-21 |
Time limit: | 2.207s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Maratona Mineira 2012 |