This round was unusual: some of problems was prepared by students and employees of Saratov State U for some of past olympiads and one of problems was prepared by dalex for Codeforces regular round but was not used there.
Let's sort the array in nonincreasing order. Now the answer is some of the first flash-drives. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.
Complexity: O(nlogn).
Let's denote cnti — the number of books of i th genre. The answer to problem is equals to 
. In first sum we are calculating the number of good pairs, while in second we are subtracting the number of bad pairs from the number of all pairs.
Complexity: O(n + m2) or O(n + m).
Denote s — the sum of elements in array. If s is divisible by n then the balanced array consists of n elements 
. In this case the difference between maximal and minimal elements is 0. Easy to see that in any other case the answer is greater than 0. On the other hand the array consists of 
numbers 
and 
numbers 
is balanced with the difference equals to 1. Let's denote this balanced array b. To get array b let's sort array a in nonincreasing order and match element ai to element bi. Now we should increase some elements and decrease others. In one operation we can increase some element and decrease another, so the answer is 
.
Complexity: O(nlogn).
609D - Гаджеты за доллары и фунты
TODO
609E - Минимальное остовное дерево по каждому ребру
TODO
TODO
