Age of Lumberjacks

# Age of Lumberjacks ## Problem Statement In the strategy game **Age of Lumberjacks**, players manage resources to expand their economy. The game begins with a **Town Center**, $n$ **Lumberjacks**, and $200$ units of wood. Wood serves as the primary currency for all game actions. The Town Center can be commanded to **create an additional Lumberjack** at a cost of $w$ units of wood. This process takes $t$ seconds, and the Town Center can only process one such command at a time. Each Lumberjack diligently collects $x$ units of wood per second. The smallest unit of time considered in the game is $1$ second. All wood collection and spawning events occur precisely at integer multiples of $t$ seconds, or at $T=0$. Your objective is to determine the **minimum initial number of Lumberjacks, $n$**, required such that a player can continuously spawn new Lumberjacks without ever running out of wood. This means that at the precise moment an additional Lumberjack finishes spawning (which is an integer multiple of $t$ seconds), there must be at least $w$ units of wood available to immediately command the Town Center to begin spawning the next Lumberjack. This condition must hold for the very first Lumberjack spawn at $T=0$ as well. If it's impossible to achieve continuous spawning, you should indicate this. ## Input Format The input consists of a single line containing three values: - First value: $t$ (an integer, $1 \le t \le 1000$), representing the time in seconds required to spawn one lumberjack. - Second value: $x$ (a float, $0 < x \le 1000$), representing the rate at which a single lumberjack collects wood per second. - Third value: $w$ (an integer, $1 \le w \le 1000$), representing the wood cost to spawn one lumberjack. ## Output Format The output should be a single integer: - The minimum initial number of lumberjacks, $n$, required for continuous spawning. - If no such $n$ exists (i.e., continuous spawning is impossible), return $-1$. ## Sample Test Cases ### Sample Input 1 ``` 25 0.2 50 ``` ### Sample Output 1 ``` 3 ``` ## Explanation 1 Let $n$ be the initial number of lumberjacks. We are given $t=25$, $x=0.2$, and $w=50$. The game starts with $200$ units of wood. First, let's calculate the wood collected by one lumberjack over $t=25$ seconds: $Y = x \cdot t = 0.2 \cdot 25 = 5$ units of wood. To achieve continuous spawning, the number of active lumberjacks must eventually be sufficient to collect at least $w=50$ units of wood every $t$ seconds. The minimum number of lumberjacks required for this sustainable state is $L_{min\_sustainable} = \lceil w/Y \rceil = \lceil 50/5 \rceil = 10$. We need to find the minimum initial $n$ such that we can continuously pay for new lumberjacks until we reach $10$ or more active lumberjacks, without the wood ever dropping below $w$ when a payment is due. Let's trace the scenario for $n=3$ initial lumberjacks: - **At $T=0$ (before 1st additional spawn):** We have $3$ lumberjacks and $200$ wood. Since $200 \ge w=50$, we can command the 1st additional lumberjack. Wood becomes $200 - 50 = 150$. The Town Center is busy for $t=25$ seconds. During this interval, $3$ lumberjacks are active. - **At $T=t=25$ (before 2nd additional spawn):** The 1st additional lumberjack finishes. During $[0, 25)$, $3$ lumberjacks collected $3 \cdot Y = 3 \cdot 5 = 15$ wood. Total wood is $150 + 15 = 165$. Now there are $3+1=4$ lumberjacks. Since $165 \ge w=50$, we can command the 2nd additional lumberjack. Wood becomes $165 - 50 = 115$. During this interval, $4$ lumberjacks are active. - **At $T=2t=50$ (before 3rd additional spawn):** The 2nd additional lumberjack finishes. During $[25, 50)$, $4$ lumberjacks collected $4 \cdot Y = 4 \cdot 5 = 20$ wood. Total wood is $115 + 20 = 135$. Now there are $4+1=5$ lumberjacks. Since $135 \ge w=50$, we can command the 3rd additional lumberjack. Wood becomes $135 - 50 = 85$. During this interval, $5$ lumberjacks are active. - **At $T=3t=75$ (before 4th additional spawn):** The 3rd additional lumberjack finishes. During $[50, 75)$, $5$ lumberjacks collected $5 \cdot Y = 5 \cdot 5 = 25$ wood. Total wood is $85 + 25 = 110$. Now there are $5+1=6$ lumberjacks. Since $110 \ge w=50$, we can command the 4th additional lumberjack. Wood becomes $110 - 50 = 60$. During this interval, $6$ lumberjacks are active. - **At $T=4t=100$ (before 5th additional spawn):** The 4th additional lumberjack finishes. During $[75, 100)$, $6$ lumberjacks collected $6 \cdot Y = 6 \cdot 5 = 30$ wood. Total wood is $60 + 30 = 90$. Now there are $6+1=7$ lumberjacks. Since $90 \ge w=50$, we can command the 5th additional lumberjack. Wood becomes $90 - 50 = 40$. During this interval, $7$ lumberjacks are active. - **At $T=5t=125$ (before 6th additional spawn):** The 5th additional lumberjack finishes. During $[100, 125)$, $7$ lumberjacks collected $7 \cdot Y = 7 \cdot 5 = 35$ wood. Total wood is $40 + 35 = 75$. Now there are $7+1=8$ lumberjacks. Since $75 \ge w=50$, we can command the 6th additional lumberjack. Wood becomes $75 - 50 = 25$. During this interval, $8$ lumberjacks are active. - **At $T=6t=150$ (before 7th additional spawn):** The 6th additional lumberjack finishes. During $[125, 150)$, $8$ lumberjacks collected $8 \cdot Y = 8 \cdot 5 = 40$ wood. Total wood is $25 + 40 = 65$. Now there are $8+1=9$ lumberjacks. Since $65 \ge w=50$, we can command the 7th additional lumberjack. Wood becomes $65 - 50 = 15$. During this interval, $9$ lumberjacks are active. - **At $T=7t=175$ (before 8th additional spawn):** The 7th additional lumberjack finishes. During $[150, 175)$, $9$ lumberjacks collected $9 \cdot Y = 9 \cdot 5 = 45$ wood. Total wood is $15 + 45 = 60$. Now there are $9+1=10$ lumberjacks. Since $60 \ge w=50$, we can command the 8th additional lumberjack. Wood becomes $60 - 50 = 10$. During this interval, $10$ lumberjacks are active. At this point, we have $10$ lumberjacks. Since $10 \cdot Y = 10 \cdot 5 = 50 = w$, we have reached the sustainable state where $L_{active} \cdot Y \ge w$. Any subsequent spawn will also be affordable. Thus, $n=3$ works. Now, let's consider $n=2$ initial lumberjacks: - **At $T=6t=150$ (before 7th additional spawn):** Following the same logic, with $n=2$, after paying for the 6th additional lumberjack, we would have $0$ wood, and $2+6=8$ lumberjacks active. During the interval $[125, 150)$, $8$ lumberjacks collect $8 \cdot Y = 40$ wood. Total wood becomes $0 + 40 = 40$. Now there are $8+1=9$ lumberjacks. At this moment, $40 < w=50$. We cannot afford to command the 7th additional lumberjack. Thus, $n=2$ fails. Therefore, the minimum initial number of lumberjacks required is $3$. ### Sample Input 2 ``` 10 1.0 250 ``` ### Sample Output 2 ``` -1 ``` ## Explanation 2 The initial wood is $200$ units. The cost to spawn a lumberjack is $w=250$. Since $w > 200$, the player cannot even afford to command the first lumberjack at $T=0$. Thus, continuous spawning is impossible, and the function returns $-1$. ## Constraints - $1 \le t \le 1000$ - $0 < x \le 1000$ - $1 \le w \le 1000$ - Time limit: 1 second - Memory limit: 256 MB