codeforces-scrape

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

1801A.md (3375B)


      1 Source: https://codeforces.com/problemset/problem/1801/A
      2 
      3 A. The Very Beautiful Blanket
      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 Kirill wants to weave the very beautiful blanket consisting of $n \times m$ of the same size square patches of some colors. He matched some non-negative integer to each color. Thus, in our problem, the blanket can be considered a $B$ matrix of size $n \times m$ consisting of non-negative integers.
     22 
     23 Kirill considers that the blanket is very beautiful, if for each submatrix $A$ of size $4 \times 4$ of the matrix $B$ is true:
     24 
     25 * $A_{11} \oplus A_{12} \oplus A_{21} \oplus A_{22} = A_{33} \oplus A_{34} \oplus A_{43} \oplus A_{44},$
     26 * $A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42},$
     27 
     28 where $\oplus$ means [bitwise exclusive OR](https://en.wikipedia.org/wiki/Exclusive_or)
     29 
     30 Kirill asks you to help her weave a very beautiful blanket, and as colorful as possible!
     31 
     32 He gives you two integers $n$ and $m$.
     33 
     34 Your task is to generate a matrix $B$ of size $n \times m$, which corresponds to a very beautiful blanket and in which the number of different numbers maximized.
     35 
     36 Input
     37 
     38 The first line of input data contains one integer number $t$ ($1 \le t \le 1000$) — the number of test cases.
     39 
     40 The single line of each test case contains two integers $n$ and $m$ $(4 \le n, \, m \le 200)$ — the size of matrix $B$.
     41 
     42 It is guaranteed that the sum of $n \cdot m$ does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, in first line output one integer $cnt$ $(1 \le cnt \le n \cdot m)$ — the maximum number of different numbers in the matrix.
     47 
     48 Then output the matrix $B$ $(0 \le B_{ij} \lt 2^{63})$ of size $n \times m$. If there are several correct matrices, it is allowed to output any one.
     49 
     50 It can be shown that if there exists a matrix with an optimal number of distinct numbers, then there exists among suitable matrices such a $B$ that $(0 \le B_{ij} \lt 2^{63})$.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 4
     58 
     59 5 5
     60 
     61 4 4
     62 
     63 4 6
     64 
     65 6 6
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 25
     72 9740 1549 9744 1553 9748
     73 1550 1551 1554 1555 1558
     74 10252 2061 10256 2065 10260
     75 2062 2063 2066 2067 2070
     76 10764 2573 10768 2577 10772
     77 16
     78 3108 3109 3112 3113
     79 3110 3111 3114 3115
     80 3620 3621 3624 3625
     81 3622 3623 3626 3627
     82 24
     83 548 549 552 553 556 557
     84 550 551 554 555 558 559
     85 1060 1061 1064 1065 1068 1069
     86 1062 1063 1066 1067 1070 1071
     87 36
     88 25800 25801 25804 25805 25808 25809
     89 25802 4294993099 25806 4294993103 25810 4294993107
     90 26312 26313 26316 26317 26320 26321
     91 26314 4294993611 26318 4294993615 26322 4294993619
     92 26824 26825 26828 26829 26832 26833
     93 26826 4294994123 26830 4294994127 26834 4294994131
     94 ```
     95 
     96 Note
     97 
     98 In the first test case, there is only 4 submatrix of size $4 \times 4$. Consider a submatrix whose upper-left corner coincides with the upper-left corner of the matrix $B$:
     99 
    100 $ \left[ {\begin{array}{cccc} 9740 & 1549 & 9744 & 1553 \\ 1550 & 1551 & 1554 & 1555 \\ 10252 & 2061 & 10256 & 2065 \\ 2062 & 2063 & 2066 & 2067 \\ \end{array} } \right] $
    101 
    102 $9740 \oplus 1549 \oplus 1550 \oplus 1551$ $=$ $10256 \oplus 2065 \oplus 2066 \oplus 2067$ $=$ $8192$;
    103 
    104 $10252 \oplus 2061 \oplus 2062 \oplus 2063$ $=$ $9744 \oplus 1553 \oplus 1554 \oplus 1555$ $=$ $8192$.
    105 
    106 So, chosen submatrix fits the condition. Similarly, you can make sure that the other three submatrices also fit the condition.