codeforces-scrape

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

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  ![](https://espresso.codeforces.com/0d1f5353f0676a88bb7778cc0d17f8f72351aae8.png) Occurrences of $1543$ in the seventh example. Different layers are colored in different colors.