An Animal Contest 6 P4 - Buffet

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Java 2.0s
Memory limit: 256M

Problem types

Kyriakos Grizzly wasn't satisfied enough with his previous parties so he decided to host an even bigger one, this time as a buffet! Kyriakos has invited N guests over, with the i^\text{th} guest initially receiving a_i nutritious dishes of food. Once everyone arrives, they will start eating their food, which will be done in rounds.

In each round, each guest will eat exactly 1 dish, thus decreasing all a_i by 1. Afterwards, a waiter will come by, choose any guest x and serve them S dishes, thus increasing a_x by S. In order to make things fair, each guest must have at least 1 dish available to eat in order for a round to proceed. Otherwise, no more rounds of food are eaten and the buffet ends. Since Kyriakos Grizzly wants the buffet to last as long as possible, help him determine the maximum number of rounds that could be done if the waiter chose optimally, or determine that the guests will never run out of food!


1 \le N \le 5 \times 10^5

1 \le S \le 10^9

1 \le a_i \le 10^9

Subtask 1 [40%]

1 \le N \le 5 \times 10^3

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains two integers N and S.

The next line contains N space separated integers a_i, the initial values of the array.

Output Specification

On one line, output the maximum number of rounds that can be done. If there is no limit on the number of rounds, output INF instead.

Sample Input 1

3 2
2 1 2

Sample Output 1


Explanation for Sample Output 1

The initial number of dishes each guest has is [2, 1, 2]. One possible ordering the waiter could follow is as follows:

Round 1: Choose x = 2. The number of dishes left is [1, 2, 1].

Round 2: Choose x = 3. The number of dishes left is [0, 1, 2]. Since a_1 = 0, the buffet ends.

Notice that if the waiter chose to serve guest 3 for the first round, only 1 round of food can be eaten.

Sample Input 2

3 4
1 2 3

Sample Output 2


Sample Input 3

5 2
1 4 4 6 9

Sample Output 3



There are no comments at the moment.