262144 Revisited
다이아몬드 I의견: 0
Bessie likes downloading games to play on her cell phone, even though she does
find the small touch screen rather cumbersome to use with her large hooves.
She is particularly intrigued by the current game she is playing. The game
starts with a sequence of \(N\) positive integers \(a_1,a_2,\ldots,a_N\)
(\(2\le N\le 262,144\)), each in the range \(1\ldots 10^6\). In one move, Bessie
can take two adjacent numbers and replace them with a single number equal to one
greater than the maximum of the two (e.g., she might replace an adjacent pair
\((5,7)\) with an \(8\)). The game ends after \(N-1\) moves, at which point only a
single number remains. The goal is to minimize this final number.
Bessie knows that this game is too easy for you. So your job is not just to play
the game optimally on \(a\), but for every contiguous subsequence of \(a\).
Output the sum of the minimum possible final numbers over all \(\frac{N(N+1)}{2}\)
contiguous subsequences of \(a\).
Problem credits: Benjamin Qi
SCORING
- Test cases 2-3 satisfy \(N\le 300\).
- Test cases 4-5 satisfy \(N\le 3000\).
- In test cases 6-8, all values are at most \(40\).
- In test cases 9-11, the input sequence is non-decreasing.
- Test cases 12-23 satisfy no additional constraints.
Problem credits: Benjamin Qi
First line contains \(N\).
The next line contains \(N\) space-separated integers denoting the input sequence.
A single line containing the sum.
6
1 3 1 2 1 10115There are \(\frac{6\cdot 7}{2}=21\) contiguous subsequences in total. For example,
the minimum possible final number for the contiguous subsequence \([1,3,1,2,1]\)
is \(5\), which can be obtained via the following sequence of operations:
original -> [1,3,1,2,1]
combine 1&3 -> [4,1,2,1]
combine 2&1 -> [4,1,3]
combine 1&3 -> [4,4]
combine 4&4 -> [5]
Here are the minimum possible final numbers for each contiguous subsequence:
final(1:1) = 1
final(1:2) = 4
final(1:3) = 5
final(1:4) = 5
final(1:5) = 5
final(1:6) = 11
final(2:2) = 3
final(2:3) = 4
final(2:4) = 4
final(2:5) = 5
final(2:6) = 11
final(3:3) = 1
final(3:4) = 3
final(3:5) = 4
final(3:6) = 11
final(4:4) = 2
final(4:5) = 3
final(4:6) = 11
final(5:5) = 1
final(5:6) = 11
final(6:6) = 10
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Platinum
평가 및 의견
262144 Revisited
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
262144 Revisited