Header Ad

HackerEarth Festivals problem solution

In this HackerEarth Festivals problem solution, Alice likes festivals a lot as we all do. He also likes spending money on these festivals. He spends money buying various things at these festivals. But he has the problem of forgetting. He only remembers his top three maximum spendings for any festival.
For eg, on Holi he spends 25 units on colors, 50 units on water sprays, 100 units on gifts, 150 units on sweets but he remembers only his top 3 spendings,i.e., 50, 100 & 150.
Now as the year ends he wants to know the festival on which he spent most of the money that he can remember.


HackerEarth Festivals problem solution


HackerEarth Festivals problem solution.

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

int main()
{

int t;
cin >> t;

while(t--){
int N;

cin >> N;

map<string, priority_queue<ll> >Events;


for(int i = 1; i <= N; i++){

string S;
ll x;
cin >> S >> x;

Events[S].push(x);
}

pair<string,ll>res;
res.second = 0;

for(auto it:Events){

ll sum = 0;

int top = min(3LL, (ll)it.second.size());

while(top--){

sum += it.second.top();
it.second.pop();
}

if(sum > res.second)res = {it.first, sum};
}

cout << res.first << " " << res.second << endl;

}


return 0;
}

Second solution

#include<bits/stdc++.h>
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
int main()
{
//fast_io;
int t;
assert(cin>>t);
assert(t>=1 && t<=100);
while(t--)
{
int n;
assert(cin>>n);
assert(n>=1 && n<=1e4);
map<string,vector<ll> >mp;
for(int i=1;i<=n;i++)
{
string temp;int val;
assert(cin>>temp>>val);
assert(temp.size()>=1 && temp.size()<=10);
assert(val>=1 && val<=1e9);
for(int i=0;i<temp.size();i++)
assert((temp[i]>='a' && temp[i]<='z') || (temp[i]>='A' && temp[i]<='Z'));
mp[temp].push_back(val);
}
ll maxx=0;
map<string,vector<ll> > :: iterator it;
for(it=mp.begin();it!=mp.end();it++)
{
vector<ll>temp=it->second;
sort(temp.begin(),temp.end());
ll sum=0;
for(int cnt=1,i=temp.size()-1;cnt<=3 && i>=0;cnt++,i--)
{
sum+=temp[i];
}
maxx=max(maxx,sum);
it->second.clear();
it->second.push_back(sum);
}
for(it=mp.begin();it!=mp.end();it++)
{
if(it->second[0]==maxx){cout<<it->first<<" "<<maxx<<"\n";break;}
}
}
return 0;
}

Post a Comment

0 Comments