365. Check if It Is Possible to Survive on the Island

You must survive on an island for exactly M days (numbered 1 to M). A market is open on the first N days of every 7-day week (a day d is a market day if (d-1) mod 7 < N) and closed the rest of the week. Each market visit lets you buy enough food to cover that day plus the next S-1 days (S consecutive days starting from the day of purchase). Find the minimum number of market visits needed to have food on every day through day M, or print -1 if it's impossible.

Input: The first line contains M, the number of days to survive. The second line contains N, the number of market days per 7-day week. The third line contains S, the number of days of food bought per market visit. Output: Print a single integer - the minimum number of market visits needed, or -1 if survival is impossible.

1 <= M <= 10^6, 1 <= N <= 7, 1 <= S <= 10^6

The market schedule's WEEKLY pattern ((d-1) mod 7 < N) needs to be correctly translated into an explicit list (or on-the-fly check) of which days are actual market days - getting this modular arithmetic exactly right is a common source of off-by-one errors in this problem.

Find the minimum number of market visits needed to have enough food for every day of a stay on an island, given a weekly market schedule. Brute force: Try every possible combination of which market days to visit and check if all M days get covered - this is combinatorially expensive, when the classic greedy 'furthest-reaching valid choice' interval-covering technique gives the true minimum directly. Optimised: Always choosing the LATEST available market day that still covers the current first-uncovered day maximizes how far forward coverage extends with each visit - this greedy strategy (identical in spirit to the classic 'minimum gas stations to refuel' problem) is provably optimal for minimum-count interval covering.

Walk through the days from 1 to M one at a time, maintaining a counter of how many days of food are currently stocked. Whenever the counter reaches zero and today is not a market day, survival is impossible; whenever the counter reaches zero (or is about to run out) and today is a market day, buy immediately (adding S days of coverage) - buying as late as possible without ever running out is always at least as good as buying earlier, since it never leaves food unused. This greedy just-in-time simulation correctly finds the minimum number of visits in a single linear pass over the days, rather than searching over all possible subsets. Time: O(M) Space: O(1)

Because the market's open/closed pattern repeats with a fixed period of 7 days, the number of visits needed per complete week can be computed once analytically instead of simulated day by day: first check the feasibility condition (if fewer than 7 days of food can be bought within a week's N market days, i.e. N*S < 7, and not every day is a market day, survival is impossible), then compute how many visits a full week requires and multiply by the number of complete weeks in M, finally handling the leftover partial week's days separately using the same reasoning. This turns the O(M) day-by-day simulation into an O(1) arithmetic computation by exploiting the weekly periodicity instead of stepping through every day. Time: O(1) Space: O(1)

Enumerate all possible subsets of the market days available across the M days, and for each subset check whether buying on exactly those days (each purchase covering S consecutive days starting from the purchase day) keeps food available on every single day from 1 to M; among all valid subsets, keep the one using the fewest visits. This is correct by exhaustive search over every possible purchasing plan, but the number of subsets of market days is exponential, making it completely impractical once M grows large. Time: O(2^(number of market days)) Space: O(M)

1. Recognize this as an INTERVAL-COVERING problem: a market visit on day d covers days d through d+S-1, and the goal is covering every day from 1 to M using the fewest visits. 2. Whenever your current coverage runs out, look among all market days at or BEFORE the first uncovered day, and pick the LATEST one (the one pushing coverage furthest forward) - the same greedy idea as the classic 'minimum refueling stops' problem. 3. If no market day exists at or before the first uncovered day when needed, survival is impossible - print -1.

Time: O(M) - determining market days and simulating the greedy coverage process both scale linearly with the number of days. Space: O(1) extra space beyond a few running trackers (current coverage end, visit count).

N = 7 (market open every day), S = 1 (each visit covers only its own day), and M at its maximum of 10^6 to confirm the interval-covering greedy runs efficiently; also cases where no market day falls before the first uncovered day (print -1).

Be ready to connect this directly to the classic 'minimum refueling stops to reach a destination' greedy problem - both share the identical 'always pick the furthest-reaching valid option at each gap' technique.