Aspersores mínimos necesarios para regar un parque rectangular

Dado N * M parque rectangular que tiene N filas y M columnas, cada celda del parque es un cuadrado de unidad de área y los límites entre las celdas se denominan hexágono y se puede colocar un rociador en el medio del hexágono. La tarea es encontrar el número mínimo de aspersores necesarios para regar todo el parque.

Ejemplos: 

Entrada: N = 3 M = 3 
Salida: 5 
Explicación: 
Para las dos primeras columnas se requieren 3 rociadores y para la última columna estamos obligados a usar 2 rociadores para regar la última columna.

Entrada: N = 5 M = 3 
Salida: 8 
Explicación: 
Para las dos primeras columnas se requieren 5 rociadores y para la última columna estamos obligados a usar 3 rociadores para regar la última columna. 

Acercarse: 

1. Después de hacer algunas observaciones, se puede señalar una cosa, es decir, por cada dos columnas, se requieren N rociadores porque podemos colocarlos entre dos columnas.
2. Si M es par, entonces claramente se requieren N* (M / 2) aspersores.
3. Pero si M es impar, la solución para M – 1 columna se puede calcular usando la fórmula de columna par, y para la última columna agregue (N + 1) / 2 rociadores para regar la última columna, independientemente de que N sea par o impar.

// C++ program to find the
// minimum number sprinklers
// required to water the park.
 
#include <iostream>
using namespace std;
typedef long long int ll;
 
// Function to find the
// minimum number sprinklers
// required to water the park.
void solve(int N, int M)
{
 
    // General requirements of
    // sprinklers
    ll ans = (N) * (M / 2);
 
    // if M is odd then add
    // one additional sprinklers
    if (M % 2 == 1) {
        ans += (N + 1) / 2;
    }
 
    cout << ans << endl;
}
 
// Driver code
int main()
{
    int N, M;
    N = 5;
    M = 3;
    solve(N, M);
}

// Java program to find minimum
// number sprinklers required
// to cover the park
class GFG{
     
// Function to find the minimum
// number sprinklers required
// to water the park.
public static int solve(int n, int m)
{
     
    // General requirements of sprinklers
    int ans = n * (m / 2);
         
    // If M is odd then add one
    // additional sprinklers
    if (m % 2 == 1)
    {
        ans += (n + 1) / 2;
    }
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int N = 5;
    int M = 3;
     
    System.out.println(solve(N, M));
}
}
 
// This code is contributed by grand_master

# Python3 program to find the
# minimum number sprinklers
# required to water the park.
 
# Function to find the
# minimum number sprinklers
# required to water the park.
def solve(N, M) :
     
    # General requirements of
    # sprinklers
    ans = int((N) * int(M / 2))
 
    # if M is odd then add
    # one additional sprinklers
    if (M % 2 == 1):
        ans += int((N + 1) / 2)
 
    print(ans)
 
# Driver code
N = 5
M = 3
solve(N, M)
 
# This code is contributed by yatinagg

// C# program to find minimum
// number sprinklers required
// to cover the park
using System;
 
class GFG{
     
// Function to find the minimum
// number sprinklers required
// to water the park.
public static int solve(int n, int m)
{
     
    // General requirements of sprinklers
    int ans = n * (m / 2);
         
    // If M is odd then add one
    // additional sprinklers
    if (m % 2 == 1)
    {
        ans += (n + 1) / 2;
    }
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    int N = 5;
    int M = 3;
     
    Console.WriteLine(solve(N, M));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// javascript program to find the
// minimum number sprinklers
// required to water the park.
 
// Function to find the
// minimum number sprinklers
// required to water the park.
function solve(N, M)
{
 
    // General requirements of
    // sprinklers
    var ans = (N) * parseInt((M / 2));
 
    // if M is odd then add
    // one additional sprinklers
    if (M % 2 == 1) {
        ans += parseInt((N + 1) / 2);
    }
 
    document.write(ans);
}
 
// Driver code
    var N, M;
    N = 5;
    M = 3;
    solve(N, M);
 
// This code is contributed by SURENDRA_GANGWAR.
</script>

Producción:

8