Monster Monster
Source: codechef
Difficulty: 1184

Monster Monster
You have run into an army of$N$monsters, and you must defeat them all!
Each monster has a certain amount of health points (HP) which you know beforehand — the$i$-th monster has$H_{i}$HP.
You can attack exactly
one
monster per day, and only if your attack stat$A$is
greater than or equal to
the monster's HP. In other words, you can attack a monster only if you can defeat it in a single hit.
At the end of each day, the HP of each alive monster increases by a fixed value,$X$.
Find the minimum possible value of the attack stat$A$you need to be able to kill all the monsters.
Note that you're allowed to kill the monsters in any order you like.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains two space-separated integers$N$and$X$— the number of monsters and the amount by which HP increases per day, respectively.
The next line contains$N$space separated integers,$H_{1}, H_{2}, \ldots, H_{N}$, the initial HP stats of the$N$monsters.
Output Format
For each test case, output on a new line a single integer, the minimum attack stat$A$needed to be able to kill all monsters.
Constraints$1 \leq T \leq 2 \times 10^{5}$$1 \leq N \leq 2 \times 10^{5}$$1 \leq X \leq 10^{9}$$1 \leq H_{i} \leq 10^{9}$The sum of$N$over all test cases won't exceed$2 \times 10^{5}$.
Sample 1:
Explanation:
Test case$1$:
We can kill all monsters with an attack stat of$21$as follows:
On the first day, we kill the monster with$2$HP. The HP stats of the remaining monsters increase by$X = 10$each, and will become$[13, 11]$.
On the second day, we kill the monster with$13$HP. The HP stat of the remaining monster will increase by$10$again, and will be$21$.
On the third day, we kill the remaining monster with$21$HP.
It can be proven that we cannot kill all the monsters with an attack stat of less than$21$, so this is optimal.
For example, with an attack stat of$20$, we'll be able to kill any two monsters but on the third day, the remaining monster will have more than$20$HP and we'll be unable to kill it.
Test case$2$:
Kill the first monster (with a HP of$10$). The other monsters can be killed in any order afterwards.

Sample Input:
2
3 10
3 1 2
5 1
10 3 2 1 2

Sample Output:
21
10

C++ solution:
// #include <bits/stdc++.h>
// using namespace std;

// int main() {
//  // your code goes here
//  int t;
//  cin>>t;
//  while(t--){
//      int n,x; //n-->> no of monster and x-->> amount of hp increses
//      cin>>n>>x;
//      vector<long>arr(n);
//      int i;
//      for( i=0;i<n;i++){
//          cin>>arr[i];
//      }
//      sort(arr.begin(),arr.end());
//      vector<long>brr;
//      int j=0;
//      long cal;
//      for(i=n-1;i>=0;i--){
//          cal=x*j+arr[i];
//          brr.push_back(cal);
//          j++;
//      }
//      long maxi=LONG_MIN;
//      for(i=0;i<n;i++){
//          maxi=max(brr[i],maxi);
//      }
//      cout<<maxi<<endl;
       
        
//  }

