Cuadrados P58849


Statement
 

pdf   zip

thehtml

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:

(-1,-1)(4,3) [linewidth=3pt] (0,0)(3,0)(3,2)(0,2)(0,0) (-1,1)(4,1) (-1,1.5)(4,1.5) (1,-1)(1,3) (1.5,-1)(1.5,3) (2.5,-1)(2.5,3)

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.

Public test cases
  • 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
    ---
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++