codeforces-scrape

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

1439A1.md (2807B)


      1 Source: https://codeforces.com/problemset/problem/1439/A1
      2 
      3 A1. Binary Table (Easy Version)
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is the easy version of the problem. The difference between the versions is in the number of possible operations that can be made. You can make hacks if and only if you solved both versions of the problem.
     22 
     23 You are given a binary table of size $n \times m$. This table consists of symbols $0$ and $1$.
     24 
     25 You can make such operation: select $3$ different cells that belong to one $2 \times 2$ square and change the symbols in these cells (change $0$ to $1$ and $1$ to $0$).
     26 
     27 Your task is to make all symbols in the table equal to $0$. You are allowed to make at most $3nm$ operations. You don't need to minimize the number of operations.
     28 
     29 It can be proved that it is always possible.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \leq t \leq 5000$) — the number of test cases. The next lines contain descriptions of test cases.
     34 
     35 The first line of the description of each test case contains two integers $n$, $m$ ($2 \leq n, m \leq 100$).
     36 
     37 Each of the next $n$ lines contains a binary string of length $m$, describing the symbols of the next row of the table.
     38 
     39 It is guaranteed that the sum of $nm$ for all test cases does not exceed $20000$.
     40 
     41 Output
     42 
     43 For each test case print the integer $k$ ($0 \leq k \leq 3nm$) — the number of operations.
     44 
     45 In the each of the next $k$ lines print $6$ integers $x_1, y_1, x_2, y_2, x_3, y_3$ ($1 \leq x_1, x_2, x_3 \leq n, 1 \leq y_1, y_2, y_3 \leq m$) describing the next operation. This operation will be made with three cells $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$. These three cells should be different. These three cells should belong into some $2 \times 2$ square.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 2 2
     54 10
     55 11
     56 3 3
     57 011
     58 101
     59 110
     60 4 4
     61 1111
     62 0110
     63 0110
     64 1111
     65 5 5
     66 01011
     67 11001
     68 00010
     69 11011
     70 10000
     71 2 3
     72 011
     73 101
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 1
     80 1 1 2 1 2 2
     81 2 
     82 2 1 3 1 3 2
     83 1 2 1 3 2 3
     84 4
     85 1 1 1 2 2 2 
     86 1 3 1 4 2 3
     87 3 2 4 1 4 2
     88 3 3 4 3 4 4
     89 4
     90 1 2 2 1 2 2 
     91 1 4 1 5 2 5 
     92 4 1 4 2 5 1
     93 4 4 4 5 3 4
     94 2
     95 1 3 2 2 2 3
     96 1 2 2 1 2 2
     97 ```
     98 
     99 Note
    100 
    101 In the first test case, it is possible to make only one operation with cells $(1, 1)$, $(2, 1)$, $(2, 2)$. After that, all symbols will be equal to $0$.
    102 
    103 In the second test case:
    104 
    105 * operation with cells $(2, 1)$, $(3, 1)$, $(3, 2)$. After it the table will be:
    106 
    107   ```
    108   011  
    109   001  
    110   000
    111   ```
    112 * operation with cells $(1, 2)$, $(1, 3)$, $(2, 3)$. After it the table will be:
    113 
    114   ```
    115   000  
    116   000  
    117   000
    118   ```
    119 
    120 In the fifth test case:
    121 
    122 * operation with cells $(1, 3)$, $(2, 2)$, $(2, 3)$. After it the table will be:
    123 
    124   ```
    125   010  
    126   110
    127   ```
    128 * operation with cells $(1, 2)$, $(2, 1)$, $(2, 2)$. After it the table will be:
    129 
    130   ```
    131   000  
    132   000
    133   ```