Problem Link:
Author: Sufiyan Ansari
Tester: Pankaj Goyal
Editorialist: Sufiyan Ansari
Difficulty
CAKEWALK
PREREQUISITES
Basic Coding Knowledge
PROBLEM
Chef Tushar is going to Chefland to get cookies for Snigdh’s birthday. He found an Ugly Toad on the road who allows only those passengers who can present him his favourite passcode P.
Ugly Toad defines passcodes as those Positive Numbers which are strictly lesser than 100 and NOT have more than two positive factors.
Chef Tushar doesn’t know this strange passcode and gives Ugly Toad T passcodes \{P_1, P_2, P_3,…,P_T\}.
For each passcode print “COOKIES” if it is correct passcode or print “HUNGRY” if it is wrong passcode.
EXPLANATION & SOLUTION:
Passcodes are Positive Numbers which are strictly lesser than 100 and NOT have more than two positive factors
Many Coders would have thought is just all prime numbers less than 100. But that’s where they miss one point “NOT have more than two positive factors.” , hence ‘1’ also passes the condition.
So, passcodes = {all prime less than 100} U {1}
As max value of T is 10000 and that of P is 10^5 and we don’t have to care about P >= 100, so any method (sieve or brute force) can be used to pass all test cases.
Setter's Solution: Sieve Solution
/*
Author : Mohd Sufiyan Ansari
g++ -std=c++17 -o sufi
Love it and You will be loved.
*/
#include<bits/stdc++.h>
#define test_cases true
#define ll long long int
#define ull unsigned long long int
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll,ll>
#define vpl vector<pll>
#define matrix(x,n,m) vector<vll>x(n,vll(m))
#define mll map<ll,ll>
#define itr iterator
#define MIT(T,X) map<T,X>::iterator
#define loop(i,x,n) for(int i=x;i<n;i++)
#define PB push_back
#define pB pop_back
#define MP make_pair
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793238462
#define test int t=1;if(test_cases)cin>>t;for(int T=1;T<=t;T++)
#define FIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define desc(x) sort(all(x)),reverse(all(x))
#define mod 1000000007
#define mod1 998244353
#define INF 1e18
#define sz(p) p.size()
#define endl "\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n";
#define Case(n) cout<<"Case #"<<n<<": "
#define ANS cout<<ans<<"\n"
using namespace std;
template <typename T> void print(T &p){cout<<p<<" ";}
template <typename T> void print(T v[],int n){for(int i=0;i<n;i++)print(v[i]);}
template <typename T> void print(pair<T,T> p){cout<<p.ff<<" "<<p.ss<<"\n";}
template <typename T> void print(vector<T> &v){int size=v.size();for(int i=0; i<size; i++) print(v[i]);cout<<endl;}
template <typename T> void print(vector<vector<T>> &v){for(auto i : v)print(i);}
template <typename T> void print(map<T,ll> &ma){for(auto it:ma)cout<<it.ff<<" "<<it.ss<<"\n";}
template <typename T> void read(T &n){cin>>n;}
template <typename T> void read(vector<T> &v){for(int i=0;i<v.size();i++)read(v[i]);}
template <typename T> void read(T v[],int n){for(int i=0;i<n;i++)cin>>v[i];}
/* ----------- MAIN PROGRAM ------------- */
const int sieve_size = 101;
bool prime[sieve_size];
void Sieve()
{
memset(prime,true,sizeof(prime));
for(int i=2;i<sieve_size;i++)
{
if(prime[i])
{
for(int p=i*i;p<sieve_size;p += i)
prime[p]=false;
}
}
prime[1]=true;
}
void sufiyan(int T)
{
int p;
cin>>p;
if(p>=100 || !prime[p])
cout<<"HUNGRY\n";
else
cout<<"COOKIES\n";
}
/* --------------- DRIVER PROGRAM -------------------- */
int main()
{
FIO;
Sieve();
test sufiyan(T);
return 0;
}
Setter's Solution: Brute Force Solution
/*
Author : Mohd Sufiyan Ansari
g++ -std=c++17 -o sufi
Love it and You will be loved.
*/
#include<bits/stdc++.h>
#define test_cases true
#define ll long long int
#define ull unsigned long long int
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll,ll>
#define vpl vector<pll>
#define matrix(x,n,m) vector<vll>x(n,vll(m))
#define mll map<ll,ll>
#define itr iterator
#define MIT(T,X) map<T,X>::iterator
#define loop(i,x,n) for(int i=x;i<n;i++)
#define PB push_back
#define pB pop_back
#define MP make_pair
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793238462
#define test int t=1;if(test_cases)cin>>t;for(int T=1;T<=t;T++)
#define FIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define desc(x) sort(all(x)),reverse(all(x))
#define mod 1000000007
#define mod1 998244353
#define INF 1e18
#define sz(p) p.size()
#define endl "\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n";
#define Case(n) cout<<"Case #"<<n<<": "
#define ANS cout<<ans<<"\n"
using namespace std;
template <typename T> void print(T &p){cout<<p<<" ";}
template <typename T> void print(T v[],int n){for(int i=0;i<n;i++)print(v[i]);}
template <typename T> void print(pair<T,T> p){cout<<p.ff<<" "<<p.ss<<"\n";}
template <typename T> void print(vector<T> &v){int size=v.size();for(int i=0; i<size; i++) print(v[i]);cout<<endl;}
template <typename T> void print(vector<vector<T>> &v){for(auto i : v)print(i);}
template <typename T> void print(map<T,ll> &ma){for(auto it:ma)cout<<it.ff<<" "<<it.ss<<"\n";}
template <typename T> void read(T &n){cin>>n;}
template <typename T> void read(vector<T> &v){for(int i=0;i<v.size();i++)read(v[i]);}
template <typename T> void read(T v[],int n){for(int i=0;i<n;i++)cin>>v[i];}
/* ----------- MAIN PROGRAM ------------- */
bool goodPasscode(int p)
{
if(p>=100)
return false;
if(p==1)
return true;
for(int i=2;i*i<=p;i++)
if(p%i==0)
return false;
return true;
}
void sufiyan(int T)
{
int p;
cin>>p;
if(goodPasscode(p))
cout<<"COOKIES\n";
else
cout<<"HUNGRY\n";
}
/* --------------- DRIVER PROGRAM -------------------- */
int main()
{
FIO;
test sufiyan(T);
return 0;
}
Tester's Solution: Sieve Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<bool> prime(101 + 1, true);
for (int i = 2; i * i <= 101; i++){
if (prime[i]){
for (int j = i * i; j <= 101; j += i) prime[j] = false;
}
}
int t; cin >> t;
while (t--){
int n; cin>>n;
if(n<100 && prime[n]) cout<<"COOKIES\n";
else cout<<"HUNGRY\n";
}
}