codeforces-scrape

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

1189C.md (3168B)


      1 Source: https://codeforces.com/problemset/problem/1189/C
      2 
      3 C. Candies!
      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 Consider a sequence of digits of length $2^k$ $[a_1, a_2, \ldots, a_{2^k}]$. We perform the following operation with it: replace pairs $(a_{2i+1}, a_{2i+2})$ with $(a_{2i+1} + a_{2i+2})\bmod 10$ for $0\le i \lt 2^{k-1}$. For every $i$ where $a_{2i+1} + a_{2i+2}\ge 10$ we get a candy! As a result, we will get a sequence of length $2^{k-1}$.
     22 
     23 Less formally, we partition sequence of length $2^k$ into $2^{k-1}$ pairs, each consisting of 2 numbers: the first pair consists of the first and second numbers, the second of the third and fourth $\ldots$, the last pair consists of the ($2^k-1$)-th and ($2^k$)-th numbers. For every pair such that sum of numbers in it is at least $10$, we get a candy. After that, we replace every pair of numbers with a remainder of the division of their sum by $10$ (and don't change the order of the numbers).
     24 
     25 Perform this operation with a resulting array until it becomes of length $1$. Let $f([a_1, a_2, \ldots, a_{2^k}])$ denote the number of candies we get in this process.
     26 
     27 For example: if the starting sequence is $[8, 7, 3, 1, 7, 0, 9, 4]$ then:
     28 
     29 After the first operation the sequence becomes $[(8 + 7)\bmod 10, (3 + 1)\bmod 10, (7 + 0)\bmod 10, (9 + 4)\bmod 10]$ $=$ $[5, 4, 7, 3]$, and we get $2$ candies as $8 + 7 \ge 10$ and $9 + 4 \ge 10$.
     30 
     31 After the second operation the sequence becomes $[(5 + 4)\bmod 10, (7 + 3)\bmod 10]$ $=$ $[9, 0]$, and we get one more candy as $7 + 3 \ge 10$.
     32 
     33 After the final operation sequence becomes $[(9 + 0) \bmod 10]$ $=$ $[9]$.
     34 
     35 Therefore, $f([8, 7, 3, 1, 7, 0, 9, 4]) = 3$ as we got $3$ candies in total.
     36 
     37 You are given a sequence of digits of length $n$ $s_1, s_2, \ldots s_n$. You have to answer $q$ queries of the form $(l_i, r_i)$, where for $i$-th query you have to output $f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}])$. It is guaranteed that $r_i-l_i+1$ is of form $2^k$ for some nonnegative integer $k$.
     38 
     39 Input
     40 
     41 The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the sequence.
     42 
     43 The second line contains $n$ digits $s_1, s_2, \ldots, s_n$ ($0 \le s_i \le 9$).
     44 
     45 The third line contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries.
     46 
     47 Each of the next $q$ lines contains two integers $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$) — $i$-th query. It is guaranteed that $r_i-l_i+1$ is a nonnegative integer power of $2$.
     48 
     49 Output
     50 
     51 Output $q$ lines, in $i$-th line output single integer — $f([s_{l_i}, s_{l_i + 1}, \ldots, s_{r_i}])$, answer to the $i$-th query.
     52 
     53 Examples
     54 
     55 Input
     56 
     57 ```
     58 8
     59 8 7 3 1 7 0 9 4
     60 3
     61 1 8
     62 2 5
     63 7 7
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 3
     70 1
     71 0
     72 ```
     73 
     74 Input
     75 
     76 ```
     77 6
     78 0 1 2 3 3 5
     79 3
     80 1 2
     81 1 4
     82 3 6
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 0
     89 0
     90 1
     91 ```
     92 
     93 Note
     94 
     95 The first example illustrates an example from the statement.
     96 
     97 $f([7, 3, 1, 7]) = 1$: sequence of operations is $[7, 3, 1, 7] \to [(7 + 3)\bmod 10, (1 + 7)\bmod 10]$ $=$ $[0, 8]$ and one candy as $7 + 3 \ge 10$ $\to$ $[(0 + 8) \bmod 10]$ $=$ $[8]$, so we get only $1$ candy.
     98 
     99 $f([9]) = 0$ as we don't perform operations with it.