Bhallaladeva Codechef Solution

Hello Programmers In this post, you will know how to solve the Bhallaladeva Codechef Solution. Problem Code: AMR15D

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Mahasena Codechef Solution