TopCoder SRM 450 Div 1 Medium (Earn)

I was searching for what problem to solve today. I tried some - few were too difficult and few were too easy or uninteresting. So, I decided to randomly solve a TopCoder Division 1 medium problem. This one came up.

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. 

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

 Now, there were 2 things that came intuitively to my mind -

1. If you decide to spend on building factories or hiring specialists, you have to spend as much money as possible. There is no point spending half and saving the other half.
2. F and S have to stay as close as possible throughout the process.

The second one is easy to prove. Lets say we have 2 numbers - x & y where x > y. Now, if we can increase either of them by one, which one should we do?

(x+1)y = xy + y

x(y+1) = xy + x

So, x(y+1) > (x+1)y

Its clear that we will have to increase the minimum of the two numbers.

As target is at most 10^12, we will need no more than 10^6 factories or specialists. So, we can just simulate the process. In each step, we can do one of the 3 things -

1. Go till the end with current number of factories and specialists.
2. If we have enough gold, we can buy factories / specialists in a way such that their difference is minimal.
3. If we don't have enough gold, we can save current day's gold for future use. In fact, instead of going one day at a time, we can calculate number of days required to acquire the minimum amount of gold needed to buy anything and advance our simulation to that day.

Though it may seem natural to do this simulation using recursion, it will get segmentation fault as no. of steps can be as great as 10^6.

Another trick is to avoid the overflow. As n and k can be as high as 10^12, multiplying them will result in overflow.

C++ Source code -

/*
Problem Name : Earn
Problem Number : TopCoder SRM 450 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10389&rd=13904
Problem Type : Simulation, Greedy
Difficulty : 6.5 / 10
Interest : 7 / 10
Date : November 21, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;

#define min(a,b) (((a)<(b))?(a):(b))

struct StrongEconomy{
 long long earn(long long n, long long k, long long price, long long target) {
  long long res = 10000000, cur = 0, cur_day = 0;
  long long z,d,x;
  res*=res;
  while(1) {
   if(k > n) swap(n,k);
   if(cur >= target) break;
   if(log((long double)n)+log((long double)k) >= log((long double)target-cur)) { //log to prevent overflow
    res = min(res, cur_day+1); 
    break; 
   }

   //go through till the end
   res = min(res, cur_day + (target - cur + n*k-1) / (n*k));

   //buy factory or specialist
   if(cur >= price) {
    z = cur / price;
    d = n - k;
    if(d >= z) k+=z;
    else {
     z -= d;
     k = n;
     n += (z/2);
     k += (z/2);
     if(z%2 == 1) n++;
    }
    cur -= (cur/price)*price;
   }
   else { //save gold
    x = (price - cur + n*k-1) / (n*k);
    cur += (n*k*x);
    cur_day += x;
   }
  }
  return res;
 }
};

Do you have any suggestions on what should I solve next?