Drought
골드 II의견: 0
The grass has dried up in Farmer John's pasture due to a drought. After hours of
despair and contemplation, FJ comes up with the brilliant idea of purchasing
corn to feed his precious cows.
FJ’s \(N\) (\(1 \leq N \leq 100\)) cows are arranged in a line such that the \(i\)th
cow in line has a non-negative integer hunger level of \(h_i\). As FJ’s cows are
social animals and insist on eating together, the only way FJ can decrease the
hunger levels of his cows is to select two adjacent cows \(i\) and \(i+1\) and feed
each of them a bag of corn, causing each of their hunger levels to decrease by
one.
FJ wants to feed his cows until all of them have the same non-negative hunger
level. Although he doesn't know his cows' exact hunger levels, he
does know an upper bound on the hunger level of each cow; specifically, the
hunger level \(h_i\) of the \(i\)-th cow is at most \(H_i\) (\(0\le H_i\le 1000\)).
Your job is to count the number of \(N\)-tuples of hunger levels
\([h_1,h_2,\ldots,h_N]\) that are consistent with these upper bounds such that it
is possible for FJ to achieve his goal, modulo \(10^9+7\).
Problem credits: Arpan Banerjee and Benjamin Qi
SCORING
\(N\) is even in even-numbered tests and odd in odd-numbered tests.
- Tests 3 and 4 satisfy \(N\le 6\) and \(H_i \le 10\).
- Tests 5 through 10 satisfy \(N\le 50\) and \(H_i \le 100\).
- Tests 11 through 20 satisfy no further constraints.
Problem credits: Arpan Banerjee and Benjamin Qi
The first line contains \(N\).
The second line contains \(H_1,H_2,\ldots,H_N\).
The number of \(N\)-tuples of hunger levels modulo \(10^9+7\).
3
9 11 7241There are \((9+1)\cdot (11+1)\cdot (7+1)\) \(3\)-tuples \(h\) that are consistent with
\(H\).
One of these tuples is \(h=[8,10,5]\). In this case, it is possible to make all
cows have equal hunger values: give two bags of corn to both cows \(2\) and \(3\),
then give five bags of corn to both cows \(1\) and \(2\), resulting in each cow
having a hunger level of \(3\).
Another one of these tuples is \(h=[0,1,0]\). In this case, it is impossible to
make the hunger levels of the cows equal.
4
6 8 5 9137평가 및 의견
Drought
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Drought