Norma
레이팅 미적용의견: 0
\(2^{nd}\) round, November \(8^{th}\), 2014
Mirko got an array of integers for his birthday from his grandmother Norma. As any other kid, he was hoping
for some money, but got an array. Luckily, in his town there is a pawn shop that buys up arrays. The cost of an
array of integers is m\(in \cdot ma\)\(x \cdot L\) kunas, where min is the minimal integer in the array, max is the maximal and L
is the array length. Mirko is going to sell a subsequence of consecutive numbers from his array. He calculated the
average price of all such subsequences.
In order to check his result, he wants you to do the same. He will be pleased with only the last 9 digits of the sum
of all prices, so you don’t need to bother with large and real numbers.
In test cases worth 40% of total points, it will hold \(N < 5\,000\).
The first line of input contains an integer N (1 ⩽N ⩽500 000).
Each of the following N lines contains a member of Mirko’s array. The members of the array will be integers from
the interval [1, \(10^{8}\)].
The first and only line of output must contain an integer, the last 9 digits of the required sum from the task. You
don’t need to output the leading zeroes of that \(9-di\)git integer.
2
1
3
4
2
4
1
4
6
8
1
3
9
7
4output
output
16
109
1042Clarification of the first example: The array consists of two integers, 1 and 3. The possible subsequences Mirko can
sell are (1), (3) and (1,3), their prices being 1, 9 and 6, respectively, which is 16 summed up. Clarification of the second
example: The possible subsequences Mirko can sell are (2), (4), (1), (4), (2, 4), (4, 1), (1, 4), (2,4,1), (4,1,4) and (2,4,1,4).
Their prices are 4, 16, 1, 16, 16, 8, 8, 12, 12 and 16, respectively, which is 109 summed up.
평가 및 의견
Norma
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Norma