Bhallaladeva Codechef Solution|Problem Code:AMR15D

Bhallaladeva  Codechef Solution

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 ith house has Ai 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 Ai 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 A1, A2, …, AN, where Ai denotes the number of gold plates in the ith 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 ith line denotes the value of K for the ith query.

Output

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

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • 0 ≤ K ≤ N-1
  • 1 ≤ Ai ≤ 104

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.

Leave a Comment