Dadas n×m de área rectangular grande con cuadrados unitarios y k tiempos de corte permitidos, el corte debe ser recto (horizontal o vertical) y debe ir a lo largo de los bordes del cuadrado unitario. ¿Cuál es el área máxima posible de la pieza más pequeña que puede obtener con exactamente k cortes?
Ejemplos:
Input : 3 4 1 Output : 6 Input : 6 4 2 Output : 8
Imagen para la segunda entrada
Imagen para la primera entrada
Como se trata de un área rectangular de n×m, hay (n-1) filas y (m-1) columnas. Entonces, si k > (n + m – 2) entonces, entonces no es posible cortar . Entonces, si k es menor que eso. Habrá dos casos
- Cuando k es menor que max( n, m ) – 1 : En el primer caso, si k es menor que max( n, m ) – 1, entonces m * ( n / ( k+1 ) ) o n * ( m / ( k+1 ) ) es máximo , aquí lo hemos dividido por ( k + 1 ) porque horizontal o verticalmente es decir ( m * n = bloques totales ) se divide en ( k + 1 ) partes.
- Cuando k es mayor o igual a max( n, m) – 1 : En el segundo caso, si k >= max( n, m ) – 1, entonces se cortarán tanto las filas como las columnas, por lo que el el área máxima más pequeña posible será m / ( k – n + 2) o n / ( k – m + 2 ) . En este caso, suponga que si n > m entonces, en primer lugar, es posible cortar n-1 (fila o columna). Después de eso, el corte (k – n) se realizará en m – 1. Entonces, aquí hemos ajustado este corte (k – n) de modo que la división más pequeña posible sea la máxima.
Código: a continuación se muestra la implementación del siguiente enfoque
C++
// C++ code for Maximum of smallest
// possible area that can get with
// exactly k cut of given rectangular
#include <bits/stdc++.h>
using namespace std;
void max_area(int n, int m, int k)
{
if (k > (n + m - 2))
cout << "Not possible" << endl;
else {
int result;
// for the 1st case
if (k < max(m, n) - 1) {
result = max(m * (n / (k + 1)), n * (m / (k + 1)));
}
// for the second case
else {
result = max(m / (k - n + 2), n / (k - m + 2));
}
// print final result
cout << result << endl;
}
}
// driver code
int main()
{
int n = 3, m = 4, k = 1;
max_area(n, m, k);
}
Java
// Java code for Maximum of smallest
// possible area that can get with
// exactly k cut of given rectangular
class GFG {
//Utility Function
static void max_area(int n, int m, int k)
{
if (k > (n + m - 2))
System.out.println("Not possible");
else {
int result;
// for the 1st case
if (k < Math.max(m, n) - 1)
{
result = Math.max(m * (n / (k + 1)),
n * (m / (k + 1)));
}
// for the second case
else {
result = Math.max(m / (k - n + 2),
n / (k - m + 2));
}
// print final result
System.out.println(result);
}
}
// Driver code
public static void main (String[] args)
{
int n = 3, m = 4, k = 1;
max_area(n, m, k);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 code for Maximum of smallest
# possible area that can get with
# exactly k cut of given rectangular
def max_area(n,m,k):
if (k > (n + m - 2)):
print("Not possible")
else:
# for the 1st case
if (k < max(m,n) - 1):
result = max(m * (n / (k + 1)), n * (m / (k + 1)));
# for the second case
else:
result = max(m / (k - n + 2), n / (k - m + 2));
# print final result
print(result)
# driver code
n = 3
m = 4
k = 1
max_area(n, m, k)
# This code is contributed
# by Azkia Anam.
C#
// C# code for Maximum of smallest
// possible area that can get with
// exactly k cut of given rectangular
using System;
class GFG {
//Utility Function
static void max_area(int n, int m, int k)
{
if (k > (n + m - 2))
Console.WriteLine("Not possible");
else {
int result;
// for the 1st case
if (k < Math.Max(m, n) - 1)
{
result = Math.Max(m * (n / (k + 1)),
n * (m / (k + 1)));
}
// for the second case
else {
result = Math.Max(m / (k - n + 2),
n / (k - m + 2));
}
// print final result
Console.WriteLine(result);
}
}
// Driver code
public static void Main ()
{
int n = 3, m = 4, k = 1;
max_area(n, m, k);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code for Maximum of smallest
// possible area that can get with
// exactly k cut of given rectangular
function max_area($n, $m, $k)
{
if ($k > ($n + $m - 2))
echo "Not possible" ,"\n";
else
{
$result;
// for the 1st case
if ($k < max($m, $n) - 1)
{
$result = max($m * ($n / ($k + 1)),
$n * ($m / ($k + 1)));
}
// for the second case
else
{
$result = max($m / ($k - $n + 2),
$n / ($k - $m + 2));
}
// print final result
echo $result ,"\n";
}
}
// Driver Code
$n = 3; $m = 4; $k = 1;
max_area($n, $m, $k);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript code for Maximum of smallest
// possible area that can get with
// exactly k cut of given rectangular
// Utility Function
function max_area(n, m, k)
{
if (k > (n + m - 2))
document.write("Not possible");
else
{
let result;
// For the 1st case
if (k < Math.max(m, n) - 1)
{
result = Math.max(m * (n / (k + 1)),
n * (m / (k + 1)));
}
// For the second case
else
{
result = Math.max(m / (k - n + 2),
n / (k - m + 2));
}
// Print final result
document.write(result);
}
}
// Driver Code
let n = 3, m = 4, k = 1;
max_area(n, m, k);
// This code is contributed by susmitakundugoaldanga
</script>
Producción :
6
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA