Muestreo de velociraptores (2) P85939


Statement
 

pdf   zip

thehtml

Es bien sabido que los velociraptores son una amenaza real y por ello hemos trazado un gran plan desde la OIE. Se ha descubierto un lugar donde, curiosamente, duermen cada noche n velociraptores en fila india. Sin embargo, la última misión fue un completo fracaso y vamos a probar de nuevo, cambiando un poco el objetivo.

Existen k especies distintas de velociraptor, y queremos capturar al menos un ejemplar de m ‍especies diferentes. Por miedo a despertarlos, un requisito esencial es que todos los velociraptores capturados duerman consecutivamente. ¿Podéis decir el menor número que habrá que capturar?

Entrada

La entrada contiene diversos casos. Cada caso empieza con n, k y m. Finalmente, viene la especie de cada uno de los n velociraptores, en orden. Suponed 1 ≤ mkn ≤ 106, que las especies se numeran entre 0 y k − 1, y que entre los n velociraptores hay al menos m de diferentes especies.

Salida

Para cada caso, escribid el menor número de velociraptores consecutivos que es necesario capturar.

Puntuación

  • Test1:  ‍ Resolver casos con m = 1 como el Ejemplo 1.  ‍5 Puntos ‍
  • Test2:  ‍ Resolver casos con n ≤ 100.  ‍15 Puntos ‍
  • Test3:  ‍ Resolver casos con n ≤ 1000.  ‍15 Puntos ‍
  • Test4:  ‍ Resolver casos con n ≤ 105.  ‍15 Puntos ‍
  • Test5:  ‍ Resolver casos de todo tipo.  ‍50 Puntos ‍
Public test cases
  • Input

    4 3 1
    0 1 1 2
    

    Output

    1
    
  • Input

    10 6 3
    1 4 1 5 3 5 5 4 5 2
    10 5 5
    3 4 0 4 2 2 1 3 4 1
    10 8 7
    4 7 2 1 6 4 5 0 2 1
    

    Output

    3
    6
    7
    
  • Information
    Author
    Alex Alvarez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++