codeforces-scrape

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

1895C.md (1329B)


      1 Source: https://codeforces.com/problemset/problem/1895/C
      2 
      3 C. Torn Lucky Ticket
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A ticket is a non-empty string of digits from $1$ to $9$.
     22 
     23 A lucky ticket is such a ticket that:
     24 
     25 * it has an even length;
     26 * the sum of digits in the first half is equal to the sum of digits in the second half.
     27 
     28 You are given $n$ ticket pieces $s_1, s_2, \dots, s_n$. How many pairs $(i, j)$ (for $1 \le i, j \le n$) are there such that $s_i + s_j$ is a lucky ticket? Note that it's possible that $i=j$.
     29 
     30 Here, the + operator denotes the concatenation of the two strings. For example, if $s_i$ is 13, and $s_j$ is 37, then $s_i + s_j$ is 1337.
     31 
     32 Input
     33 
     34 The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of ticket pieces.
     35 
     36 The second line contains $n$ non-empty strings $s_1, s_2, \dots, s_n$, each of length at most $5$ and consisting only of digits from $1$ to $9$.
     37 
     38 Output
     39 
     40 Print a single integer — the number of pairs $(i, j)$ (for $1 \le i, j \le n$) such that $s_i + s_j$ is a lucky ticket.
     41 
     42 Examples
     43 
     44 Input
     45 
     46 ```
     47 10
     48 
     49 5 93746 59 3746 593 746 5937 46 59374 6
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 20
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 5
     62 
     63 2 22 222 2222 22222
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 13
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 3
     76 
     77 1 1 1
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 9
     84 ```