Chef and Direction Codechef Solution|Problem Code: WESTAND

Chef and Direction Codechef Solution

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] ≤ 1000P[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  Chase2learn. This tutorial is only for Educational and Learning purpose.

Leave a Comment