Maximice las celdas ocupadas en Matrix dada satisfaciendo las condiciones

Dada una array de dimensión N*M , la tarea es maximizar el número total de celdas ocupadas en la array dada de modo que sigan la condición dada:

• Si dos celdas están ocupadas en la misma fila, debe haber al menos una celda vacía entre ellas.
• Si dos celdas están ocupadas en filas diferentes, debe haber al menos una fila completamente vacía entre ellas, 
  es decir, si las celdas en la i- ésima y j- ésima fila están ocupadas de manera que i < j , entonces debe haber una k-ésima fila completamente vacía de modo que i < k < j .

Ejemplos:

Entrada: N = 1 ,M = 5
Salida: 3
Explicación: Solo hay una fila con cinco asientos. 
Se pueden ocupar un máximo de tres celdas. 
Consulte la tabla a continuación, donde 1 indica una celda ocupada.

1

1

1

Entrada: N = 3 ,M = 3
Salida: 4
Explicación:  Hay tres filas con tres asientos cada una.
El máximo de celdas ocupadas puede ser 4.

1		1
1		1

Enfoque ingenuo: el problema se puede resolver utilizando un enfoque codicioso . Comience a llenar desde la primera fila y la primera columna y mantenga un espacio de 1 entre dos celdas ocupadas de una fila y un espacio de una fila entre dos celdas ocupadas de filas diferentes.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// maximum number of occupied cells
int solve(int N, int M)
{
    int ans = 0;
    while (1) {
        // Count number of occupied cells
        // in one row
        for (int i = 1; i <= M; i += 2) {
            ans++;
        }
        // If row numbers to be filled
        // are greater than or equal to 2
        // decrease by 2 otherwise decrease by 1
        // and if number of rows to be filled
        // are 0 return ans
        if (N >= 2) {
            N--;
            N--;
        }
        else if (N == 1) {
            N--;
        }
        if (N == 0) {
            break;
        }
    }
   
    // Return number of occupied cells
    return ans;
}
 
// Driver code
int main()
{
    int N = 1;
    int M = 5;
    cout << solve(N, M);
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
 
  // Function to find
  // maximum number of occupied cells
  static int solve(int N, int M)
  {
    int ans = 0;
    while (true)
    {
 
      // Count number of occupied cells
      // in one row
      for (int i = 1; i <= M; i += 2) {
        ans++;
      }
 
      // If row numbers to be filled
      // are greater than or equal to 2
      // decrease by 2 otherwise decrease by 1
      // and if number of rows to be filled
      // are 0 return ans
      if (N >= 2) {
        N--;
        N--;
      }
      else if (N == 1) {
        N--;
      }
      if (N == 0) {
        break;
      }
    }
 
    // Return number of occupied cells
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 1;
    int M = 5;
    System.out.print(solve(N, M));
  }
}
 
// This code is contributed by Samim Hossain Mondal

# Python program for the above approach
 
# Function to find
# maximum number of occupied cells
def solve(N, M):
    ans = 0;
    while (1):
     
        # Count number of occupied cells
        # in one row
        for i in range(1, M + 1, 2):
            ans += 1
         
        # If row numbers to be filled
        # are greater than or equal to 2
        # decrease by 2 otherwise decrease by 1
        # and if number of rows to be filled
        # are 0 return ans
        if (N >= 2):
            N -= 1
            N -= 1
        elif (N == 1):
            N -= 1
        if (N == 0):
            break
   
    # Return number of occupied cells
    return ans;
 
# Driver code
N = 1;
M = 5;
print(solve(N, M));
 
# This code is contributed by saurabh_jaiswal.

// C# program for the above approach
using System;
class GFG {
 
  // Function to find
  // maximum number of occupied cells
  static int solve(int N, int M)
  {
    int ans = 0;
    while (true)
    {
 
      // Count number of occupied cells
      // in one row
      for (int i = 1; i <= M; i += 2) {
        ans++;
      }
 
      // If row numbers to be filled
      // are greater than or equal to 2
      // decrease by 2 otherwise decrease by 1
      // and if number of rows to be filled
      // are 0 return ans
      if (N >= 2) {
        N--;
        N--;
      }
      else if (N == 1) {
        N--;
      }
      if (N == 0) {
        break;
      }
    }
 
    // Return number of occupied cells
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 1;
    int M = 5;
    Console.Write(solve(N, M));
  }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for the above approach
 
// Function to find
// maximum number of occupied cells
function solve(N, M)
{
    let ans = 0;
    while (1)
    {
     
        // Count number of occupied cells
        // in one row
        for (let i = 1; i <= M; i += 2) {
            ans++;
        }
         
        // If row numbers to be filled
        // are greater than or equal to 2
        // decrease by 2 otherwise decrease by 1
        // and if number of rows to be filled
        // are 0 return ans
        if (N >= 2) {
            N--;
            N--;
        }
        else if (N == 1) {
            N--;
        }
        if (N == 0) {
            break;
        }
    }
   
    // Return number of occupied cells
    return ans;
}
 
// Driver code
let N = 1;
let M = 5;
document.write(solve(N, M));
 
// This code is contributed by saurabh_jaiswal.
</script>

3

Complejidad de Tiempo: O(N*M)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.

Enfoque eficiente: para maximizar el número total de celdas ocupadas, deben ocuparse de la manera mencionada anteriormente. El número total se puede obtener de la siguiente observación:

Entonces, el número máximo de celdas que se pueden ocupar para cada fila es ceil(M/2) .
Y como hay un espacio de una fila entre dos celdas ocupadas de filas diferentes, 
el número máximo de filas que se pueden ocupar es ceil(N/2) .
Por lo tanto , el número máximo de celdas que se pueden ocupar es ceil(M/2) * ceil(N/2) .

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// maximum number of occupied cells
int solve(int N, int M)
{
    int x = (M + 1) / 2;
    int y = (N + 1) / 2;
    int ans = x * y;
 
    // Return number of occupied cells
    return ans;
}
 
// Driver code
int main()
{
    int N = 1;
    int M = 5;
    cout << solve(N, M);
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Function to find
  // maximum number of occupied cells
  public static int solve(int N, int M)
  {
    int x = (M + 1) / 2;
    int y = (N + 1) / 2;
    int ans = x * y;
 
    // Return number of occupied cells
    return ans;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    int N = 1;
    int M = 5;
    System.out.print(solve(N, M));
  }
}
 
// This code is contributed by Shubham Singh

# Python program for the above approach
 
# Function to find
# maximum number of occupied cells
def solve (N, M):
    x = (M + 1) // 2
    y = (N + 1) // 2
    ans = x * y
     
    # Return number of occupied cells
    return ans
     
# Driver code
N = 1
M = 5
print(solve(N, M));
 
# This code is contributed by Shubham Singh

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to find
  // maximum number of occupied cells
  public static int solve(int N, int M)
  {
    int x = (M + 1) / 2;
    int y = (N + 1) / 2;
    int ans = x * y;
 
    // Return number of occupied cells
    return ans;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int N = 1;
    int M = 5;
    Console.Write(solve(N, M));
  }
}
 
// This code is contributed by shikhasingrajput

<script>
        // JavaScript program for the above approach
 
        // Function to find
        // maximum number of occupied cells
        const solve = (N, M) => {
            let x = parseInt((M + 1) / 2);
            let y = parseInt((N + 1) / 2);
            let ans = x * y;
 
            // Return number of occupied cells
            return ans;
        }
 
        // Driver code
 
        let N = 1;
        let M = 5;
        document.write(solve(N, M));
 
    // This code is contributed by rakeshsahni
 
    </script>

3

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)