PROBLEM LINK :
Author and Editorialist: Sahil Soni
Tester: Pankaj Sharma
DIFFICULTY:
EASY
PREREQUISITES:
Basic observations, sorting,
PROBLEM:
There are N vacant rooms in chef’s hotel in each room maximum K peoples can stay, there come G groups of peoples to stay in chef’s hotel, i^th group have P_i members.
For each group, you can allot one or more than one room as per their need but in a room member of same group can stay.
A group stays in the chef’s hotel if every member of their group gets the room.
Your task is to find maximum no. of groups that can stay in the chef’s hotel.
EXPLANATION:
we have to find maximum numbers of the group that can stay, by basic observation we can conclude
a group with minimum numbers of members will capture minimum rooms in the chef’s hotel.
Now for getting maximum numbers of groups we will allot rooms to the groups having minimum members.
To implement the above idea first we sort given an array of group members in increasing order. Now we start allotting rooms to groups as per their size (smaller first) and check if there are sufficient vacant rooms so given group can stay, by dividing numbers of members in a group with k (capacity of room ) we will get the rooms needed for that group to stay , repeat it until all groups gets rooms or there are not sufficient rooms for any group to stay and we will get the count of the maximum number of groups that can stay.
TIME COMPLEXITY:
Time complexity is O(GlogG)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#include <fstream>
using namespace std ;
int main(){
int t;cin>>t;
while(t--){
int n,k,g;
cin>>n>>k>>g;
int p[g];
for(int i=0;i<g;i++)
cin>>p[i];
sort(p,p+g);
int count=0;
for(int i=0;i<g;i++){
int rooms = p[i]/k;
if(p[i]%k!=0)
rooms++;
if(rooms<=n){
count++;
n = n-rooms;
}
}
cout<<count<<endl;}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define pb push_back
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}
ll max(ll a, ll b) {return (a > b ? a : b);}
ll min(ll a, ll b) {return (a < b ? a : b);}
void yes_or_no(ll x) {if (x) cout << "YES\n"; else cout << "NO\n";}
const ll MOD = 1e9 + 7;
ll add(ll x, ll y) {ll ans = x + y; return (ans >= MOD ? ans - MOD : ans);}
ll mul(ll x, ll y) {ll ans = x * y; return (ans >= MOD ? ans % MOD : ans);}
ll sub(ll x, ll y) {ll ans = x - y; return (ans < 0 ? ans + MOD : ans);}
void solve() {
ll ans = 0;
int n, k, g;
cin >> n >> k >> g;
int p[g];
for (int i = 0; i < g; i++)
cin >> p[i];
sort(p, p + g);
int idx = 0;
int roomsAvailable = n;
while (idx < g and roomsAvailable>0)
{
ll neededRooms = (p[idx] + k - 1) / k;
if (neededRooms > roomsAvailable) break;
idx++;
roomsAvailable -= neededRooms;
ans++;
}
cout << ans << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t; while (t--)
solve();
return 0;
}
For doubts, please leave them in the comment section, I’ll address them.