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:
- Garnet’s pet eats mandragora i. This increments s by 1 and defeats mandragora i.
- 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)
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); } } }
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("%lldn",wyn); } int main() { int a; scanf("%d",&a); while(a--) { wyk(); } return 0; }
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("%llun",r); } return 0; }