Решение задачи OR в матрице с Codeforces

Без пояснения   Просмотров: 26


Определим логический OR как операцию над двумя логическими значениями (то есть, значениями, которые принадлежат множеству {0, 1}), которая даёт 1, если один или оба операнда равны 1, в противном случае операция даёт 0. Можно определить логическое OR трех или более логических значений аналогичным образом:

, где , равняется 1, если какое-то из a i = 1, в противном случае результат равняется 0.

У Нама есть матрица A, состоящая из m строк и n столбцов. Строки пронумерованы от 1 до m, столбцы пронумерованы от 1 до n. Элемент в строке i (1 ≤ i ≤ m) и столбце j (1 ≤ j ≤ n) обозначается как A ij. Все элементы A равны либо 0, либо 1. По матрице A Нам строит матрицу B того же размера, используя следующюю формулу:

.

( B ij — OR всех элементов в строке i со всеми элементами столбца j матрицы A)

Нам дает вам матрицу B и бросает вызов: сможете ли вы угадать матрицу A? Хотя Нам умен, он вполне мог ошибиться в подсчете матрицы B, так как размеры матрицы A могут быть очень большими.

Код


#include <bits/stdc++.h>
using namespace std;
int main(){
	int m,n;
	cin>>m>>n;
	int matrixA[109][109];
	int matrixB[109][109];
	for(int i = 0;i<m;i++){
		for(int j = 0;j<n;j++){
			matrixA[i][j] = 1;
		}   
	}
	for(int i = 0;i<m;i++){
		for(int j = 0;j<n;j++){
			cin>>matrixB[i][j];
			if(matrixB[i][j] == 0){
				for(int k = 0;k<m;k++){
					matrixA[k][j] = 0;
				}
				for(int k = 0;k<n;k++){
					matrixA[i][k] = 0;
				}
			}
		}
	}
	for(int i = 0;i<m;i++){
		for(int j = 0;j<n;j++){
			int tmp = 0;
			for(int k = 0;k<m;k++){
				tmp |= matrixA[k][j];
			}
			for(int k = 0;k<n;k++){
				tmp |= matrixA[i][k];
			}
			if(tmp != matrixB[i][j]){
				cout<<"NO";
				return 0;
			}
		}
	}
	cout<<"YES"<<endl;
	for(int i = 0;i<m;i++){
		for(int j = 0;j<n;j++){
			cout << matrixA[i][j]<< " ";
		}
		cout<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться