Muestreo de velociraptores (2) P85939
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 ≤ m ≤ k ≤ n ≤ 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
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
- Author
- Alex Alvarez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++