Piling Papers
다이아몬드 V의견: 0
Farmer John wrote down \(N\) (\(1\le N\le 300\)) digits on pieces of paper. For
each \(i\in [1,N]\), the \(i\)th piece of paper contains digit \(a_i\)
(\(1 \leq a_i \leq 9\)).
The cows have two favorite integers \(A\) and \(B\) (\(1\le A\le B< 10^{18}\)), and
would like you to answer \(Q\) (\(1\le Q\le 5\cdot 10^4\)) queries. For the \(i\)th
query, the cows will move left to right across papers \(l_i\dots r_i\)
(\(1\le l_i\le r_i\le N\)), maintaining an initially empty pile of papers. For
each paper, they will either add it to the top of the pile, to the bottom of the
pile, or neither. In the end, they will read the papers in the pile from top to
bottom, forming an integer. Over all \(3^{r_i-l_i+1}\) ways for the cows to make
choices during this process, count the number of ways that result in the cows
reading an integer in \([A,B]\) inclusive, and output this number modulo \(10^9+7\).
Problem credits: Jesse Choe
SCORING
- Inputs 2-3: \(B<100\)
- Inputs 4-5: \(A=B\)
- Inputs 6-13: No additional constraints.
Problem credits: Jesse Choe
The first line contains three space-separated integers \(N\), \(A\), and \(B\).
The second line contains \(N\) space-separated digits \(a_1, a_2, \dots, a_N\).
The third line contains an integer \(Q\), the number of queries.
The next \(Q\) lines each contain two space-separated integers \(l_i\) and \(r_i\).
For each query, a single line containing the answer.
5 13 327
1 2 3 4 5
3
1 2
1 3
2 52
18
34For the first query, there are nine ways Bessie can stack papers when reading
the interval \([1, 2]\):
- Bessie can ignore \(1\) then ignore \(2\), getting \(0\).
- Bessie can ignore \(1\) then add \(2\) to the top of the stack, getting \(2\).
- Bessie can ignore \(1\) then add \(2\) to the bottom of the stack, getting \(2\).
- Bessie can add \(1\) to the top of the stack then ignore \(2\), getting \(1\).
- Bessie can add \(1\) to the top of the stack then add \(2\) to the top of the stack, getting \(21\).
- Bessie can add \(1\) to the top of the stack then add \(2\) to the bottom of the stack, getting \(12\).
- Bessie can add \(1\) to the bottom of the stack then ignore \(2\), getting \(1\).
- Bessie can add \(1\) to the bottom of the stack then add \(2\) to the top of the stack, getting \(21\).
- Bessie can add \(1\) to the bottom of the stack then add \(2\) to the bottom of the stack, getting \(12\).
Only the \(2\) ways that give \(21\) yield a number between \(13\) and \(327\), so the
answer is \(2\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Gold
평가 및 의견
Piling Papers
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Piling Papers