Puntuaciones comunes P95498


Statement
 

pdf   zip

thehtml

Dos amigos, Arthur y Bob, están jugando con un ordenador y han decidido guardar sus puntuaciones. Cuando acaban de jugar, Arthur y Bob quieren determinar la longitud de la máxima subsecuencia de puntuaciones que tienen en común.

Por ejemplo, si las puntuaciones de Arthur son [8, 12, 6, 9, 2] y las de Bob son [12, 6, 8, 2], entonces la máxima subsecuencia que tienen en común es [12, 6, 2], que tiene longitud 3. Observad que una subsecuencia no tiene porqué estar formada por elementos contiguos, pero que sí debe preservarse el orden de las puntuaciones.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con dos números 0≤ M≤ 1000 y 0≤ N≤ 1000, representando la longitud de las secuencia de Arthur y de Bob, respectivamente. Siguen los M números de Arthur, y los N números de Bob. Todos los números son naturales.

Salida

Para cada caso, escribid la longitud de la subsecuencia común más larga.

Public test cases
  • Input

    5 4
    8 12 6 9 2
    12 6 8 2
    7 7
    8 13 16 7 12 9 5
    16 7 9 5 8 13 16
    15 12
    11 9 12 6 2 6 12 19 2 7 1 16 12 15 2
    9 6 18 6 12 17 19 8 7 12 3 15
    

    Output

    3
    4
    8
    
  • Information
    Author
    Anders Jonsson
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++ Python Python
    User solutions
    C++ Python