// }

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); // Fast IO
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        long x;
        cin >> n >> x;
        
        vector<long> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        sort(arr.begin(), arr.end());
        
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long temp = arr[i] + (n - i - 1) * x;
            ans = max(ans, temp);
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    // Faster input/output handling
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    // `inception`: Number of test cases
    inceptionStr, _ := reader.ReadString('\n')
    inception, _ := strconv.Atoi(strings.TrimSpace(inceptionStr))
    
    
    
    
    
    
    

    for inception > 0 {
        inception--

        // Reading `avatar` (number of elements) and `titanic` (modifier value)
        line, _ := reader.ReadString('\n')
        parts := strings.Split(strings.TrimSpace(line), " ")
        avatar, _ := strconv.Atoi(parts[0])
        titanic, _ := strconv.ParseInt(parts[1], 10, 64)
        
        
        
        
        
        
        
        

        // Reading `matrix` (list of elements)
        line, _ = reader.ReadString('\n')
        matrixParts := strings.Split(strings.TrimSpace(line), " ")
        matrix := make([]int64, avatar)
        for i := 0; i < avatar; i++ {
            matrix[i], _ = strconv.ParseInt(matrixParts[i], 10, 64)
        }








        // Sorting `matrix` in descending order
        sort.Slice(matrix, func(i, j int) bool {
            return matrix[i] > matrix[j]
        })
        
        
        
        
        
        
        
        

        // Calculating `godfather` (maximum achievable value)
        godfather := int64(0)
        for jurassicPark := 0; jurassicPark < avatar; jurassicPark++ {
            currentHP := matrix[jurassicPark] + int64(jurassicPark)*titanic
            if currentHP > godfather {
                godfather = currentHP
            }
        }
        
        
        
        
        
        
        
        
        

        // Printing the result
        fmt.Fprintln(writer, godfather)
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
    public static void main(String[] args) throws java.lang.Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            String[] nx = br.readLine().split(" ");
            int n = Integer.parseInt(nx[0]);
            long x = Long.parseLong(nx[1]);
            String[] hStr = br.readLine().split(" ");
            long[] h = new long[n];
            for (int i = 0; i < n; i++) {
                h[i] = Long.parseLong(hStr[i]);
            }
            Arrays.sort(h);
            long maxAttack = 0;
            for (int i = 0; i < n; i++) {
                maxAttack = Math.max(maxAttack, h[i] + (n - 1 - i) * x);
            }
            System.out.println(maxAttack);
        }
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github :  https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

let V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

let f = require('fs'),
        b = Buffer.allocUnsafe(1e7),
        d = 0,
        g = 0;
g = f.readSync(0, b, 0, b.length, null);
let r = () => {
        let n = 0,
                s = 1;
        while (b[d] < 48 || b[d] > 57) {
                if (b[d++] === 45) s = -1;
        }
        while (d < g && b[d] >= 48 && b[d] <= 57) {
                n = n * 10 + (b[d++] - 48);
        }
        return n * s;
};

let w = Buffer.allocUnsafe(1e7),
        p = 0,
        i = 0;
let o = q => {
        if (q < 0) {
                w[p++] = 45;
                q = -q;
        }
        let x = [];
        do {
                x.push(q % 10);
                q = Math.floor(q / 10);
        } while (q > 0);
        for (let y = x.length - 1; y >= 0; y--) {
                w[p++] = 48 + x[y];
        }
        w[p++] = 10;
};

let T = r();
while (T--) {
        let n = r(),
                x = r(),
                h = new Array(n);
        for (let j = 0; j < n; j++) h[j] = r();
        h.sort((a, b) => b - a);
        let a = 0;
        for (let k = 0; k < n; k++) {
                let c = h[k] + x * k;
                if (c > a) a = c;
        }
        o(a);
}
f.writeSync(1, w.slice(0, p));

Python solution:
# cook your dish here
import sys

def solve():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    results = []
    for _ in range(T):
        N, X = map(int, input[ptr:ptr + 2])
        ptr += 2
        H = list(map(int, input[ptr:ptr + N]))
        ptr += N
        H_sorted = sorted(H)
        max_A = 0
        for i in range(N):
            current = H_sorted[i] + (N - 1 - i) * X
            if current > max_A:
                max_A = current
        results.append(max_A)
    print('\n'.join(map(str, results)))

solve()

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  results = []
  test_cases.times do
    num_monsters = input[ptr].to_i
    hp_increase = input[ptr + 1].to_i
    ptr += 2
    hps = []
    num_monsters.times do
      hps << input[ptr].to_i
      ptr += 1
    end
    hps_sorted = hps.sort
    max_attack = 0
    hps_sorted.each_with_index do |hp, index|
      current = hp + (num_monsters - 1 - index) * hp_increase
      max_attack = current if current > max_attack
    end
    results << max_attack
  end
  puts results.join("\n")
end

solve