Dados cuatro enteros N, M, A, B donde N es el número de filas y M es el número de columnas, la tarea es comprobar si es posible crear una array binaria de dimensiones N x M tal que cada fila tenga un número A de 1s y cada columna tiene un número B de 1s . Si alguna array de este tipo es posible, imprímala; de lo contrario, imprima «-1» .
Ejemplos:
Entrada: N = 3, M = 6, A = 2, B = 1
Salida:
1 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 1
Explicación:
Cada fila tiene A unos, es decir, 2 y cada columna tiene Huesos, es decir, 1.Entrada: N = 2, M = 2, A = 2, B = 1
Salida: No
Explicación:
No es posible crear una array de 2 x 2 en la que cada fila tenga 2 unos y cada columna tenga 1 debido a la siguientes dos observaciones:
1. Para cada fila colocar dos unos por lo que nunca podremos tener un 1 en cada columna.
1 1
1 12. Para cada columna coloque un 1 por lo que nunca podemos tener 2 unos en cada fila.
1 0
0 1
Enfoque: la idea es observar que dado que cada fila debe tener exactamente A 1 y cada columna debe tener exactamente B 1 , por lo tanto, el número de unos en todas las filas A * N debe ser igual al número de 1 en todas las columnas B * m _ Por lo tanto, la array deseada existe si y solo si A*N = B*M . A continuación se muestra la ilustración:
- Encuentre cualquier número 0 < d < M tal que (d * N)%M == 0 , donde A % B es el resto de dividir A entre B .
- En la primera fila de la array deseada, inserte los que están en las posiciones [1, A] .
- En la fila i -ésima , coloque los unos, como en la fila i – 1 , pero desplazados cíclicamente por d a la derecha.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Number of rows
const int n = 3;
// Number of columns
const int m = 6;
// Function that prints the matrix
// if it exists
void printMatrix(int arr[][m],
string ans)
{
if (ans == "No")
cout << "No\n";
else {
// Print if matrix exists
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << arr[i][j] << " ";
cout << '\n';
}
}
}
// Function to check if it is possible
// to create a matrix such that every
// row has A 1s & every column has B 1s
void createMatrix(int a, int b)
{
int matrix[n][m], row[n], col[m];
// Initialize all matrix
// entries equal to 0
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = 0;
}
}
// Initialize the number of
// ones required in every row
for (int i = 0; i < n; i++)
row[i] = a;
// Initialize the number of
// ones required in each column
for (int i = 0; i < m; i++)
col[i] = b;
int l = 0, d = 0;
// Check if the total number of
// ones required in every row is
// not equal to total number of
// ones required in every column
// then print No
if (n * a != m * b)
printMatrix(matrix, "No");
else {
for (int i = 0; i < n; i++) {
int j;
if (l == m)
l = 0;
for (j = l; j < m; j++) {
if (row[i] > 0 && col[j] > 0) {
// Fill a one if there is a
// place to be filled
matrix[i][j] = 1;
// Decrease the number of
// ones required in ith row
row[i]--;
// Decrease the number of
// ones required in jth column
col[j]--;
d = j;
}
}
l = d + 1;
if (row[i] != 0) {
for (j = 0; j < m; j++) {
if (row[i] > 0 && col[j] > 0) {
// Fill a one if there is
// a place to be filled
matrix[i][j] = 1;
// Decrease the number of 1s
// required in ith row
row[i]--;
// Decrease the number of 1s
// required in jth column
col[j]--;
l = j + 1;
}
// Break the loop if no place
// is left for ones to filled
if (row[i] == 0)
break;
}
}
}
// Function call to print the matrix
printMatrix(matrix, "Yes");
}
}
// Driver Code
int main()
{
// Number of ones required
// in every row
int a = 2;
// Number of ones required
// in every column
int b = 1;
// Function call
createMatrix(a, b);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Number of rows
static int n = 3;
// Number of columns
static int m = 6;
// Function that prints the matrix
// if it exists
static void printMatrix(int arr[][],
String ans)
{
if (ans == "No")
System.out.print("No\n");
else
{
// Print if matrix exists
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
System.out.print(arr[i][j] + " ");
System.out.println();
}
}
}
// Function to check if it is possible
// to create a matrix such that every
// row has A 1s & every column has B 1s
static void createMatrix(int a, int b)
{
int [][]matrix = new int[n][m];
int []row = new int[n];
int []col = new int[m];
// Initialize all matrix
// entries equal to 0
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
matrix[i][j] = 0;
}
}
// Initialize the number of
// ones required in every row
for(int i = 0; i < n; i++)
row[i] = a;
// Initialize the number of
// ones required in each column
for(int i = 0; i < m; i++)
col[i] = b;
int l = 0, d = 0;
// Check if the total number of
// ones required in every row is
// not equal to total number of
// ones required in every column
// then print No
if (n * a != m * b)
printMatrix(matrix, "No");
else
{
for(int i = 0; i < n; i++)
{
int j;
if (l == m)
l = 0;
for(j = l; j < m; j++)
{
if (row[i] > 0 && col[j] > 0)
{
// Fill a one if there is a
// place to be filled
matrix[i][j] = 1;
// Decrease the number of
// ones required in ith row
row[i]--;
// Decrease the number of
// ones required in jth column
col[j]--;
d = j;
}
}
l = d + 1;
if (row[i] != 0)
{
for(j = 0; j < m; j++)
{
if (row[i] > 0 && col[j] > 0)
{
// Fill a one if there is
// a place to be filled
matrix[i][j] = 1;
// Decrease the number of 1s
// required in ith row
row[i]--;
// Decrease the number of 1s
// required in jth column
col[j]--;
l = j + 1;
}
// Break the loop if no place
// is left for ones to filled
if (row[i] == 0)
break;
}
}
}
// Function call to print the matrix
printMatrix(matrix, "Yes");
}
}
// Driver Code
public static void main(String[] args)
{
// Number of ones required
// in every row
int a = 2;
// Number of ones required
// in every column
int b = 1;
// Function call
createMatrix(a, b);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach
# Number of rows
n = 3
# Number of columns
m = 6
# Function that prints the matrix
# if it exists
def printMatrix(arr, ans):
if (ans == "No"):
print("No")
else:
# Print if matrix exists
for i in range(n):
for j in range(m):
print(arr[i][j], end = " ")
print()
# Function to check if it is possible
# to create a matrix such that every
# row has A 1s & every column has B 1s
def createMatrix(a, b):
matrix = [[0 for i in range(m)]
for i in range(n)]
row = [a for i in range(n)]
col = [b for i in range(m)]
l = 0
d = 0
# Check if the total number of
# ones required in every row is
# not equal to total number of
# ones required in every column
# then print No
if (n * a != m * b):
printMatrix(matrix, "No")
else:
for i in range(n):
j = 0
if (l == m):
l = 0
for j in range(l, m):
if (row[i] > 0 and col[j] > 0):
# Fill a one if there is a
# place to be filled
matrix[i][j] = 1
# Decrease the number of
# ones required in ith row
row[i] -= 1
# Decrease the number of
# ones required in jth column
col[j] -= 1
d = j
l = d + 1
if (row[i] != 0):
for j in range(m):
if (row[i] > 0 and col[j] > 0):
# Fill a one if there is
# a place to be filled
matrix[i][j] = 1
# Decrease the number of 1s
# required in ith row
row[i] -= 1
# Decrease the number of 1s
# required in jth column
col[j] -= 1
l = j + 1
# Break the loop if no place
# is left for ones to filled
if (row[i] == 0):
break
# Function call to print matrix
printMatrix(matrix, "Yes")
# Driver Code
if __name__ == '__main__':
# Number of ones required
# in every row
a = 2
# Number of ones required
# in every column
b = 1
# Function call
createMatrix(a, b)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Number of rows
static int n = 3;
// Number of columns
static int m = 6;
// Function that prints the matrix
// if it exists
static void printMatrix(int [,]arr,
String ans)
{
if (ans == "No")
Console.Write("No\n");
else
{
// Print if matrix exists
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
Console.Write(arr[i, j] + " ");
Console.WriteLine();
}
}
}
// Function to check if it is possible
// to create a matrix such that every
// row has A 1s & every column has B 1s
static void createMatrix(int a, int b)
{
int [,]matrix = new int[n, m];
int []row = new int[n];
int []col = new int[m];
// Initialize all matrix
// entries equal to 0
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
matrix[i, j] = 0;
}
}
// Initialize the number of
// ones required in every row
for(int i = 0; i < n; i++)
row[i] = a;
// Initialize the number of
// ones required in each column
for(int i = 0; i < m; i++)
col[i] = b;
int l = 0, d = 0;
// Check if the total number of
// ones required in every row is
// not equal to total number of
// ones required in every column
// then print No
if (n * a != m * b)
printMatrix(matrix, "No");
else
{
for(int i = 0; i < n; i++)
{
int j;
if (l == m)
l = 0;
for(j = l; j < m; j++)
{
if (row[i] > 0 && col[j] > 0)
{
// Fill a one if there is a
// place to be filled
matrix[i,j] = 1;
// Decrease the number of
// ones required in ith row
row[i]--;
// Decrease the number of
// ones required in jth column
col[j]--;
d = j;
}
}
l = d + 1;
if (row[i] != 0)
{
for(j = 0; j < m; j++)
{
if (row[i] > 0 && col[j] > 0)
{
// Fill a one if there is
// a place to be filled
matrix[i,j] = 1;
// Decrease the number of 1s
// required in ith row
row[i]--;
// Decrease the number of 1s
// required in jth column
col[j]--;
l = j + 1;
}
// Break the loop if no place
// is left for ones to filled
if (row[i] == 0)
break;
}
}
}
// Function call to print the matrix
printMatrix(matrix, "Yes");
}
}
// Driver Code
public static void Main(String[] args)
{
// Number of ones required
// in every row
int a = 2;
// Number of ones required
// in every column
int b = 1;
// Function call
createMatrix(a, b);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Number of rows
let n = 3;
// Number of columns
let m = 6;
// Function that prints the matrix
// if it exists
function printMatrix(arr,
ans)
{
if (ans == "No")
document.write("No\n");
else
{
// Print if matrix exists
for(let i = 0; i < n; i++)
{
for(let j = 0; j < m; j++)
document.write(arr[i][j] + " ");
document.write("<br/>");
}
}
}
// Function to check if it is possible
// to create a matrix such that every
// row has A 1s & every column has B 1s
function createMatrix(a, b)
{
let matrix = new Array(n);
// Loop to create 2D array using 1D array
for (var i = 0; i < matrix.length; i++) {
matrix[i] = new Array(2);
}
let row = Array.from({length: n}, (_, i) => 0);
let col = Array.from({length: m}, (_, i) => 0);
// Initialize all matrix
// entries equal to 0
for(let i = 0; i < n; i++)
{
for(let j = 0; j < m; j++)
{
matrix[i][j] = 0;
}
}
// Initialize the number of
// ones required in every row
for(let i = 0; i < n; i++)
row[i] = a;
// Initialize the number of
// ones required in each column
for(let i = 0; i < m; i++)
col[i] = b;
let l = 0, d = 0;
// Check if the total number of
// ones required in every row is
// not equal to total number of
// ones required in every column
// then print No
if (n * a != m * b)
printMatrix(matrix, "No");
else
{
for(let i = 0; i < n; i++)
{
let j;
if (l == m)
l = 0;
for(j = l; j < m; j++)
{
if (row[i] > 0 && col[j] > 0)
{
// Fill a one if there is a
// place to be filled
matrix[i][j] = 1;
// Decrease the number of
// ones required in ith row
row[i]--;
// Decrease the number of
// ones required in jth column
col[j]--;
d = j;
}
}
l = d + 1;
if (row[i] != 0)
{
for(j = 0; j < m; j++)
{
if (row[i] > 0 && col[j] > 0)
{
// Fill a one if there is
// a place to be filled
matrix[i][j] = 1;
// Decrease the number of 1s
// required in ith row
row[i]--;
// Decrease the number of 1s
// required in jth column
col[j]--;
l = j + 1;
}
// Break the loop if no place
// is left for ones to filled
if (row[i] == 0)
break;
}
}
}
// Function call to print the matrix
printMatrix(matrix, "Yes");
}
}
// Driver Code
// Number of ones required
// in every row
let a = 2;
// Number of ones required
// in every column
let b = 1;
// Function call
createMatrix(a, b);
</script>
Producción:
1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
Complejidad de tiempo : O (N * M), ya que estamos usando bucles anidados para atravesar N * M veces.
Espacio auxiliar : O(N*M), ya que estamos usando espacio adicional para la array.
Publicación traducida automáticamente
Artículo escrito por shuklarishabh356 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA