Counting Haybales
플래티넘 II의견: 0
As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has \(N\)
(\(1\leq N \leq 5000\)) stacks of haybales. For each \(i\in [1,N]\), the \(i\)th stack
has \(h_i\) (\(1\le h_i\le 10^9\)) haybales. Bessie does not want any haybales to
fall, so the only operation she can perform is as follows:
- If two adjacent stacks' heights differ by exactly one, she can move the top haybale of the taller stack to the shorter stack.
How many configurations are obtainable after performing the above operation
finitely many times, modulo \(10^9+7\)? Two configurations are considered the same
if, for all \(i\), the \(i\)th stack has the same number of haybales in both.
Problem credits: Daniel Zhang
SCORING
- Inputs 1-3 satisfy \(N\le 10\).
- Input 4 satisfies \(1\le h_i\le 3\) for all \(i\).
- Inputs 5-7 satisfy \(|h_i-i|\le 1\) for all \(i\).
- Inputs 8-10 satisfy \(1\le h_i\le 4\) for all \(i\) and \(N\le 100\).
- Inputs 11-13 satisfy \(N\le 100\).
- Inputs 14-17 satisfy \(N\le 1000\).
- Inputs 18-21 satisfy no additional constraints.
Problem credits: Daniel Zhang
The first line contains \(T\) (\(1\le T\le 10\)), the number of independent test
cases, all of which must be solved to solve one input correctly.
Each test case consists of \(N\), and then a sequence of \(N\) heights. It is
guaranteed that the sum of \(N\) over all test cases does not exceed \(5000\).
Please output \(T\) lines, one for each test case.
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 54
4
5
15
9
8
19For the first test case, the four possible configurations are:
$$ (2,2,2,3), (2,2,3,2), (2,3,2,2), (3,2,2,2). $$
For the second test case, the four possible configurations are:
$$ (2,3,3,1),(3,2,3,1),(3,3,2,1), (3,3,1,2). $$
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Platinum
평가 및 의견
Counting Haybales
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Counting Haybales