Problem Statement |
| | As a serious strategy-games player, you know how important it is for your country to have a strong economy. In order to make this happen, you've just built n factories and hired k specialists. Unfortunately, you now have no gold left, and you must figure out the fastest way to raise target units of gold.
In a single round, you earn F*S units of gold, where F is the number of factories and S is the number of specialists you currently have. At the end of each round, you can build more factories and hire more specialists. Building one new factory or hiring one new specialist costs price units of gold. As long as you can afford them, there is no limit to the number of factories and specialists you have. Return the minimum number of rounds required to earn at least target units of gold.
|
| |
Definition |
| | | Class: | StrongEconomy | | Method: | earn | | Parameters: | long, long, long, long | | Returns: | long | | Method signature: | long earn(long n, long k, long price, long target) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | n, k, price and target will each be between 1 and 10^12, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 4 | | In the first round you will earn 2*1 = 2 units of gold and must spend them on hiring a new specialist. In each of the rounds that follow, you will earn 2*2 = 4 units of gold. You need 3 more rounds in order to earn at least 10 units of gold. |
|
|
| 1) | |
| | | Returns: 3 | | In the first round you will earn 2*1 = 2 units of gold and must spend them on hiring a new specialist. In the second round you will earn 2*2 = 4 units of gold and must spend them on building a factory and hiring another specialist. In the third round you will earn 3*3 = 9 units of gold. |
|
|
| 2) | |
| | | Returns: 1000001 | | Wait 500000 rounds in order to earn 500000*1*1 = 500000 units of gold. At the end of the 500000th round, spend all your money to build a factory (or to hire a specialist). In each of the rounds that follow, you will earn 2*1 = 2 units of gold, so you need 500001 more rounds in order to earn the required 1000002 units of gold. |
|
|
| 3) | |
| | | Returns: 5 | | Don't spend your gold at all. |
|
|