Coupon System Codechef Solution

Chef is organizing an exam for certifying algorithmic skills. The exam will consist of three levels: 1, 2 and 3, and will be organized at various cities numbered from 1 to 100.

You have received n coupons which give discounts for the exam. Each coupon can be applied for a particular city, for a given level and will provide a certain discount.

You want to attempt all the three levels of the exam, and you are willing to go to different cities to avail the maximum discount. So, for each level, find out the maximum discount that you can avail, and which city you’d need to go to to do so. If there are multiple such cities, choose the city that has the least number. That is, if the discounts are same, city i is preferable over city j, if i < j.

Input

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer n denoting the number of coupons.
  • Each of the next n lines contains three space-separated integers city c, level l and discount x applicable in the i-th coupon.

Output

For each test case, output three lines. The first line should contain two space-separated integers: maximum discount for level 1, and the city where you can avail this discount. In case of ties, find the smallest numbered such city. Similarly, second and third line should contain similar info for second and third levels.

Constraints

  • 1 ≤ T ≤ 100
  • 3 ≤ n ≤ 100
  • 1 ≤ c ≤ 100
  • 1 ≤ l ≤ 3
  • 1 ≤ x ≤ 100
  • It is guaranteed that for each level, there will at least one coupon.

Example

Input
1
7
2 1 10
1 1 20
3 2 100
2 3 50
2 2 100
5 3 75
100 3 75

Output
20 1
100 2
75 5

Explanation

For Level 1, there are two discount coupons, which give a discount of 10 and 20 respectively. We choose the maximum, and that is for city 1. Hence the first line of output is “20 1”.

For Level 2, there are two discount coupons, both of which give a discount of 100. We choose the one which is for the city with the smaller number, and that is for city 2. Hence the second line of output is “100 2”.

For Level 3, there are three discount coupons, which give discounts of 50, 75 and 75. The maximum discount is 75, and so that leaves us with two coupons to decide from. We choose the one which is for the city with the smaller number, and that is for city 5. Hence the third line of output is “75 5”.

Coupon System – CodeChef Solution in JAVA

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
					Scanner s=new Scanner(System.in);
		int t=s.nextInt();
		while(t-->0)
		{
		    int n=s.nextInt();
		    int[] a=new int[n];
		    int[] b=new int[n];
		    int[] c=new int[n];
		    for(int i=0;i<n;i++)
		    {
		        a[i]=s.nextInt();
		        b[i]=s.nextInt();
		        c[i]=s.nextInt();
		      
		    }
		    int l=100;
		   
		    for(int i=1;i<=3;i++)
		    {
		       int x=0;  
		        for(int j=0;j<n;j++)
		        {
		            if(i==b[j])
		            {
		                if(x<c[j])
		                {
		                    l=a[j];
		                    x=c[j];
		                }
		                if(x==c[j])
		                {
		                    if(l>a[j])
		                    {
		                        l=a[j];
		                    }
		                }
		               
		             
		            }
		            
		        }
		           System.out.println(x+"  "+l);
		    }
		      
		    
		}
	}
}

Coupon System  – CodeChef Solution in CPP

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

int main() {
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		int a[n],b[n],c[n];
		int max1=0,max2=0,max3=0;
		for(int i=0;i<n;i++)
		{
			cin>>a[i]>>b[i]>>c[i];
			if(b[i]==1)
			{
				if(max1<c[i])
				max1 = c[i];
			}
			if(b[i]==2)
			{
				if(max2<c[i])
				max2 = c[i];
			}
			if(b[i]==3)
			{
				if(max3<c[i])
				max3 = c[i];
			}
		}
		int x=INT_MAX,y=INT_MAX,z=INT_MAX;
		for(int i=0;i<n;i++)
		{
			if(b[i]==1 && c[i]==max1)
			{
				if(x>a[i])
				x = a[i];
			}
			if(b[i]==2 && c[i]==max2)
			{
				if(y>a[i])
				y = a[i];
			}
			if(b[i]==3 && c[i]==max3)
			{
				if(z>a[i])
				z = a[i];
			}
		}
		cout<<max1<<" "<<x<<endl<<max2<<" "<<y<<endl<<max3<<" "<<z<<endl;
		
	}
	return 0;
}

Coupon System -CodeChef Solution in Python

for _ in range(int(input())):
    d = {}
    for _ in range(int(input())):
        c, l, dis =  map(int, input().split())
        if l in d.keys():
            if dis > d[l][0]:
                d[l] = [dis, c]
            elif dis == d[l][0]:
                if c < d[l][1]:
                    d[l] = [dis, c]
        else:
            d[l] = [dis, c]
    for k in d.keys():
        print(*d[k])

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

Leave a Reply

Your email address will not be published. Required fields are marked *