353. Roti Prata - Minimum Time to Cook P Pratas

There are L cooks, each with a rank R (a positive integer); all cooks work in parallel starting at time 0. A cook of rank R takes exactly R minutes to cook a 1st prata, another 2R minutes to cook a 2nd, another 3R minutes for a 3rd, and so on (the k-th prata that cook makes finishes at cumulative time R*(1+2+...+k) = R*k*(k+1)/2 minutes). Given the L cooks' ranks and the total number of pratas P that must be made, find the minimum time by which all P pratas can be ready.

Input: The first line contains an integer L (number of cooks). The second line contains L space-separated integers, the ranks. The third line contains the integer P, the total pratas needed. Output: Print a single integer - the minimum time by which all P pratas can be ready.

1 <= L <= 50, 1 <= P <= 1000, 1 <= R <= 8

This is yet another instance of 'binary search on the answer' with a MONOTONIC feasibility condition (more time always yields at least as many pratas) - the same underlying pattern as Eko, Painter's Partition, and Aggressive Cows, just with a different, cook-specific feasibility formula.

Several cooks work in parallel, each getting progressively SLOWER at making more pratas - find the minimum time by which a required total number of pratas can all be made. Brute force: Simulate every cook's progress minute by minute (or prata by prata) and track cumulative totals directly - this can work but is much less efficient than directly computing, for any given time T, exactly how many pratas each cook could have finished using the closed-form formula. Optimised: Since 'total pratas ready by time T' only increases (never decreases) as T grows, binary searching on T directly - using the closed-form R*n*(n+1)/2 formula to instantly compute each cook's progress at a candidate T (rather than simulating minute by minute) - finds the minimum feasible T efficiently.

Binary search directly on the candidate total time T: for a given T, each cook of rank R can complete the largest k such that R*k*(k+1)/2 <= T, which can be found in O(sqrt(T/R)) by incrementing or in O(1) via the quadratic formula; summing this k across all L cooks gives the total pratas produced by time T, a value that is monotonically non-decreasing in T. Binary search for the smallest T where this total is >= P. This collapses the search from being proportional to P (as in the heap simulation) down to logarithmic in the time range, which matters when P and R combine to produce very large completion times. Time: O(L * log(R * P^2)) Space: O(1)

Instead of stepping through every minute, maintain a min-heap keyed by each cook's next prata-completion time. Repeatedly pop the cook with the earliest completion time, count that prata as made, compute and push that cook's next completion time (adding the next increment for their rank), and stop once P pratas have been counted; the last popped time is the answer. This skips over all the 'nothing happens' minutes between events, so the work is proportional to the number of pratas produced rather than the number of minutes elapsed. Time: O(P log L) Space: O(L)

Simulate minute by minute: at each unit of time, check whether any cook completes a prata at exactly that moment (by tracking each cook's next completion time) and increment the total made. Stop as soon as the running total reaches P and report that minute. This is correct by direct simulation of the process described, but the total time can be large (proportional to R*P^2), so stepping through every single minute is very slow. Time: O(T_max * L) where T_max ~ R*P^2 Space: O(L)

1. Binary search on the total TIME T. 2. For a candidate T, compute how many pratas EACH cook can finish by then: a cook of rank R can finish the largest n such that R*n*(n+1)/2 <= T. 3. Sum this count across all cooks; if the total meets or exceeds P, T is feasible - try a SMALLER T; otherwise, try a LARGER one.

Time: O(L log(max T)) - for each of the O(log(max T)) binary search steps, computing every one of the L cooks' progress takes O(L) (using the closed-form formula, itself requiring a quick per-cook search or formula inversion for n). Space: O(1) extra space beyond the input cook ranks.

Test L = 1 (a single cook makes every prata), all cooks with rank R = 1 (fastest possible), and L = 50 with P = 1000 for performance.

Be ready to derive the closed-form 'how many pratas can rank-R cook finish by time T' relationship clearly - recognizing the cumulative sum formula R*(1+2+...+k) = R*k*(k+1)/2 is the foundation the whole binary search rests on.