HackerRank Mandragora Forest problem solution

In this HackerRank Mandragora Forest problem solution, The evil forest is guarded by vicious mandragoras. Garnet and her pet must make a journey through. She starts with 1 health point (s) and 0 experience point.

As she encounters each mandragora, her choices are:

1. Garnet's pet eats mandragora i. This increments s by 1 and defeats mandragora i.
2. Garnet's pet battles mandragora i. This increases p by s x H[i] experience points and defeats mandragora i.

Once she defeats a mandragora, it is out of play. Given a list of mandragoras with various health levels, determine the maximum number of experience points she can collect on her journey.

Problem solution in Python.

N = int(input())

for n in range(N):
    input()
    hps = sorted(list(map(int, input().split())))
    s = 1
    total = sum(hps)
    for hp in hps:
        if (s+1) * (total - hp) <= s * total:
            break
        s += 1
        total -= hp
    print(s * total)

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            sc.nextLine();
            
            long totalH = 0L;
            List<Long> nums = new ArrayList<Long>();
            String line = sc.nextLine();
            String[] tokens = line.split(" ");
            for (String s : tokens) {
                long nj = Long.parseLong(s);
                nums.add(nj);
                totalH += nj;
            }
            Collections.sort(nums);
            //Arrays.sort(nums);
            long bestScore = 0;
            int eaten = 0;
            long s = totalH;
            
            while (s > bestScore) {
                bestScore = s;
                totalH -= nums.get(eaten);
                eaten += 1;
                s = (1L + eaten) * totalH;
            }
            System.out.println(bestScore);
        }
    }
}

{"mode":"full","isActive":false}

Problem solution in C++.

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

#define MAXN 100001

typedef long long int ll;

int n;
ll t[MAXN];
void wyk()
{
	scanf("%d",&n);
	for(int i = 0;i < n;++i)
		scanf("%lld",&t[i]);
	sort(t,t + n);
	ll s = n;
	ll wyn = 0;
	for(int i = n - 1;i >= 0;--i)
	{
		wyn = max(wyn,s * t[i]);
		t[i - 1] += t[i];
		--s;
	}
	printf("%lld\n",wyn);
}
int main()
{
	int a;	scanf("%d",&a);
	while(a--)
	{
		wyk();
	}
	return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include<stdio.h>
#include<stdlib.h>
typedef long long unsigned llu;
typedef unsigned u;
int F(const void*x,const void*y){return*(int*)x-*(int*)y;}
u H[111111];llu S[111111];
int main()
{
 u t,n,i,k;llu r,x,y;
 for(scanf("%u",&t);t--;)
 {
  scanf("%u",&n);k=1;r=0;
  for(i=-1;++i<n;)scanf("%u",H+i);
  qsort(H,n,sizeof(u),F);
  for(S[i=n]=0;i--;)S[i]=S[i+1]+H[i];
  for(i=-1;++i<n;)
  {
   x=S[i]*k;
   y=S[i+1]*(k+1);
   if(y>x)++k;
   else r+=H[i]*(llu)k;
  }
  printf("%llu\n",r);
 }
 return 0;
}

{"mode":"full","isActive":false}