Gold Mining Codechef Solution

Gold Mining Codechef Solution: Chef and Chefu are working as gold miners. There are a total of NN gold mines, numbered 11 through NN. For each valid ii, the ii-th gold mine contains GiGi gold in total; if only Chef worked in it, it would take him AiAi days to completely mine it, while if only Chefu worked in it, it would take him BiBi days.

Each of our miners may only work in one mine at a time, but they may decide to start working in another mine at any time (even in the middle of some day), any number of times. They also choose the mines to work in independently from each other and they may work in the same mine at the same time.

Mining gold is a continuous process, i.e. if a miner works for tt days (where tt is a real number) in a mine where this miner has mining speed gg gold per day, then he will mine g⋅tg⋅t gold. Obviously, it is impossible to work in a mine after no gold remains in it. For example, if a gold mine contains 3030 gold and Chef needs 22 days to completely mine it, but he spends 11 day in it, then he will mine 1515 gold; if Chefu needs 11 day to completely mine the same gold mine, and both Chef and Chefu start working in this mine at the same time, it will be empty after 2/32/3 days ― Chefu will mine 2020 gold, while Chef will mine 1010 gold.

At each point of time, both Chef and Chefu know the gold mine in which the other miner is working. Each of them wants to gather the maximum amount of gold for himself. Find the amounts of gold the miners will have if they both act optimally.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • NN lines follow. For each valid ii, the ii-th of these lines contains three space-separated integers GiGi, AiAi and BiBi.

Output

For each test case, print a single line containing two space-separated real numbers ― the amount of gold mined by Chef and the amount of gold mined by Chefu. Your answer will be considered correct if the absolute or relative error of each amount of gold does not exceed 10−610−6.

Constraints

  • 1≤T≤1,0001≤T≤1,000
  • 1≤N≤1051≤N≤105
  • 1≤Gi≤1051≤Gi≤105 for each valid ii
  • 1≤Ai≤1051≤Ai≤105 for each valid ii
  • 1≤Bi≤1051≤Bi≤105 for each valid ii
  • the sum of NN over all test cases does not exceed 106106

Subtasks

Subtask #1 (50 points): N≤2N≤2

Subtask #2 (50 points): original constraints

Sample Input 1 

2
1
30 2 1
3
10 1 1
20 2 2
30 3 3

Sample Output 1 

10.00000 20.00000
30.00000 30.00000

Gold Mining  – CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		int t=Integer.parseInt(br.readLine());
		while(t-->0)
		{
		    int n=Integer.parseInt(br.readLine());
		    double d1=0;
		    double d2=0;
		    while(n-->0)
		    {
		        String in[]=br.readLine().split(" ");
		        double g=Double.parseDouble(in[0]);
		        double a=Double.parseDouble(in[1]);
		        double b=Double.parseDouble(in[2]);
		        d1+=g*(b/(a+b));
		        d2+=g*(a/(a+b));
		    }
		    sb.append(d1+" "+d2+"\n");
		}
		System.out.print(sb);
	}
}

Gold Mining  – CodeChef Solution in CPP

#include <iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
#include<bits/stdc++.h>
#include "limits.h"
typedef priority_queue<ll> pq;
ll power(ll a,ll b){
    if(b==0)return 1;
    if(b%2)return a*power(a*a,(b-1)/2);
    else return power(a*a,b/2);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int T;
	cin>>T;
	while(T--){
	    ll N;
	    cin>>N;
	    ld m1=0,m2=0;
	    for(ll i=0;i<N;++i){
	        ld G,A,B,D;
	        cin>>G>>A>>B;
	        D=G/(A+B);
	        m1+=(B*D);
	        m2+=(A*D);
	    }
	    cout<<fixed<<setprecision(6);
	    cout<<m1<<" "<<m2<<"\n";
	}
	return 0;
}

Gold Mining- CodeChef Solution in Python

def solve():
    gold_mines = []
    N = (int)(input())
    for _ in range(N):
        amount, A, B = map(int, input().split())
        gold_mines.append([amount, A, B])
    ans1, ans2 = 0.0, 0.0
    for i in range(N):
        sumRatio = gold_mines[i][1] + gold_mines[i][2]
        ans1 += (gold_mines[i][0] * gold_mines[i][2]) / (sumRatio)
        ans2 += (gold_mines[i][0] * gold_mines[i][1]) / (sumRatio)
    print("{0:.10f}".format(ans1), "{0:.10f}".format(ans2))
if __name__ == '__main__':
    T = (int)(input())
    for _ in range(0, T):
        solve()

Disclaimer: The above Problem (Gold Mining ) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment