StrongEconomy

SRM 450 · 2009-10-17 · by Rydberg

SRM 450 · 2009-10-17 · by Rydberg · Greedy, Simulation

Show categories

Class Name: StrongEconomy

Return Type: long

Method Name: earn

Arg Types: (long long, long long, long long, long long)

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.

Constraints

n, k, price and target will each be between 1 and 10^12, inclusive.

Examples

2
1
2
10
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.

2
1
2
9
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.

1
1
500000
1000002
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.

5
4
15
100
Returns: 5

Don't spend your gold at all.

4294967296*4294967296 = 0 in long long

Submissions are judged against all 313 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StrongEconomy with a public method long long earn(long long n, long long k, long long price, long long target) · 313 test cases · 2 s / 256 MB per case