codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

486B.md (2195B)


      1 Source: https://codeforces.com/problemset/problem/486/B
      2 
      3 B. OR in Matrix
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Let's define logical *OR* as an operation on two logical values (i. e. values that belong to the set {0, 1}) that is equal to 1 if either or both of the logical values is set to 1, otherwise it is 0. We can define logical *OR* of three or more logical values in the same manner:
     22 
     23 ![](https://espresso.codeforces.com/661f67f4b56b351d145dce2e9a87cd7c5f6a4d64.png) where ![](https://espresso.codeforces.com/7bcdd7440cc300269a3395fa037d5af6351c3221.png) is equal to 1 if some *a**i* = 1, otherwise it is equal to 0.
     24 
     25 Nam has a matrix *A* consisting of *m* rows and *n* columns. The rows are numbered from 1 to *m*, columns are numbered from 1 to *n*. Element at row *i* (1 ≤ *i* ≤ *m*) and column *j* (1 ≤ *j* ≤ *n*) is denoted as *A**ij*. All elements of *A* are either 0 or 1. From matrix *A*, Nam creates another matrix *B* of the same size using formula:
     26 
     27 ![](https://espresso.codeforces.com/4332dfa4828fa3b9679abe53387834c43c801689.png).
     28 
     29 (*B**ij* is *OR* of all elements in row *i* and column *j* of matrix *A*)
     30 
     31 Nam gives you matrix *B* and challenges you to guess matrix *A*. Although Nam is smart, he could probably make a mistake while calculating matrix *B*, since size of *A* can be large.
     32 
     33 Input
     34 
     35 The first line contains two integer *m* and *n* (1 ≤ *m*, *n* ≤ 100), number of rows and number of columns of matrices respectively.
     36 
     37 The next *m* lines each contain *n* integers separated by spaces describing rows of matrix *B* (each element of *B* is either 0 or 1).
     38 
     39 Output
     40 
     41 In the first line, print "NO" if Nam has made a mistake when calculating *B*, otherwise print "YES". If the first line is "YES", then also print *m* rows consisting of *n* integers representing matrix *A* that can produce given matrix *B*. If there are several solutions print any one.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 2 2  
     49 1 0  
     50 0 0
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 NO
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 2 3  
     63 1 1 1  
     64 1 1 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 YES  
     71 1 1 1  
     72 1 1 1
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 2 3  
     79 0 1 0  
     80 1 1 1
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 YES  
     87 0 0 0  
     88 0 1 0
     89 ```