CODECHEF April Cook-off ( Div. 2 ) – Making a Meal in C++

In this C++ tutorial, we are going to discuss the codechef April Cook-off problem “Making a meal”. This problem uses the concept of string and basic mathematics only.

Problem Statement

There are total N strings S1, S2, S3,______Sn. We have to find that total how many times we can form the word “codechef” using the characters of these N strings. If a character appears more than one time it can be used many times. All characters are in lower case English letter.

INPUT

Input consists of test cases and for each test case it consists of an integer N and next N line follows strings.

OUTPUT

Output must consist of the maximum number of times we can form the word “codechef ” using the characters of N strings in each test case.

Algorithm

• Input N strings for each test case.
• Count the occurrence of characters ‘c’ , ‘o’ , ‘d’ , ‘e’ , ‘h’ , ‘f” for each string.
• Now, in each word of “codechef” c needed to be present 2 times, e 2 times and rest characters 1 time only.
• So, in run the while loop till frequency any character does not become zero and use a counter to check how many time you run the while loop also check that character ‘c’ and ‘e’ should be greater than 1 always.
• In while loop decrement count of character ‘c’ and ‘e’ twice while rest character once.

C++ code implementation for making a meal problem

#include<bits/stdc++.h>
#define Fast  std::ios::sync_with_stdio(false);  cin.tie(NULL);
#define pb  push_back
#define mp  make_pair
#define fi  first
#define se  second
#define all(x) x.begin(),x.end()
#define p pair<ll,ll>
#define pii pair<int,int>
#define mod (int)(1e9+7)
#define PI  (double)(3.14159265358979323846264338327950)
#define for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
ll i,j;

int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;

string s;

ll c=0,o=0,d=0,e=0,h=0,f=0;

for(i,0,n)
{
cin>>s;

for(j,0,s.length())
{
if(s[j]=='c')
c++;

if(s[j]=='o')
o++;

if(s[j]=='d')
d++;

if(s[j]=='e')
e++;

if(s[j]=='h')
h++;

if(s[j]=='f')
f++;
}
}

ll count=0;

while(c!=0 && o!=0 && d!=0 && e!=0 && h!=0 && f!=0 && c>1 && e>1)
{
count++;
c=c-2;
o--;
d--;
e=e-2;
h--;
f--;
}
cout<<count<<endl;
}
}

Example

Input

3
6
cplusplus
oscar
deck
fee
hat
near
5
code
hacker
chef
chaby
dumbofe
5
codechef
chefcode
fehcedoc
cceeohfd
codechef

1
2
5