PROBLEM LINK
Author: Shivanand
Tester: S N
Editorialist: Adarsh Raj
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
You are facing problems of your own as there is constant threat of your real identity being disclosed. Hence, in order to test your loyalty, the Front Man has designated you the task of helping in organizing the next game. However, what they don’t know that not only you are a very good detective, but also a good coder.
The upcoming game will be conducted in various rooms, which can accommodate at most four participants. Front Man tried to make this task difficult for you by randomly dividing all the participants in NN groups. Since you have observed the participants closely, you have prepared a list where each ithith group consists of AiAi people (1≤Ai≤41≤Ai≤4). You are a good person, so you will try to place the people of one group together. Now, your task is to find the minimum number of rooms required for the game.
Note: One room can have more than one group of people
QUICK EXPLANATION:
With a little bit of precomputation, this can be solved by accomodating groups of 3 with groups of 1, and two groups of 2’s together.
EXPLANATION:
Each room has a capacity of 4 , so a group of 4 people will be allotted a room each. So first, the total numbers of rooms = number of groups of 4.
Now, groups of 3’s will be accommodated with groups of 1’s. This means, that first all groups of 3’s will be allotted a room each, and the same number of 1’s groups (if available) will be accommodated in those rooms.
Now, total number of rooms allotted = groups of 4’s + groups of 3’s
And, groups of 1’s left to be accommodated are calculated by max(0,number of 3’s - number of 1’s).
Now, two groups of 2-2 members each are given a room, so total number of rooms will be incremented by (groups of 2’s)/2.
Now, all groups left will be accommodated accordingly.
SOLUTION:
int n;
cin>>n;
vector<int>v;
for(int i=0; i<n; i++)
{
long long a;
cin>>a;
v.push_back(a);
}
int a=0,b=0,c=0,d=0;
for(int i=0; i<n; i++)
{
if(v[i]==1)
{
a++;
}
if(v[i]==2)
{
b++;
}
if(v[i]==3)
{
c++;
}
if(v[i]==4)
{
d++;
}
}
int ans=0;
ans+=d;
ans+=c;
if(a>c)
{
a=a-c;
}
else{
a=0;
}
if(b%2==0){
ans+=(b/2);
b=0;
}
else{
ans+=(b/2);
b=2;
}
int e=b+a;
if(e%4==0)
{
ans+=(e/4);
}
else{
ans+=(e/4);
ans++;
}
cout<<ans<<"\n";