Cuadrados P58849
En una hoja de papel de n× m centímetros se dibujan varias líneas horizontales y verticales, tal y como se muestra en la figura siguiente:
Al dibujar las líneas el papel queda dividido en diversos rectángulos vacíos (es decir, que no contienen ningún otro rectángulo dentro). Te pedimos que digas cuáles de estos rectángulos son, en realidad, cuadrados, y cuántos hay de cada tamaño.
Entrada
Una entrada está formada por un número indeterminado de casos de pruebas, separados por una línea en blanco. Cada caso está formado por 3 líneas. La primera línea contiene los números n (altura) y m (ancho) del rectángulo. Se te garantiza que 1<n,m≤ 20000. La segunda línea empieza con el número h≥ 0 de líneas horizontales, seguido de h números entre 1 i n−1 con las posiciones de dichas líneas. La tercera línea contiene el número v≥ 0 de líneas verticales, y los v números entre 1 y m−1 con sus posiciones. Puedes asumir que ambos listados se te dan ordenados, y que no hay dos líneas que ocupen la misma posición. Tu programa tendrá 1 segundo de CPU para resolver cada entrada.
Salida
Para cada caso de pruebas, escribe una línea con Case X, donde X es el número del caso (empezando por 1), seguido de tantas líneas como tamaños distintos de cuadrados. Cada una de estas líneas será de la forma Square YxY:, donde Y es el tamaño del cuadrado, seguido del número de cuadrados de dicho tipo. Las líneas deberán listarse de menor a mayor Y. Escribe una línea con tres guiones al final de cada caso de pruebas.
Puntuación
- Test1: 20 Puntos
Resolver varias entradas con no más de 10 casos con n,m≤ 50.
- Test1: 20 Puntos
Resolver varias entradas con no más de 10 casos con n,m≤ 200.
- Test1: 20 Puntos
Resolver varias entradas con no más de 10 casos con n,m≤ 1000.
- Test1: 20 Puntos
Resolver varias entradas con no más de 10 casos con n,m≤ 5000.
- Test1: 20 Puntos
Resolver varias entradas con no más de 10 casos con n,m≤ 20000.
Input
4 4 1 2 1 2 4 4 1 3 1 1 4 4 1 2 0 4 4 2 1 3 1 2 4 4 3 1 2 3 3 1 2 3 4 4 0 0
Output
Case 1 Square 2x2: 4 --- Case 2 Square 1x1: 1 Square 3x3: 1 --- Case 3 --- Case 4 Square 2x2: 2 --- Case 5 Square 1x1: 16 --- Case 6 Square 4x4: 1 ---
Input
10 20 5 1 2 4 6 9 8 3 5 7 8 11 16 17 19 20 20 6 1 2 4 7 11 15 6 7 12 13 14 18 19
Output
Case 1 Square 1x1: 9 Square 2x2: 6 Square 3x3: 2 --- Case 2 Square 1x1: 8 Square 4x4: 2 Square 5x5: 1 ---
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++