No.2931 Shibuya 109
レベル :
/ AI推定難易度 : 1350
/ 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 :
kusirakusira
/ テスター :
hirayuu_yc
nouka28
👑
loop0919
tnodino
amesyu
uruzunyaa
タグ : / 解いたユーザー数 46
作問者 :
kusirakusira
/ テスター :
tnodino
問題文最終更新日: 2024-10-12 14:04:56
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
第3回緑以下コンテスト エキストラ
(順位表)
の他の問題:
Problem Statement
There is a sequence $A$ of length $N$ consisting of 1, 0, and 9.
For a pair of integers $(l, r)$ satisfying $1 \le l \le r \le N$, define the function $f(l ,r)$ as follows.
Find the digit sum of $\left\lfloor\frac{f(l, r)}{9}\right\rfloor$.$f(l, r) :=$ the value obtained by regarding the $l$-th through $r$-th elements of the sequence $A$ as strings, concatenating them, and regarding the result as a number in base $10$
Answer $Q$ queries.
What is the digit sum?
The digit sum of a positive integer $n$ is defined as the sum of its digits when written in base $10$. For example, the digit sum of $2024$ is $2+0+2+4=8$.Constraints
- $1 \le N, Q \le 5 \times 10^5$
- $A_i \in$ {$0, 1, 9$}
- $1 \le l \le r \le N$
- $A_l \neq 0$
- There are at most $8$ indices $i$ satisfying $A_i = 1 \ (1 \le i \le N)$
- All input values are integers
Input
The input is given from standard input in the following format.
$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $l_1\ r_1$ $l_2\ r_2$ $\vdots$ $l_Q r_Q$
Output
Print $Q$ lines. On line $i$ $(1 \leqq i \leqq Q)$, print the answer to the $i$-th query.
Sample
Sample 1
Input
9 3 1 0 9 1 0 9 1 0 9 3 5 1 4 1 9
Output
2 4 18
For the first case, the value obtained by concatenating the $3$-rd through $5$-th elements of the sequence $A$ as strings is $910$, so $f(3, 5)$ is $910$.
Since $\left\lfloor\frac{f(3, 5)}{9}\right\rfloor = \left\lfloor\frac{910}{9}\right\rfloor = 101$, the digit sum is $2(=1+0+1)$.
Sample 2
Input
23 8 1 0 1 9 1 0 1 0 0 0 9 1 9 9 0 9 1 0 0 0 0 1 1 4 20 5 22 1 19 11 22 3 14 13 20 3 3 22 23
Output
44 51 74 19 33 6 0 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。