Maahismathi

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.

Example:

Input:  4
3 2 1 4
2
0
2
Output: 10 3

Approach

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Maahismathi {
    public static void main(String[] argsthrows Exception {
        int n = 4;
        int[] golds = { 3214 };
        Arrays.sort(golds);
        int q = 2;
        int[] queries = { 02 };
        for (int query : queries) {
            System.out.println(getValue(query, golds));
        }
    }

    static Map<IntegerIntegermemo = new HashMap<>();

    private static int getValue(int queryint[] golds) {
        if (memo.containsKey(query))
            return memo.get(query);
        int len = golds.length, paidIdx = 0, paidAmt = 0;
        int processed = 0;
        while (processed < len) {
            paidAmt += golds[paidIdx++];
            processed++;
            processed += query;
        }
        memo.put(query, paidAmt);
        return paidAmt;
    }
}


No comments:

Post a Comment