Hello Programmers In this post, you will know how to solve the Chef and Direction Codechef Solution. The Problem Code: WESTAND
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
Chef has opened new restaurant “Direction” and his first problem is to find cooks. Chef has K candidates, each of them is characterized by P[i] and S[i] – the number of dishes that he can cook per minute and the salary he wants, cook gets salary only once. Two cooks can’t work on the one order together, but every cook whenever he wants can interrupt another cook and start working on his order, even if the previous cook doesn’t finish some of the dishes from order. Moreover, the transition from one order to another is instantaneous (this time can be ignored).
The restaurant has received N orders. Each order is characterized by two numbers D[i] i M[i] – the number of dishes in order and the number of minutes that client is ready to wait. “Direction” is a new restaurant, so Chef doesn’t want to leave bad impression on clients and doesn’t want to let them go hungry.
Chief asks you to help him to resolve which of the K candidates should get an offer for this job. So, you have to choose some candidates, which can prepare all orders in time and at the same time you have to minimize expenses for the salaries for cooks. “Direction” opens in a minute with number 0. If you can not fulfill all orders in time, then output “-1”.
Input
The first line of input contains a single integer T denoting the number of test cases. This will be followed by T test cases.
The first line of each test case contains integer K denoting numbers of candidates.
Each of the next K line of each test case contains two integers P[i] and S[i] denoting the number of dishes that cook with number i can cook per minute and the salary he wants.
The next line of each test case contains N denoting numbers of orders.
Each of the next N lines of each test case contains two integers D[i] and M[i] denoting the number of dishes in order with number i and the number of minutes that client with number i is ready to wait.
Output
For each test case in a separate line output the minimum of possible costs for hiring cooks or “-1”.
Constraints and Subtasks
- 1 ≤ T ≤ 5
- 1 ≤ K ≤ 10
- 1 ≤ P[i] ≤ 1000
- 1 ≤ S[i] ≤ 100
- N = 1
- 1 ≤ D[i] ≤ 10000
- 1 ≤ M[i] ≤ 100
- 1 ≤ K ≤ 10
- 1 ≤ P[i] ≤ 1000, P[1] = P[2] = … = P[K]
- 1 ≤ S[i] ≤ 100
- 1 ≤ N ≤ 50
- 1 ≤ D[i] ≤ 10000
- 1 ≤ M[i] ≤ 100
- 1 ≤ K ≤ 10
- 1 ≤ P[i] ≤ 1000
- 1 ≤ S[i] ≤ 100
- 1 ≤ N ≤ 50
- 1 ≤ D[i] ≤ 10000
- 1 ≤ M[i] ≤ 100
Chef and Direction CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff static_cast<double>
struct cook{
int speed,salary;
};
struct order{
int time;
double dish;
double priority;
};
bool comp_cook(cook a, cook b){
return a.salary < b.salary;
}
bool comp_order(order a, order b){
return a.priority > b.priority;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t,k,n;
cin>>t;
while(t--){
cin>>k;
cook cooks[k];
for(int i=0;i<k;i++){
cin>>cooks[i].speed>>cooks[i].salary;
}
cin>>n;
order orders[n];
for(int i=0;i<n;i++){
int d;
cin>>d>>orders[i].time;
orders[i].dish = ff(d);
orders[i].priority = ff(orders[i].dish)/ff(orders[i].time);
}
if(n==1){
sort(cooks,cooks+k,comp_cook);
bool flag = false;
for(int i=0;i<k;i++){
if(orders[0].time * cooks[i].speed >= orders[0].dish)
{
flag = true;
cout<<cooks[i].salary<<endl;
break;
}
}
if (flag == false)
cout<<-1<<endl;
continue;
}
bool flag = true;
int check = cooks[0].speed;
for(int i=1;i<k;i++){
if (check != cooks[i].speed){
flag = false;
break;
}
}
//now for n!=1 and all cook speed equal
if (flag == true){
int max_t = -1;
sort(orders,orders+n,comp_order);
int cook_speed = cooks[0].speed;
for(int i=0;i<n;i++){
max_t = max(max_t,orders[i].time);
}
bool outer_flag = false;
int cook_needed = 0;
for(int i=1;i<=k;i++){
bool flag_check = true;
double arr[n+1][max_t+1] = {0};
order orders_temp[n];
memcpy(orders_temp,orders,n*sizeof(order));
for (int j=0;j<n+1;j++)
for(int k=0;k<max_t+1;k++)
arr[j][k] = 0.0;
for(int j=0;j<n;j++){
for(int k=orders_temp[j].time;k>=1;k--){
if (orders_temp[j].dish >= cook_speed){
if (arr[n][k] + 1.0 <= ff(i)){
arr[j][k] = 1.0;
orders_temp[j].dish -= cook_speed;
arr[n][k] += arr[j][k];
}
else{
double left = ff(i) - arr[n][k];
arr[j][k] = left;
arr[n][k] = ff(i);
orders_temp[j].dish -= left*ff(cook_speed);
}
}
else{
double req_time = ff(orders_temp[j].dish) / ff(cook_speed);
//cout<<req_time<<endl;
if (arr[n][k] + req_time <= ff(i)){
arr[j][k] = req_time;
orders_temp[j].dish = 0.0;
arr[n][k] += arr[j][k];
break;
}
else{
double left = ff(i) - arr[n][k];
//cout<<"*"<<left<<endl;
arr[j][k] = left;
arr[n][k] = ff(i);
orders_temp[j].dish -= left*ff(cook_speed);
}
}
}
// check if dish still remaining
if (orders_temp[j].dish > 0.0){
flag_check = false;
break;
}
}
if (flag_check == false){
// dish possible with current number of cook
// increase cooks if possible
}
else{
outer_flag = true;
cook_needed = i;
break;
}
}
// if outer flag true then possible otherwise not
if (outer_flag == true){
sort(cooks,cooks+k,comp_cook);
int ans = 0;
for(int i=0;i<cook_needed;i++){
ans += cooks[i].salary;
}
cout<<ans<<endl;
}
else{
cout<<-1<<endl;
}
}
else{
cout<<1000<<endl;
}
}
return 0;
}Disclaimer: The above Problem (Chef and Direction) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.
Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.
