Bhallaladeva Codechef Solution|Problem Code:AMR15D

Hello coders, today we are going to solve Bhallaladeva Codechef Solution|Problem Code:AMR15D.

Problem

Bhallaladeva was an evil king who ruled the kingdom of Maahishmati. He wanted to erect a 100ft golden statue of himself and he looted gold from several places for this. He even looted his own people, by using the following unfair strategy:

There are N houses in Maahishmati, and the i^th house has A_i gold plates. Each gold plate costs exactly 1 Nimbda, which is the unit of currency in the kingdom of Maahishmati. Bhallaladeva would choose an integer K, and loots all the houses in several steps. In each step:

1. He would choose a house i which hasn’t been looted yet, pay the owner exactly A_i Nimbdas, and take away all the gold plates in that house (Hence, he also ends up looting this house).
2. He would now choose atmost K houses which haven’t been looted yet and take away all the gold plates from these houses without paying a single Nimbda (Yes, he takes all of them for free).

He repeats the above steps until all the N houses have been looted. Your task is to devise a strategy for Bhallaladeva to loot the houses in some order, so that the number of nimbdas he has to pay is minimium. You’ll also be given multiple values of K (Q of them to be precise), and you need to find the minimum number of nimbdas for each of these values.

Input

The first line of input consists of a single integer N denoting the number of houses in Maahishmati. The second line of input consists of N space separated integers denoting A₁, A₂, …, A_N, where A_i denotes the number of gold plates in the i^th house. The third line of input consists of a single integer Q denoting the number of values of K to follow. Each of the following Q lines consist of a single integer, where the value on the i^th line denotes the value of K for the i^th query.

Output

Output exactly Q integers on separate lines, where the output on the i^th line denotes the answer for the i^th value of K.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 0 ≤ K ≤ N-1
• 1 ≤ A_i ≤ 10⁴

Sample Input 1 

4
3 2 1 4
2
2

Sample Output 1 

10
3

Bhallaladeva CodeChef Solution in JAVA

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] A = readArray(sc);
		int[] K = readArray(sc);
		Arrays.stream(solve(A, K)).forEach(System.out::println);
		sc.close();
	}
	static int[] readArray(Scanner sc) {
		int size = sc.nextInt();
		int[] result = new int[size];
		for (int i = 0; i < result.length; i++) {
			result[i] = sc.nextInt();
		}
		return result;
	}
	static int[] solve(int[] A, int[] K) {
		Arrays.sort(A);
		int[] prefixSums = buildPrefixSums(A);
		int[] result = new int[K.length];
		for (int i = 0; i < result.length; i++) {
			result[i] = prefixSums[divideToCeil(prefixSums.length, K[i] + 1) - 1];
		}
		return result;
	}
	static int[] buildPrefixSums(int[] A) {
		int prefixSum = 0;
		int[] prefixSums = new int[A.length];
		for (int i = 0; i < prefixSums.length; i++) {
			prefixSum += A[i];
			prefixSums[i] = prefixSum;
		}
		return prefixSums;
	}
	static int divideToCeil(int x, int y) {
		return x / y + (x % y == 0 ? 0 : 1);
	}
}

Disclaimer: The above Problem (Bhallaladeva) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.