Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
Airlift
You and your family are trapped on a flood-prone island.When you called the emergency services to ask for assistance . They promised to send aircraft to airlift your family. As long as the combined weight of the two passengers is less than or equal to K
,each aircraft is only permitted to to carry a maxmum of K and a maximum of K and a maximum of two other passengers in addition to the pilot . You are given the following
- The maximum capacity of the aircraft
- The total number of family members
- An array weights where weights[i], reprsent the weight of the ith family member
Task
Return the minimum number of aircraft required to airlift the family
If not possible, return -1.
Example
Assumptions:
K = 5
N= 9
weights = [3,3,5,2,1,4,5,1,5]
Constraints
1 <= K <= 5*109
1 <= N <= 105
1 <= weights[i] <= 109
weights contain only positive integers
Sample Input Sample Output
6 3
4
3 5 4 3
Shopping and billing
In a shop wth N counters. M peccie arrive for billing at different times denoted as smell. Each person selects the counter with the shortest queue, based on the number of people already present. if a counter is empty the pets immediate biting, otherefse, they join the queue
For every person, output the tit
rig and leave the counter.
Notes
- It takes 1 unit of time for the counter to process a person's bills
- The counter processess the next person mmediately after the current person leaves .
- The time is given in increasing order of arrival at the counters . In formal terms time[i] <= time[i+1]
Function Description
Complete the function solve . This function takes the following 3 parameters returns teh required answer
- N- Represents the numer of counters
- M: Represents the number of persons
- tiime: Represents an array containing the entry time of the people
Input format for custom testing
Note: Use this input format if you are testing against custom Input or writing code in a language
where we don't provide bollerplate code.
- The first line contains N denoting the number of counters.
- The second line contains M denoting the number of persons.
- The third line contains an array time, indicating the entry time of the people.
Output format
Print a single line of M space-separated integers, denoting the exit times of the people.
Constraints
1<= N <= 105
1 <= M <= 105
0 <= position[i] <= 109
Sample Input Sample Output
2 1 1 2 2
4
0 0 0 0Explanation
N=2
M=4
position = |0, 0. 0. 0]
Output
1 1 2 2
- The first person arrives at O, finds both counters empty, goes to counter 1, and leaves at
- The second person arrives at 0, finds counter 2 empty, and leaves at 1
- The third person arrives at 0, finds both counters with 1 person, goes to counter 2, and leaves at 2
- The fourth person arrives at 0, finds counter 1 with 1 person and counter 2 with 2 persons, goes to counter 1 and leaves at 2
Sample Input Sample Output
10 88234 93641 99414 99901 99990 99994 99997 99997 99
31
88233 93640 99410 99900 99989 99993 99996Special Package
You are the manager of a grocery store and you want to create special package deal for your customers . you are given a matrix of prices of size N * M . for different products ,with each row representing different category of products and esch column representing a different product in the category
You want to select one item from each category such that the total cost of the package is as close as possible to a specific target price K
You need to determine the minimum absolute difference between targer price and actual cost of the package you can create products in the matrix
Fuction Description
Complete the function solution() provided in the editor .The function takes the following 4 parameters and return the solution
- N: Represents the number of categories
- M:Represents the number of items in each category
- K: Repreents the target price
- price: represents the price of items
Input format for custom testing
Note: Use this input format if you are testing against custom input or writing code in a language
where we don't provide boilerplate code
The first line contains N denoting the number of categories.
The second line contains M denoting the number of items in each category.
* The third line contains K denoting the target price.
• Each of the next N lines contains M integers each, denoting the price of the items.
Output format
Print an integer, representing the minimum absolute difference between the target price and the total cost of the package.
Constraints
1 <= N,M <= 70
1 <= price[i][j] <= 70
1 <= K <= 800
Entering edit mode
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int k;
int n;
cin>>k>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
int z=min(k-1,n-1);
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<=z;i++)
{
pq.push(v[i]);
}
z++;
vector<int> ans;
while(!pq.empty())
{
int x=pq.top();
ans.push_back(x+1);
pq.pop();
if(z<n and v[z]<=x+1)
{
int p=max(x+1,v[z]);
pq.push(p);
z++;
}
if(z<n and pq.size()<k)
{
pq.push(v[z]);
z++;
}
}
for(int i=z;i<n;i++)
ans.push_back(v[i]+1);
for(int x:ans)
cout<<x<<" ";
}
Question 2 Solution probably this
Entering edit mode
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int k;
int n;
cin>>k>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
int z=min(k-1,n-1);
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<=z;i++)
{
pq.push(v[i]);
}
z++;
vector<int> ans;
while(!pq.empty())
{
int x=pq.top();
ans.push_back(x+1);
pq.pop();
if(z<n and v[z]<=x+1)
{
int p=max(x+1,v[z]);
pq.push(p);
z++;
}
if(z<n and pq.size()<k)
{
pq.push(v[z]);
z++;
}
}
for(int i=z;i<n;i++)
ans.push_back(v[i]+1);
for(int x:ans)
cout<<x<<" ";
}
Question 2 Solution probably this
Entering edit mode
3rd question
Hack--> since 1<=n,m,items<=70 so map will store at max 4900 entries.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
ll n,m,k;
cin>>n>>m>>k;
vector<vector<ll>> items(n,vector<ll>(m));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>items[i][j];
}
}
unordered_map<ll,ll> mp;
for(int i=0;i<m;i++)
{
mp[items[0][i]]++;
}
for(int i=1;i<n;i++)
{
unordered_map<ll,ll> mpp;
for(int j=0;j<m;j++)
{
for(auto item:mp)
{
mpp[item.first+items[i][j]]++;
}
}
mp=mpp;
}
ll ans=INT_MAX;
for(auto i:mp)
{
ans=min(ans,abs(k-i.first));
}
cout<<ans<<"\n";
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Entering edit mode
Solution to Question no 2 . The approach is we use a set to find the empty counter and cnt is used to see which counter is occupied. We push {time+1, counterid} into pq. Note we use min heap here since we need to find the shortest queue. We remove all the person <= arrivalTime[i]. If there is no free counter when a person comes then he is bound to wait and we pop the first vale and allocate that counter to him since it is guaranteed to have shortest waiting time for that person. Lastly we add pq.top().time+1 as the exit time. Else if counter is free then we will assign counter to him and add arrivalTime[i]+1 as the answer.
using ll = long long int ;
int main() {
ll n,m;
cin>>n>>m;
vector <ll> pos(m);
for (int i=0;i<m;i++ ) {cin>>pos[i];}
priority_queue < pair <int,int> , vector <pair <int,int>>, greater <pair <int,int> >> pq;
set <ll> free;
vector <int> ans;
vector <ll> cnt(n+2,0);
for (ll i=1;i<=n;i++) {free.insert(i);}
for (ll i=0;i<m;i++ ) {
ll Time=pos[i];
while (pq.size () && pq.top().first <= Time) {
pair <int,int> top=pq.top();
pq.pop();
int id=top.second;
if (cnt[id] == 1) {
free.insert(id);
}
cnt[id]--;
}
if (free.size() == 0) {
pair <int,int> top=pq.top();
pq.pop();
int id=top.second;
if (cnt[id] == 1) {
free.insert(id);
}
cnt[id]--;
int begin= *free.begin();
cnt[begin]+=1;
free.erase(begin);
pq.push({top.first+1,begin});
ans.push_back(top.first+1);
}
else {
int begin= *free.begin();
cnt[begin]+=1;
pq.push({ Time+1 ,begin});
free.erase(begin);
ans.push_back(Time+1);
}
}
for (auto &i:ans) {
cout<<i<<" ";
}
return 0;
}
Entering edit mode
please send solution of third question also
Entering edit mode
1
static int u1=(int)1e9;
public static void main(String args[]) throws IOException {
int n=in.nextInt();
int m=in.nextInt();
int k=in.nextInt();
int arr[][]=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
arr[i][j]=in.nextInt();
}
}
f(0,0,n,m,arr,k,0);
print(u1);
}
public static void f(int i,int j,int m,int n,int grid[][],int k,int sum){
if(i==m){
System.out.print(sum+" ");
u1=Math.min(u1,Math.abs(sum-k));
return;
}
for(int u=j;u<n;u++){
sum+=grid[i][u];
f(i+1,0,m,n,grid,k,sum);
sum-=grid[i][u];
}
}this can be the solution of q3 but it can give tle
Entering edit mode
Here is my solution to 3rd problem:
https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/submissions/927777874/https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/submissions/927777874/
Entering edit mode
2nd question solution let me know if there are any wrongs
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<int>arr(m);
for(int i=0;i<m;i++){
cin>>arr[i];
}
int blocklen=n;
priority_queue<int,vector<int>,greater<int>>pq;
for(int i=0;i<m;i++){
pq.push(arr[i]);
}
int ind=0;
vector<int>ans(m);
int k=1;
while(!pq.empty()&&blocklen>0){
int a=pq.top();
pq.pop();
ans[ind]=a+k;
ind++;
blocklen--;
if(blocklen==0){
blocklen=n;
k++;
}
}
for(auto i : ans){
cout<<i<<" ";
}
return 0;
}
Entering edit mode
#include <bits/stdc++.h>
using namespace std;
int solve(int i,int t,vector<vector<int>>&mat,int sum,vector<vector<int>>&dp){
int n=mat.size();
int m=mat[0].size();
if(i==n){
return abs(t-sum);
}
if(dp[i][sum]!=-1)return dp[i][sum];
int ans=INT_MAX;
for(int ind=0;ind<m;ind++){
ans=min(ans,solve(i+1,t,mat,sum+mat[i][ind],dp));
}
return dp[i][sum]=ans;
}
int main()
{
int n;
cin>>n;
int m;
cin>>m;
int k;
cin>>k;
vector<vector<int>>arr(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>arr[i][j];
}
}
vector<vector<int>>dp(n+1,vector<int>(5000,-1));//5000 because that can be maximum sum possible i.e 4900
int sum=0;
cout<<solve(0,k,arr,sum,dp)<<endl;
return 0;
}3 rd question memoisation solution
Entering edit mode
void solve()
{
ll n ,k ; cin >> n>> k ;
vll v(n); fl(i ,0 ,n ) cin >> v[i] ;
sort(vbe) ;
if(v[n-1]>k)
{
cout << -1 <<nl ;
return ;
}
if(n==1)
{
if(v[0]<=k)
cout << 1 << nl ;
else
cout << -1 << nl ;
return ;
}
ll i = 0 ,j = n-1 ;
ll ans =0 ,c= 0;
while(i<j)
{
ll sum = v[i]+v[j] ;
if(sum<=k)
{ans++ ;i++ ,j-- ; }
else
{
j-- ;
c++ ;
}
}
cout << ans+c << nl ;
}
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
ll a[m];
vector<ll> ans(m,0);
for(int i=0;i<m;++i){
cin >> a[i];
}
vector<vector<int>> v(n);
for(int i=0;i<m;++i){
v[i%(n)].push_back(i);
}
ll diparture=0;
for(int i=0;i<n;++i){
if(v[i].size()!=0){
ans[v[i][0]]=a[v[i][0]]+1;
diparture=ans[v[i][0]];
}
for(int j=1;j<v[i].size();++j){
int val1=a[v[i][j]];
if(diparture>val1){
ans[v[i][j]]=diparture+1;
diparture++;
}
else{
diparture=val1+1;
ans[v[i][j]]=diparture;
}
}
}
for(int i=0;i<m;++i){
cout << ans[i] << "\n";
}
return 0;
}
solution for ques 2;
Loading Similar Posts
Question 1 solution