PROBLEM LINK:
Author: Sibasish Ghosh
Tester: Pritish Nayak
Editorialist: Sibasish Ghosh
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given the traits of a student, you need to decide which House the student will be sorted into. Each House has its own set of four traits. You need to figure out which House’s traits are present in the student the maximum number of times and sort the student into that House. If there are multiple Houses satisfying the condition, sort the student into the lexicographically smallest House.
EXPLANATION:
Create a 4\times 4 matrix that contains all the 16 traits. Each row of the matrix will contain all the 4 traits of a particular House.
Let’s think for a particular student. For each trait of that student, search the trait in the Traits Matrix. And note down the row where it was found. This row will represent the House the trait belongs to. Maintain a count for each House. Finally, print the House with the maximum count. If there are multiple Houses satisfying the condition, print the lexicographically smallest House.
Refer to the solutions below if you face any problem.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input3.txt","r",stdin);
// freopen("output3.txt","w",stdout);
ll t=1;
cin>>t;
string houses[4]={"Gryffindor", "Slytherin", "Ravenclaw", "Hufflepuff"};
string trait[4][4]={"Courage", "Bravery", "Chivalry", "Daring",
"Resourcefulness", "Cunning", "Ambition", "Determination",
"Intelligence", "Wit", "Wisdom", "Creativity",
"Diligence", "Dedication", "Fairness", "Patience"};
while(t--)
{
ll k,i,j,cnt[4]={0},mx=0;
cin>>k;
string s;
while(k--)
{
cin>>s;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(s == trait[i][j])
cnt[i]++;
}
}
}
string ans="z";
for(i=0;i<4;i++)
{
if(cnt[i] > mx)
{
mx=cnt[i];
ans=houses[i];
}
else if(cnt[i] == mx)
ans=min(ans,houses[i]);
}
cout<<ans<<"\n";
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int N;
cin>>N;
assert(N>=1&&N<=100000);
set<string> mpp[4];
mpp[0]={"Courage", "Bravery", "Chivalry","Daring"};
mpp[1]={"Diligence", "Dedication", "Fairness","Patience"};
mpp[2]={"Intelligence", "Wit", "Wisdom", "Creativity"};
mpp[3]={"Resourcefulness", "Cunning", "Ambition","Determination"};
for (int i = 0; i < N; i++)
{
int K;
cin>>K;
assert(K>=1&&K<=16);
int a[4]={0};
for(int j = 0; j< K; j++)
{
string s;
cin>>s;
int cnt=0;
for(int l=0;l<4;l++)
{
if(mpp[l].find(s)!=mpp[l].end())
a[l]++,cnt++;
}
assert(cnt>0);
}
int mx=*max_element(a,a+4);
if(a[0]==mx)cout<<"Gryffindor\n";
else
if(a[1]==mx)cout<<"Hufflepuff\n";
else
if(a[2]==mx)cout<<"Ravenclaw\n";
else
cout<<"Slytherin\n";
}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
Feel free to write your approach in the comments