2036D.md (2032B)
1 Source: https://codeforces.com/problemset/problem/2036/D 2 3 D. I Love 1543 4 5 time limit per test 6 7 2 seconds 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 One morning, Polycarp woke up and realized that $1543$ is the most favorite number in his life. 22 23 The first thing that Polycarp saw that day as soon as he opened his eyes was a large wall carpet of size $n$ by $m$ cells; $n$ and $m$ are even integers. Each cell contains one of the digits from $0$ to $9$. 24 25 Polycarp became curious about how many times the number $1543$ would appear in all layers$^{\text{∗}}$ of the carpet when traversed clockwise. 26 27 $^{\text{∗}}$The first layer of a carpet of size $n \times m$ is defined as a closed strip of length $2 \cdot (n+m-2)$ and thickness of $1$ element, surrounding its outer part. Each subsequent layer is defined as the first layer of the carpet obtained by removing all previous layers from the original carpet. 28 29 Input 30 31 The first line of the input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The following lines describe the test cases. 32 33 The first line of each test case contains a pair of numbers $n$ and $m$ ($2 \leq n, m \leq 10^3$, $n, m$ — even integers). 34 35 This is followed by $n$ lines of length $m$, consisting of digits from $0$ to $9$ — the description of the carpet. 36 37 It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $10^6$. 38 39 Output 40 41 For each test case, output a single number — the total number of times $1543$ appears in all layers of the carpet in the order of traversal clockwise. 42 43 Example 44 45 Input 46 47 ``` 48 8 49 50 2 4 51 52 1543 53 54 7777 55 56 2 4 57 58 7154 59 60 8903 61 62 2 4 63 64 3451 65 66 8888 67 68 2 2 69 70 54 71 72 13 73 74 2 2 75 76 51 77 78 43 79 80 2 6 81 82 432015 83 84 512034 85 86 4 4 87 88 5431 89 90 1435 91 92 5518 93 94 7634 95 96 6 4 97 98 5432 99 100 1152 101 102 4542 103 104 2432 105 106 2302 107 108 5942 109 ``` 110 111 Output 112 113 ``` 114 1 115 1 116 0 117 1 118 0 119 2 120 2 121 2 122 ``` 123 124 Note 125 126  Occurrences of $1543$ in the seventh example. Different layers are colored in different colors.