Lecture 66 :- PRATA SPOJ

"PRATA - Roti Prata" is another classic problem on the Sphere Online Judge (SPOJ) platform. The problem is described as follows:

Rosie is a chef and she loves her job. She decided to open a new restaurant and named it "Rosie's Roti Prata." She wants to minimize the time it takes to cook prata for her customers. There are N chefs available, and each takes some amount of time to cook a single prata. The customers come one by one, and each customer has a certain rank. The time taken to cook a prata for a customer is (rank * time taken by the chef). Rosie wants to know the minimum time required to cook pratas for all her customers.

The task is to find the minimum time T required to cook pratas for all the customers.

To solve this problem, we can use binary search to find the minimum time T. We will set the search space to be the range from 1 (minimum time) to a large enough upper bound (e.g., 10^8). Then, we will check if it is possible to cook all the pratas in time T. If it is possible, we try to minimize this time by moving to the left half of the search space. Otherwise, we move to the right half.

Here's the C++ implementation of the PRATA problem:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> bool isPossible(std::vector<int>& chefs, int pratas, int timeLimit) {    int pratasCooked = 0;    for (int time : chefs) {        int count = 1;        int timeTaken = time;        while (timeTaken <= timeLimit) {            pratasCooked += count;            count++;            timeTaken += time;        }    }    return pratasCooked >= pratas; } int minCookingTime(std::vector<int>& chefs, int pratas) {    int left = 1;    int right = 1e8; // Upper bound (can be adjusted based on constraints)    int result = -1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (isPossible(chefs, pratas, mid)) {            result = mid;            right = mid - 1;        } else {            left = mid + 1;        }    }    return result; } int main() {    int T;    std::cin >> T;    while (T--) {        int pratas;        std::cin >> pratas;        int N;        std::cin >> N;        std::vector<int> chefs(N);        for (int i = 0; i < N; i++) {            std::cin >> chefs[i];        }        int minTime = minCookingTime(chefs, pratas);        std::cout << minTime << std::endl;    }    return 0; }

Example Input:

Copy code

2 10 4 1 2 3 4 8 5 1 1 1 1 1

Example Output:

Copy code

12 5

In this code, the isPossible function checks if it is possible to cook all the pratas in time timeLimit. The minCookingTime function uses binary search to find the minimum time required to cook all the pratas. The time complexity of this algorithm is O(N * log(maxTime)), where N is the number of chefs and maxTime is the upper bound of the search space.