codeforces-scrape

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

364A.md (1166B)


      1 Source: https://codeforces.com/problemset/problem/364/A
      2 
      3 A. 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 You have a string of decimal digits *s*. Let's define *b**ij* = *s**i*·*s**j*. Find in matrix *b* the number of such rectangles that the sum *b**ij* for all cells (*i*, *j*) that are the elements of the rectangle equals *a* in each rectangle.
     22 
     23 A rectangle in a matrix is a group of four integers (*x*, *y*, *z*, *t*) (*x* ≤ *y*, *z* ≤ *t*). The elements of the rectangle are all cells (*i*, *j*) such that *x* ≤ *i* ≤ *y*, *z* ≤ *j* ≤ *t*.
     24 
     25 Input
     26 
     27 The first line contains integer *a* (0 ≤ *a* ≤ 109), the second line contains a string of decimal integers *s* (1 ≤ |*s*| ≤ 4000).
     28 
     29 Output
     30 
     31 Print a single integer — the answer to a problem.
     32 
     33 Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 10  
     41 12345
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 6
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 16  
     54 439873893693495623498263984765
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 40
     61 ```