# Football Game

Posted: 29 Sep, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### Your task is to print the maximum possible pounds that the club will gain with the help of ticket sales.

##### Input Format:
``````The first line of input contains two integers 'M', and 'N', where 'M' denotes the number of rows and 'N' denotes the number of fans waiting in the line to get a ticket.

The second line contains 'M' single space-separated integers where 'VACANT_SEATS[i]' denotes the number of seats initially empty in the ith row.
``````
##### Output Format:
``````For each output, print a single integer denoting the maximum pounds the club will earn.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= 'M' <= 5 * 10^5
1 <= 'N' <= 10^9
1 <= 'VACANT_SEATS[i]' <=10^9

Time Limit: 1 sec
`````` Approach 1

Lets first discuss the approach in steps with an example,

1. The idea is to initially sort the array.
2. Now, let the sorted array be {1, 2, 4, 6, 8} and the number of fans is 8. The team can sell a ticket of 8 pounds and again a ticket of 7 pounds as the maximum number of vacant seats remain in the last row only.
3. The number of vacant seats thus becomes {1, 2, 4, 6, 6} and the number of fans becomes 6. Now, we can sell 2 tickets of 6 pounds and 2 of 5 pounds i.e 2 * (6 + 5) pounds can be earned.
4. The number of vacant seats thus becomes {1, 2, 4, 4, 4} and the number of fans becomes 2. Now, we can sell 3 tickets of 4 pounds and 3 of 3 pounds i.e 3 * (4 + 3) pounds can be earned but the number of fans in the queue is 2. Thus, we can sell 2 tickets worth 4 pounds.

Algorithm:

1. Sort the given array.
2. Maintain a counter variable C and initialize it by 1.
3. Maintain a variable ANS to store the answer and declare it with 0.
4. Iterate over the array from the end.
• If‘N is less than or equal to zero, break.
• Initialize DIF = VACANT_SEATS[i] - VACANT_SEATS[i - 1].
• If N >= DIF * C, we will add the sum of sequence (VACANT_SEATS[i - 1] + 1, VACANT_SEATS[i - 1] + 2,...,VACANT_SEATS[i - 1] + DIF - 1), C number of times.
• Otherwise, initialize X = N / C, MAX= VACANT_SEATS[i - 1] + DIF
• If X > 0, we will add the sum of sequence (MAX - X + 1, MAX - X + 2,..., MAX), C number of times. Decrease N by X * C and MAX by X.
• Add (MAX * N) to ANS and now there is no person left, N = 0.
• Decrease N by DIF * C, Increase C by 1.
5. If N is still greater than zero,
• Decrease C by 1.
• Initialize X = N / C, MAX = VACANT_SEATS
• If X > 0, we will add the sum of sequence (MAX - X + 1, MAX - X + 2,..., MAX), C number of times. Decrease N by X * C and MAX by X.
• Add (MAX * N) to ANS and now there is no person left, N = 0.
6. Print ANS.