# 111qqz的小窝

## codeforces edu #29 E. Turn Off The TV (思维，乱搞)

wa了2次。。原因是没认真看题，l,r的范围的最小值是从0开始而不是1。所以总体来说是道水题（调教场的题这么水了么。。。

## 1303: [CQOI2009]中位数图

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2480  Solved: 1529
[Submit][Status][Discuss]

7 4
5 7 2 4 3 1 6

4

N<=100000

## 1637: [Usaco2007 Mar]Balanced Lineup

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 503  Solved: 336
[Submit][Status][Discuss]

## Description

Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族0和种族1的牛的数量相等。 请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。 输入中，每个种族至少有一头牛，没有两头牛的坐标相同。

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

## Sample Output

11

1 1 0 1 0 1 1
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

<——– 平衡的 ——–>
1 1 0 1 0 1 1
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

## codeforces 484 B Maximum Value (暴力乱搞)

Let us iterate over all different aj. Since we need to maximize , then iterate all integer x (suchx divisible by aj) in range from 2aj to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum ai, such ai < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM)

Sort the array and just maintain another array A of 10^6 elements where index i stores element just smaller than i

For example consider sorted array [2,4,7,11], then

A(0 indexed) will be [-1,-1,-1,2,2,4,4,4,7,7,7,7,11...]

-1 means no element is smaller than i.

## codeforces #322 div 2 C. Developing Skills(乱搞)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya loves computer games. Finally a game that he’s been waiting for so long came out!

The main character of this game has n different skills, each of which is characterized by an integer ai from 0 to 100. The higher the numberai is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values ​​of  for all i from 1 to n. The expression ⌊ x⌋ denotes the result of rounding the number x down to the nearest integer.

At the beginning of the game Petya got k improvement units as a bonus that he can use to increase the skills of his character and his total rating. One improvement unit can increase any skill of Petya’s character by exactly one. For example, if a4 = 46, after using one imporvement unit to this skill, it becomes equal to 47. A hero’s skill cannot rise higher more than 100. Thus, it is permissible that some of the units will remain unused.

Your task is to determine the optimal way of using the improvement units so as to maximize the overall rating of the character. It is not necessary to use all the improvement units.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 107) — the number of skills of the character and the number of units of improvements at Petya’s disposal.

The second line of the input contains a sequence of n integers ai (0 ≤ ai ≤ 100), where ai characterizes the level of the i-th skill of the character.

Output

The first line of the output should contain a single non-negative integer — the maximum total rating of the character that Petya can get using k or less improvement units.

Sample test(s)
input

output

input

output

input

output

Note

In the first test case the optimal strategy is as follows. Petya has to improve the first skill to 10 by spending 3 improvement units, and the second skill to 10, by spending one improvement unit. Thus, Petya spends all his improvement units and the total rating of the character becomes equal to lfloor frac{100}{10} rfloor +  lfloor frac{100}{10} rfloor = 10 + 10 =  20.

In the second test the optimal strategy for Petya is to improve the first skill to 20 (by spending 3 improvement units) and to improve the third skill to 20 (in this case by spending 1 improvement units). Thus, Petya is left with 4 improvement units and he will be able to increase the second skill to 19 (which does not change the overall rating, so Petya does not necessarily have to do it). Therefore, the highest possible total rating in this example is .

In the third test case the optimal strategy for Petya is to increase the first skill to 100 by spending 1 improvement unit. Thereafter, both skills of the character will be equal to 100, so Petya will not be able to spend the remaining improvement unit. So the answer is equal to .

a用来记录原始值，b用来记录mod10的余数与１０的差..

sum/10是一个限制条件