Dados tres números , , . Encuentra el número de cuadrados de dimensión requeridos para cubrir el rectángulo.
Nota :
- Se permite cubrir la superficie más grande que el rectángulo, pero el rectángulo debe cubrirse.
- No está permitido romper un cuadrado.
- Los lados de los cuadrados deben ser paralelos a los lados del rectángulo.
Ejemplos :
Input: N = 6, M = 6, a = 4 Output: 4 Input: N = 2, M = 3, a = 1 Output: 6
Enfoque: Un enfoque eficiente es hacer una observación y encontrar una fórmula. La restricción de que los bordes de cada cuadrado deben ser paralelos a los bordes del rectángulo permite analizar los ejes X e Y por separado, es decir, cuántos cuadrados de longitud ‘a’ se necesitan para cubrir cuadrados de longitud ‘m’ y ‘n’ y tome el producto de estas dos cantidades. El número de cuadrados pequeños de longitud de lado ‘a’ necesarios para cubrir un cuadrado de tamaño ‘m’ es ceil (m/a). Del mismo modo, el número de cuadrados de tamaño ‘a’ necesarios para cubrir un cuadrado de tamaño ‘n’ es ceil(n/a).
Entonces, la respuesta será ceil(m/a)*ceil(n/a).
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find number of squares // of a*a required to cover n*m rectangle #include <bits/stdc++.h> using namespace std; // function to find number of squares // of a*a required to cover n*m rectangle int Squares(int n, int m, int a) { return ((m + a - 1) / a) * ((n + a - 1) / a); } // Driver code int main() { int n = 6, m = 6, a = 4; // function call cout << Squares(n, m, a); return 0; }
C
// C program to find number of squares // of a*a required to cover n*m rectangle #include <stdio.h> // function to find number of squares // of a*a required to cover n*m rectangle int Squares(int n, int m, int a) { return ((m + a - 1) / a) * ((n + a - 1) / a); } // Driver code int main() { int n = 6, m = 6, a = 4; // function call printf("%d",Squares(n, m, a)); return 0; } // This code is contributed by kothavvsaakash.
Java
// Java program to find number of squares // of a*a required to cover n*m rectangle import java.util.*; class solution { // function to find a number of squares // of a*a required to cover n*m rectangle static int Squares(int n, int m, int a) { return ((m + a - 1) / a) * ((n + a - 1) / a); } // Driver code public static void main(String arr[]) { int n = 6, m = 6, a = 4; // function call System.out.println(Squares(n, m, a)); } } //This code is contributed by Surendra_Gangwar
Python 3
# Python 3 program to find number # of squares of a*a required to # cover n*m rectangle # function to find number of # squares of a*a required to # cover n*m rectangle def Squares(n, m, a): return (((m + a - 1) // a) * ((n + a - 1) // a)) # Driver code if __name__ == "__main__": n = 6 m = 6 a = 4 # function call print(Squares(n, m, a)) # This code is contributed # by ChitraNayal
C#
// CSHARP program to find number of squares // of a*a required to cover n*m rectangle using System; class GFG { // function to find a number of squares // of a*a required to cover n*m rectangle static int Squares(int n, int m, int a) { return ((m + a - 1) / a) * ((n + a - 1) / a); } static void Main() { int n = 6, m = 6, a = 4; // function call Console.WriteLine(Squares(n, m, a)); } // This code is contributed by ANKITRAI1 }
PHP
<?php // PHP program to find number of squares // of a*a required to cover n*m rectangle // function to find number of squares // of a*a required to cover n*m rectangle function Squares($n, $m, $a) { return ((int)(($m + $a - 1) / $a)) * ((int)(($n + $a - 1) / $a)); } // Driver code $n = 6; $m = 6; $a = 4; // function call echo Squares($n, $m, $a); // This code is contributed // by Akanksha Rai ?>
Javascript
<script> // JavaScript program to find number of squares // of a*a required to cover n*m rectangle // function to find a number of squares // of a*a required to cover n*m rectangle function Squares(n, m, a) { return parseInt(((m + a - 1) / a)) * parseInt(((n + a - 1) / a)); } // Driver code var n = 6, m = 6, a = 4; // Function call document.write(Squares(n, m, a)); // This code is contributed by Ankita saini </script>
4
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA