Show problems as
Classic problem #2327MediumDynamic ProgrammingQueueSimulation

Number of People Aware of a Secret

Real-world version: Couriers Still Holding the Shortcut
Tracked in this browser only
Read Number of People Aware of a Secret on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot's couriers pass a routing shortcut along by word of mouth. On day 1 exactly one courier knows it.

A courier who learns the shortcut on day d behaves as follows:

  • on each of the days d + quiet, d + quiet + 1, ..., d + stale - 1 that courier explains it to exactly one courier who has never heard it;
  • at the start of day d + stale the courier's notes go stale: from that day on the courier no longer knows the shortcut and never explains it again.

The depot employs far more couriers than the shortcut can ever reach, so every explanation lands on someone who has never heard it. Since quiet is smaller than stale, every courier gets at least one day of explaining.

Return how many couriers know the shortcut at the end of day n. The count grows quickly, so return it modulo 1000000007.

Examples

Example 1

Input
n = 9, quiet = 3, stale = 5
Output
5

The first courier learns it on day 1 and explains it on days 4 and 5, so one courier learns on day 4 and one on day 5. The day-4 courier explains on days 7 and 8, and the day-5 courier explains on days 8 and 9. Learning days are therefore 1, 4, 5, 7, 8, 8 and 9, seven couriers in all. Notes from day 1 go stale at the start of day 6 and notes from day 4 at the start of day 9, leaving five couriers at the end of day 9.

Example 2

Input
n = 5, quiet = 1, stale = 4
Output
14

Each courier explains the shortcut on the three days after learning it. Counting the couriers who learn on each day gives 1 on day 1, 1 on day 2, 2 on day 3, 4 on day 4 and 7 on day 5, fifteen couriers in all. Only the first courier's notes have gone stale by the end of day 5, so fourteen couriers still know the shortcut.

Example 3

Input
n = 7, quiet = 6, stale = 7
Output
2

The first courier's only explaining day is day 7, so one more courier learns the shortcut that day. Neither courier's notes have gone stale by the end of day 7.

Constraints

  • 2 <= n <= 1000
  • 1 <= quiet <= 1000
  • 2 <= stale <= 1000
  • quiet is strictly smaller than stale, and stale is at most n.
  • Return the count modulo 1000000007.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def couriers_knowing_shortcut(n: int, quiet: int, stale: int) -> int:
Java
public int couriersKnowingShortcut(int n, int quiet, int stale)

More on the same topics