I have found an interesting problem like this: there are $$$n$$$ kind of cakes and for $$$1 \le i \le n$$$, there are $$$a_i$$$ cakes of the $$$i-$$$th kind. We need to take out as much as $$$k-$$$ tuples of distinct cakes. So with the given value of $$$k \ge 1$$$ and array $$$a_1,a_2,...,a_n$$$, what is the maximum number of tuples can we get?

For example: we have $$$4$$$ kinds of cake as $$$(A,B,C,D)$$$ with amounts: $$$a[4] = (20,30,40,50)$$$ and $$$k=3$$$. We can get at most $$$45$$$ tuples as: $$$5$$$ tuples $$$(A,B,C)$$$ and $$$15$$$ tuples $$$(A,C,D)$$$ and $$$25$$$ tuples $$$(B,C,D)$$$.

I came up with this idea to solve as follow:

By this idea, for the test case as: $$$a[5] = (1,2,3,1000,1000)$$$ and $$$k=4$$$, I got the answer is $$$3$$$ after some iterations. And by checking with some other tricky test cases, I'm pretty sure this idea is true.

I have two questions: Is this problem new? And how to find a proof for this approach? Thanks for your help.

I wonder which problem in the contest of Codeforces is the hardest one.

When I sort the problem list of Codeforces base on number of Accepted submission of user, I find out some problems as follow:

111E - Petya and Rectangle 68E - Contact

What is your opinion? :D

I have taken part in the team selection test of my school for Olympiad and there are some difficult problems remaining unsolved during this contest. Hope some one can help me with the outline idea, thanks so much!

Problem 1.

Let S be a string with length |S| <  = 10⁴ and S₁, S₂, ..., S_k are all distinct sub-strings of S (sub-string of S can be received by deleting some or all characters from S). Let f_i be be number of occurrence of sub-strings S_i with 1 ≤ i ≤ k. Find the total in which 2 ≤ M ≤ 10⁹. There are T ≤ 50 tests and each test includes string S and number M. Example:

input:

2
zoo
10
@#$%
1000000

output:

2
16

Problem 2.

Let (a_n) be a positive integer sequence and a key X be a positive number. Count the number of ordered triples (i, j, k) such that a_i + a_j + a_k ≥ X. There are T ≤ 50 test and each test includes number n ≤ 5000, X ≤ 10¹² indicates the size of sequences, the key, respectively and n terms of sequence a₁, a₂, ..., a_n such that 1 ≤ a_i ≤ 10⁹, i = 1, 2, 3, ..., n. Example:

input:

2
5 300
100 100 100 100 100
5 301
100 100 100 100 100

output:

60
0

Problem 3.

Balanced number is a positive integer satisfied that: (1) The amount of even digit equals to the amount of odd digits. (2) The sum of even digits equals to the sum of odd digits. Ex: 1982, 11822989 are balanced numbers. Given L, R are two positive integer such that 1 ≤ L ≤ R ≤ 10¹². Count the number of balanced numbers in the interval [L;R]. There are T ≤ 100 tests, each test includes 2 numbers L, R. Example:

input:

2
1 10000
45645 10987656

output:

450
29993

Problem 4.

Symmetric number is a positive integer greater than 9 and be unchanged when reading it from the left to right and from the right to left. Asymmetric number is a positive integer that not contain any symmetric number. Ex: 96276 , 1234 are asymmetric number. Given L, R such that 1 ≤ L ≤ R ≤ 10¹⁸. Count the number of asymmetric numbers in the interval [L;R]. There are T ≤ 100 tests, each test includes 2 numbers L, R. Example:

input:

2
123 321
123456789 987654321

output:

153
167386971